Intereting Posts

Why is F a UFD?
Hamiltonian Cycle Problem
Is the “binary operation” in the definition of a group always deterministic?
Improving my understanding of Cantor's Diagonal Argument
Image of ring homomorphism $\phi : \mathbb{Z} \to \mathbb{Q}$?
Modern approaches to mathematical notation
How to properly apply the Lie Series
Showing that the groups (Q,+) and (Q⁺,*) are not isomorphic
How do I find two integers – $x$ and $y$ – whose values satisfy the expression $x^2 + y^2 = z$, where $z$ is a perfect square?
How can I find an element $x\not\in\mathfrak mM_{\mathfrak m}$ for every maximal ideal $\mathfrak m$
The constant distribution
Why is full- & faithful- functor defined in terms of Set properties?
For integers $a$ and $b$, $ab=\text{lcm}(a,b)\cdot\text{hcf}(a,b)$
What is wrong with this proof of $0=1$?
Product Notation for Multiplication in Reverse Order

What is the probability of randomly putting $n$ elements into $k$ boxes ($k\leq n$) such that there is no empty box?

I have two different ideas:

- I could use the principle of inclusions and exclusions with $A_i=\{\text{box $i$ is empty}\}$: \begin{align}P(\text{no empty boxes})&=1-P\left(\bigcup_{i=1}^k A_i\right)=1-\sum_{i=1}^{k-1} (-1)^{k-1} \binom{k}{i}\left(\frac{k-i}{k}\right)^n\\&=\sum_{i=0}^{k-1}(-1)^k\binom{k}{i}\left(\frac{k-i}{k}\right)^n\end{align}
- There are $\binom{n+k-1}{k-1}$ different ways of putting $n$ elements in $k$ boxes. Putting the elements in such that no box remains empty should be the same as putting $n-k$ elements in $k$ boxes i.e. $\binom{n-1}{k-1}$. So the probability that no box is empty should be \begin{align}P(\text{no empty boxes})&=\frac{\binom{n-1}{k-1}}{\binom{n+k-1}{k-1}}\end{align}

The two solutions are different. I’m pretty sure the first on is correct. Where is the mistake in the second one? Is the problem that the different ways of putting the elements in the boxes are not equal-probable? Can I fix the second attempt somehow?

- How many $N$ of the form $2^n$ are there such that no digit is a power of $2$?
- Time to reach a final state in a random dynamical system (answer known, proof unknown)
- How find that $\left(\frac{x}{1-x^2}+\frac{3x^3}{1-x^6}+\frac{5x^5}{1-x^{10}}+\frac{7x^7}{1-x^{14}}+\cdots\right)^2=\sum_{i=0}^{\infty}a_{i}x^i$
- Combinatorial expression for all ternary strings that don't have consecutive 1's and 2's
- In how many ways can five letters be posted in 4 boxes?
- How to prove this using combinatorics?

- Conditional probability branching process
- What is the number of compositions of the integer n such that no part is unique?
- Proof that $a^b>b^a$ if $a<b$ are integers larger or equal to two and $(a,b)\neq (2,3),(2,4)$
- Finding a bound on the maximum of the absolute value of normal random variables
- Is this casino promotion exploitable?
- How many fours are needed to represent numbers up to $N$?
- A Combinatorial Proof of Dixon's Identity
- What is the probability of rolling $n$ dice until each side appears at least once?
- How many ways can $133$ be written as sum of only $1s$ and $2s$
- Ferrers Diagram Partitions

To see what’s wrong with the second approach, look at the case $n=k=2$. Call the $2$ objects $a$ and $b$. The $4$ equally likely outcomes are:

$$\begin{array}{c|c}

\text{Box }1&\text{Box }2\\ \hline

a,b\\

a&b\\

b&a\\

&a,b

\end{array}$$

Clearly the desired probability is $\frac12$.

When you say that there are $\binom{2+2-1}{2-1}=3$ possible distributions of the $2$ objects amongst the $2$ boxes, you’re talking about *indistinguishable* objects: the second and third cases in the table above are counted as a single distribution of the objects. The appropriate table is now this one, in which only one of the three distributions has objects in both boxes.

$$\begin{array}{c|c}

\text{Box }1&\text{Box }2\\ \hline

x,x\\

x&x\\

&x,x

\end{array}$$

Your second calculation gives the probability that a randomly selected distribution of $n$ indistinguishable objects amongst $k$ boxes has no empty boxes.

In your case the objects being distributed really are distinguishable: there’s a difference between the identity function on $\{0,1\}$ and the function $f(x)=1-x$, though both are surjective. Your second calculation, however, treats these as the same function: each puts one object in each of the two boxes, so to speak.

- Split up sum of products $\sum{a_i b_i}\approx(1/N)\sum{a_i}\sum{b_i}$ for uncorrelated summands?
- Show that $T$ is normal
- Why is $\mathfrak{sl}(n)$ the algebra of traceless matrices?
- Is it possible to get arbitrarily near any acute angle with Pythagorean triangles?
- How to prove the midpoint of a chord is also the midpoint of the line segment defined by the points of intersection of other two chords with it?
- Vandermonde determinant by induction
- How many ways so that $x+y+z\leq n$?
- What sequence does $\frac{1}{1-s-s^4}$ generate?
- Determinant of a large block matrix
- Do mathematicians, in the end, always agree?
- Does there exist non-compact metric space $X$ such that , any continuous function from $X$ to any Hausdorff space is a closed map ?
- Are polynomials infinitely many times differentiable?
- $A/ I \otimes_A A/J \cong A/(I+J)$
- Prove that $\lim_{x\rightarrow 1}{\frac{x^n-1}{x-1}}=n$ for all integer n without L'Hôpital
- Strictly increasing, absolutely continuous function with vanishing derivative