# Find the probability that no kid will have his own pair of shoes

In the morning, $n$ children come to the kindergarten and leave their shoes in the locker room. Leaving the kindergarten one by one, each child takes one left and one right shoe, accidentally equiprobably choosing them from among the remaining ones. Find the likelihood that none of the children will leave in their own pair of shoes.

My thoughts: I assume that decisions are independent based on accidentally equiprobably choosing them from among the remaining ones part. Let $I_l$ and $I_r$ be indicator r.v. for choosing his/her left shoe. Let $A$ be the probability that none of the children will leave in their own pair of shoes

$$P(I_l=1)=\frac1n; P(I_r=1)=\frac1n$$

Leaving without his/her pair of shoes can occur in several ways:

$1$) Choose his/her left shoe and other (not his/her) right shoe $$P(I_l=1)P(I_r=0)=\left(\frac1n\right)^n\left(1-\frac1n\right)^n$$

$2$) Choose his/her right shoe and other (not his/her) left shoe $$P(I_r=1)P(I_l=0)=\left(\frac1n\right)^n\left(1-\frac1n\right)^n$$

$3$) Nobody chose his/her pair of shoes $$P(I_l=0)P(I_r=0)=\left(1-\frac1n\right)^n\left(1-\frac1n\right)^n$$

Therefore, $$P(A)=2\left(\frac1n\right)^n\left(1-\frac1n\right)^n+\left(1-\frac1n\right)^{2n}$$

Here I assume that kids can distinguish between right and left shoes.

If they can not: probability of choosing left shoe out of $2n$ shoes:

$$P(\text{left})=\frac{n}{\binom{2n}{2}}$$ by symmetry the same for $P(\text{right})$

$1$) Chose two left shoes included his/her: $$(P(\text{left})P(\text{left}))^n=\left(\frac{n}{\binom{2n}{2}}\cdot\frac{n-1}{\binom{2n-1}{2}}\right)^n$$ Power $n$, because there are $n$ people who make this decisions

$2$) Chose two right shoes included his/her: $$(P(\text{right})P(\text{right}))^n=\left(\frac{n}{\binom{2n}{2}}\cdot\frac{n-1}{\binom{2n-1}{2}}\right)^n$$

$3$) Choose one left included his/her and one right excluded his/her own: $$P(\text{left})P(\text{right})=\left(\frac{n}{\binom{2n}{2}}\cdot\frac{n-1}{\binom{2n-1}{2}}\right)^n$$

$4$) Choose one right inlcuded his her and one left excluded his/her own $$P(\text{right})P(\text{left})=\left(\frac{n}{\binom{2n}{2}}\cdot\frac{n-1}{\binom{2n-1}{2}}\right)^n$$

• The probability that a particular child leaves with the correct shoes is $\frac 1{n^2},$ so the expected number of children leaving with correct shoes is $\frac 1n$ by the linearity of expectation. The chance that nobody leaves with the correct shoes is at least $\frac {n-1}n$, which assumes that you never have more than one child with correct shoes. The chance is somewhat higher than this. The problem does say they each take one left and one right shoe. Dec 9 '17 at 15:33

Using inclusion-exclusion in its basic form we immediately obtain for the probability that it is

$$\frac{1}{n!^2} \sum_{q=0}^n {n\choose q} (-1)^q (n-q)!^2.$$

We can use this closed form to gather more information from the OEIS, where we find it is listed as OEIS A089041, i.e.

$$0, 3, 26, 453, 11844, 439975, 22056222, \\ 1436236809, 117923229512, \ldots$$

In particular consulting the asymptotics we find in the OEIS entry

$$\frac{1}{n!^2} 2\pi e^{-2n} n^{2n+1}.$$

Combining this with Stirling we get

$$\left(\frac{1}{\sqrt{2\pi n}} \frac{e^n}{n^n}\right)^2 2\pi e^{-2n} n^{2n+1} \sim 1.$$

This means for $n$ large we can be almost certain that no one leaves with their own pair of shoes.

Clarification of the problem definition that was used, by Maple code.

with(combinat);

ENUM :=
proc(n)
option remember;
local lperm, rperm, res, pos;

res := 0;

lperm := firstperm(n);

while type(lperm, list) do
rperm := firstperm(n);

while type(rperm, list) do

for pos to n do
if lperm[pos] = pos and
rperm[pos] = pos then
break;
fi;
od;

if pos = n+1 then
res := res + 1;
fi;

rperm := nextperm(rperm);
od;

lperm := nextperm(lperm);
od;

res/n!^2;
end;

EX := n -> add(binomial(n,q)*(-1)^q*(n-q)!^2, q=0..n)/n!^2;


Remark. Apparently the asymptotics here follow by inspection, i.e. by writing the probability as

$$\frac{1}{n!} \sum_{q=0}^n \frac{1}{q!} (-1)^q (n-q)! \\ = 1 - \frac{1}{n} + \frac{1}{2}\frac{1}{n(n-1)} - \frac{1}{6} \frac{1}{n(n-1)(n-2)} + \cdots \pm \frac{1}{n!}$$

which is seen not to leave the interval $(1-1/n, 1)$ after the second term and hence produces a probability of one for $n$ large. (These alternating terms are strictly decreasing in absolute value.)