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.

Answer 3

Brian Scott and joriki have already answered this comprehensively, so the purpose of this answer is to provide a direct counting perspective that lays bare some of the interesting connections between the harmonic number $H_{n}$ and a certain Stirling number of the first kind.

Let $X$ be the discrete random variable representing the number of cycles in a random permutation of $[n].$ Then $X \in \{1, 2, \ldots , n\}$ and $P[X =i] = \dfrac{c(n, i)}{n!}$, where $c(n, i)$ denotes the (unsigned) Stirling number of the first kind which counts the number of permutations on $[n]$ with exactly $i$ disjoint cycles.

Then $E[X] = \displaystyle\sum_{i=1}^{n}iP[X=i]= \dfrac{1}{n!}\displaystyle\sum_{i=1}^{n}i \,c(n, i)$

It so happens that the sum $\begin{equation}\displaystyle\sum_{i=1}^{n}i \,c(n, i) = c(n+1, 2) \tag{*}\label{*}\end{equation}$ by the following double-counting argument: the RHS by definition, counts the number of permutations on $[n+1]$ having $2$ cycles. (We can freely require that $n+1$ be written as the first element of the cycle.) But we can also count the elements of this set via the LHS too. Begin with a permutation on $[n]$ with $i$ cycles (written in cycle form) where $1\leq i \leq n.$ There is a choice of $i$ cycles for $n+1$ to join (and be the first element of) and define one cycle. Deleting all the internal brackets of the remaining cycles we obtain the other cycle. Summing over all possible numbers of cycles for a permutation on $[n]$ to have, we get the above identity.

So $E[X] = \dfrac{c(n+1, 2)}{n!} = H_{n}$, where the latter equality holds by yet another interpretation of $c(n+1, 2):$ Consider a permutation on $[n+1]$ with $2$ cycles and $n+1$ is the first element in a cycle of length $i$ where $1\leq i \leq n.$ Choose the $i-1$ elements to fill out that cycle in $\binom{n}{i-1}$ and arrange them in $(i-1)!$ ways and place the remaining $n-i+1$ elements in a cycle in $(n-i)!$ ways. Putting this together and summing over all possible lengths of the first cycle we get: $c(n+1, 2)=\displaystyle \sum_{i=1}^{n}\binom{n}{i-1}(i-1)!(n-i)! = \displaystyle n!\sum_{i=1}^{n}\dfrac{1}{n-i+1} = n! H_{n}$ after re-indexing, thereby completing the proof.

It's worth noting that equation $\eqref{*}$ is a special case corresponding to $k=1$ in the following identity: $$\displaystyle \sum_{i=k}^{n}\binom{i}{k}c(n, i) = c(n+1, k+1).$$

This can be proven by a similar double-counting argument.

Final remark: One advantage of using an approach like this is that we can get higher moments of $X$ without too much additional work, if $c(n, i)$ is known for small $i.$