Intereting Posts

$f$ is integrable, prove $F(x) = \int_{-\infty}^x f(t) dt$ is uniformly continuous.
Why does $L^2$ convergence not imply almost sure convergence
Logic/Reasoning
On an $h \times h$ square lattice, count all the paths from $(0,a)$ to $(h-1,b)$, $a,b \in $, with diagonal moves allowed
$a+b\sqrt{-3}$ and $a-b\sqrt{-3}$ are coprime in $\mathbb{Z}+ \omega \mathbb{Z}$
“De-localization” of a Noetherian module?
How come the number $N!$ can terminate in exactly $1,2,3,4,$ or $6$ zeroes but never $5$ zeroes?
Help finding a combinatorial proof of $k {n \choose k } = n {n – 1 \choose k -1}$
Correct calculation of recursive limit
If the size of 2 subgroups of G are coprime then why is their intersection is trivial?
How to find the determinant of this matrix?
How does one prove that if function's partial derivative respect to every variable is zero, function is constant?
Find a basis given a vector space
Image of the union and intersection of sets.
Rounding Percentages

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?

- Show that a connected graph on $n$ vertices is a tree if and only if it has $n-1$ edges.
- How find this $a_{1}+a_{2}+\cdots+a_{500}=b_{1}+b_{2}+\cdots+b_{500}$?
- How many different numbers can you make with the following digits?
- Gardner riddle on mathemagicians
- Proof/derivation of $\lim\limits_{n\to\infty}{\frac1{2^n}\sum\limits_{k=0}^n\binom{n}{k}\frac{an+bk}{cn+dk}}\stackrel?=\frac{2a+b}{2c+d}$?
- upper bounding alternating binomial sums

- Combinatorial interpretation of Binomial Inversion
- Maximum Likelihood Estimator of parameters of multinomial distribution
- Probability density function of a quotient of two normal random variables
- How is Leibniz's rule for the derivative of a product related to the binomial formula?
- How can I get f(x) from its Maclaurin series?
- {Thinking}: Why equivalent percentage increase of A and decrease of B is not the same end result?
- Amalgamation of graphs
- probabilistically what can we say about the next throw of a coin after n throws
- Difference and relation between dependency graph and graphical model?
- Partition problem for consecutive $k$th powers with equal sums (another family)

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.

- Is there a sequence such that $\sum{a_n}$ diverges but $\sum{na_n}$converges?
- Recurrence for the partition numbers
- Limit approach to finding $1+2+3+4+\ldots$
- Determing the number of possible March Madness brackets
- Strategies to denest nested radicals.
- How to prove that the center of a group is not a maximal subgroup?
- Suppose $\lim \sup_{n \to \infty}a_n \le \rho$. Show $\lim \sup_{n \to \infty} a_n^{{(n-m)}/{n}} \le \rho$.
- Can I prove (if $n^2$ is even then $n$ is even) directly?
- Contraction of non-zero prime ideals in the ring of algebraic integers
- $GL(n,K)$ is open in $M(n,K)$
- Trig sum: $\tan ^21^\circ+\tan ^22^\circ+…+\tan^2 89^\circ = ?$
- Solving a differential equation related to the deformation of a space curve.
- ∅ ⊆ { ∅ } Is this true or false?
- Fields finitely generated as $\mathbb Z$-algebras are finite?
- Number of digits from $1$ to $n$