— — Vánoční besídka (šatnářka)

Vánoční besídka (šatnářka)

n dárců dostane nazpět n dárků. Každá z n! možností je stejně pravděpodobná. Jaká je pravděpodobnost, že nikdo nedostane zpátky svůj dárek?

Matematická formulace

Hledáme \frac{š(n)}{n!} , š(n) = počet permutací π množiny \{1, …, n\} bez pevného bodu. Pevný bod: i je pevný bod, pokud π(i) = i.

VĚTA (Šatnářka):

š(n) = n! (1 − \frac{1}{1!} + \frac{1}{2!} − \frac{1}{3!} + ⋯ + (−1)^{n} \frac{1}{n!})

Příklad:

š(1) = 1! (1 − \frac{1}{1!}) = 0

š(2) = 2! (1 − \frac{1}{1!} + \frac{1}{2!}) = 1

š(3) = 3! (1 − \frac{1}{1!} + \frac{1}{2!} − \frac{1}{3!}) = 2

DŮKAZ:

S_{n} = množina všech permutací {1, …, n}
A_{i} = {π ∈ S_{n}, i = 1, …, n : π(i) = i}

|A_{i}| = (n − 1)! (Prvek i stojí, ostatní se propermutují.)

Pro I = {i_{1}, …, i_{k}} ⊆ {1, …, n} platí:

\underbrace{⋂_{i∈I} A_{i}}_{A_{i_{1}} ∩···∩A_{i_{k}}} = množina vsech permutací π

množiny {1, …, n} takových, že π(i_{1}) = i_{1}, …, π(i_{k}) = i_{k}.

| ⋂_{i∈I} A_{i}| = (n − k)! (t prvků stojí, ostatní se propermutují.)

š(n) = |S_{n}| − | ⋃_{i=1}^{n} A_{i}| =

= n! − ∑_{k=1}^{n}(−1)^{k−1} · ∑_{I∈\binom{\{1,...,n\}}{k}} \underbrace{| ⋂_{i∈I} A_{i}|}_{(n−k)!}

= n! − ∑_{k=1}^{n}(−1)^{k−1} · \underbrace{\binom{n}{k}(n − k)!}_{\frac{n!}{k!}}

= n! · (1 − ∑_{k=1}^{n} \frac{(−1)^{k−1}}{k!} )

— — Vánoční besídka (šatnářka)

Q.E.D. Tedy pravděpodobnost, že nikdo nedostane zpět svůj dárek, je:

\frac{š(n)}{n!} = 1 − \frac{1}{1!} + \frac{1}{2!} − ⋯ ± \frac{1}{n!} → \frac{1}{e} ≈ 0.36787 …