Intereting Posts

Compound interest: why does everyone get it wrong?
The Jeep Problem and Nash's Friends
Necessary and sufficient conditions for differentiability.
Is this function bounded? Next question about integral $\int_{\partial M} \frac{1}{||y-x||} n_y \cdot \nabla_y \frac1{||y-x||} dS_y$.
How can I infer a result using primal feasibility, dual feasibility, and complementary slackness?
Can the equation $ax^2+by^2=cz^2$ be solved in integers (excluding trivial solutions)?
Strange combinatorial identity $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}\binom{2n-2k}{n-1}=0$
Why does $\frac{1 }{ 99989999}$ generate the Fibonacci sequence?
All roots of the quartic equation $a x^4 + b x^3 + x^2 + x + 1 = 0$ cannot be real
Product of sets and supremum
Number of birational classes of dimension d, geometric genus 0 varieties?
How can I prove $dz=dx+idy$?
Taking derivative of $L_0$-norm, $L_1$-norm, $L_2$-norm
Minimum area of the parallelepiped surface
How to solve an equation of the form $ax^2 – by^2 + cx – dy + e =0$?

If $n$ balls are thrown into $k$ bins (uniformly at random and independently), what is the probability that every bin gets at least one ball? i.e. If we write $X$ for the number of empty bins, what is $P(X=0)$?

I was able to calculate the $E(X)$ and thus bound with Markov’s inequality $P(X>=1) \le E(X)$ but I don’t how to work out an exact answer.

http://www.inference.phy.cam.ac.uk/mackay/itprnn/ps/588.596.pdf

- How can I solve bins-and-balls problems?
- Second pair of matching birthdays
- We throwing $m$ balls to $n$ cells…
- How many expected people needed until 3 share a birthday?
- Throwing $k$ balls into $n$ bins.
- Combinations, when placing n objects into k boxes, each box has its own size and the order in them doesn't matter?

- $\lim_n \frac{1}{n} E(\max_{1\le j\le n} |X_j|) = 0$
- Probability that $n$ random points on a circle, divided into $m$ fixed and equal sized slices are contained in less than $m/2$ adjacent slices.
- Domino Probability Problem
- finding Expected Value for a system with N events all having exponential distribution
- What is an approximation for Poisson binomial distribution?
- Help with an integral for: If U has a $\chi^2$ distribution with v df, find E(U) and V(U)
- Four balls with different colors in a box, how many times do I need to pick to see all four colors?
- A fair coin is tossed $n$ times by two people. What is the probability that they get same number of heads?
- Finding the confidence level and number of successes?
- How to calculate the probability of rolling 6 at least 5 times in a row, out of 50 tries?

What is the chance that all $k$ bins are occupied?

For $1\leq i\leq k$, define $A_i$ to be the event that the $i$th bin stays empty.

These are exchangeable events with $P(A_1\cdots A_j)=(1-{j\over k})^n$ and so

by inclusion-exclusion, the probability that there are no empty bins is

$$P(X=0)=\sum_{j=0}^k (-1)^j {k\choose j}\left(1-{j\over k}\right)^n.$$

Stirling numbers of the second kind can be used to give

an alternative solution to the occupancy

problem. We can fill all $k$ bins as follows: partition the balls

$\{1,2,\dots, n\}$ into $k$ non-empty sets, then assign the bin values $1,2,\dots, k$ to

these sets. There are ${n\brace k}$ partitions, and for each partition $k!$ ways to

assign the bin values. Thus,

$$P(X=0)={{n\brace k}\,k!\over k^n}.$$

I propose to use combinatorics. Namely, stars and bars formulae.

- Number of outcomes with at least one ball in every bin is $\tbinom{n

– 1}{k-1}.$ - Number of outcomes with any number of balls in every bin is $\tbinom{n + k – 1}{n}.$

Now just divide.

To count the outcomes for this question, using inclusion-exclusion formula is correct, but $n$ choose $k$ and then multiplied by $k!$ is only correct if the question is asking that “each bin has only one ball”. If n balls are thrown into $n$ bins, then, a simple answer is $n!$.

So the question asking at least one ball is complicated. We have to write down each possible way and sum up each combination, just like another question asking about each day per week has at least one call. If we have exact numbers, we can count the numbers of outcomes, but here, it is better to ask at least one ball with the setting of $n$ balls thrown into $n$ bins.

Set $X_i = 1$ if there is at least 1 ball in the $\textit{i}$th bin; and $0$ otherwise [$\textit{i}$ goes from 1 to k]. Then this question is asking what is $P[\sum\limits_{i=1}^k X_i = k]$. Given that each $X_i$s are independent of each other, $P[\sum\limits_{i=1}^k X_i=k]) = (P[X_i=1])^k =(1-P[X_i=0])^k =(1-(\frac{k-1}{k})^n)^k$

- Doubt about proof of factorization $f=pi$, where $i$ is acyclic cofibration and $p$ is fibration
- Average distance to a random point in a rectangle from an arbitrary point
- What is a Simple Group?
- “Intrinsic” treatment of projective spaces
- Show $\operatorname{rank}(A) + \operatorname{rank}(B) \ge \operatorname{rank}(A+B)$
- Derive the Poisson Formula for a bounded C-harmonic function in the upper half-plane.
- Approximation of $e$ using $\pi$ and $\phi$?
- Limit of sequence with floor function problem
- Two Circles and Tangents from Their Centers Problem
- Number of solutions of equation
- Combinatorics – Recurrence relation
- How to prove that operator is not compact in $L_2 (\mathbb{R})$
- How to find a nonzero $2 \times 2$ matrix whose square is zero?
- Intuition behind the Definition of Conditional Probability (for 2 Events)
- Why is there always a Householder transformation that maps one specific vector to another?