Name Drawing Puzzle

Question

There is a party with 20 people, and everyone writes their name down on a piece of paper and puts it into a bag. The bag is mixed up, and each person draws one piece of paper. If you draw the name of someone else, you are considered to be in his "group". What is the expected number of groups after everyone draws?

So basically if we have a loop where each person draws someone else's name, and the last person draws the first person in that list's name, we have a group. Not quite sure how to approach this problem.

Thanks for any help.

Answer 1

What you’re asking for is the average number of cycles in a random permutation of $[n]$ in the case $n=20$. (Here $[n]=\{1,\dots,n\}$.)

Let $h(n)$ be the average number of cycles in a random permutation of $[n]$; I claim that $h$ satisfies the recurrence $$h(n)=\frac{n-1}nh(n-1)+\frac1n\Big(h(n-1)+1\Big)\;.\tag{1}$$

Proof: Let $\pi$ be any permutation of $\{2,3,\dots,n\}$ written in cycle form. Say that the entries in $\pi$ from left to right, ignoring parentheses, are $\pi_1,\dots,\pi_{n-1}$. Now insert $1$ into $\pi$ in one of the following two ways.

1. To the left of $\pi_1$ as $(1)$, forming a cycle of its own.
2. Immediately after one of the $\pi_k$, $k=1,\dots,n-1$, in the same cycle as $\pi_k$.

Every permutation of $[n]$ can be uniquely obtained in this way from a unique permutation $\pi$ of $\{2,\dots,n\}$.

The average number of cycles of a random permutation of $\{2,\dots,n\}$ is of course $h(n-1)$. The recurrence $(1)$ is now an immediate consequence of the fact that operation (1) above increases the number of cycles by $1$ and accounts for $\frac1n$ of all cases, while operation (2) leaves the number of cycles unchanged and accounts for the remaining $\frac{n-1}n$ cases. $\dashv$

Now rewrite $(1)$ as $$h(n)=h(n-1)+\frac1n$$ and note that $h(1)=1$. Then $h(2)=1+\frac12$, $h(3)=h(2)+\frac13=1+\frac12+\frac13$, and an easy induction verifies that in general $$h(n)=H_n=\sum_{k=1}^n\frac1k\;,$$ the $n$-th harmonic number. It is known that $$H_n=\ln n+\gamma+\epsilon_n\;,$$ where $\gamma\approx 0.5772$ is the Euler-Mascheroni constant and $\epsilon_n\sim\frac1{2n}$.

Added: $H_{20}=\dfrac{55835135}{15519504}\approx 3.59774$. The numerator is taken from A001008 at OEIS and the denominator from A002805.

Answer 2

You're asking for the expected number of cycles in a random permutation with uniform distribution over the symmetric group $S_n$ (with $n=20$). To calculate this, we can calculate the expected number of cycles a single element represents, and multiply by the number $n$ of elements. To find the number of permutations in which element $a$ is in a cycle of length $k$, imagine the $n$ elements in a row, with $a$ at the front, and a separator after the first $k$ elements. If we fill the rest of the row with any of the $(n-1)!$ permutations of the remaining $n-1$ elements, we can regard the resulting row as representing a permutation in which the first $k$ elements form a cycle containing $a$, and the remaining $n-k$ elements stand for a permutation of those elements. This establishes a bijection between the $(n-1)!$ ways of filling the row and the permutations in which $a$ is in a cycle of length $k$. Thus, for every $k$ between $1$ and $n$, there are $(n-1)!$ permutations in which $a$ is in a cycle of length $k$. Being in a cycle of length $k$, the element $a$ contributes $1/k$ cycles to the total number of cycles. Thus, since each permutation has probability $1/n!$ of occurring, the expected number of cycles is

$$n\sum_{k=1}^n(n-1)!\frac1k\frac1{n!}=\sum_{k=1}^n\frac1k=H_n\;,$$

the $n$-th harmonic number.