An exchange gift breakdown

I don't know how to answer the following, so here goes.

10 people decide to exchange gifts, in the following manner:

All 10 people write down their names on pieces of paper, and along with their names go their gift preferences.

They put the names in a box and then each person randomly picks out a name from the box.

They then give their gifts to the person whose name they drew from the box. If a person draws his own name, then he gives his gift to himself.

Now, if Anne gives his gift to Bob, and Bob gives his gift to Charles, and Charles gives his gift to Anne, then Anne, Bob and Charles are said to be in a chain, with 3 members.

Now for the million-dollar question:

What is the expected length of the longest chain in the group?

#Combinatorics

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

I don't know how much you know about permutations, so I'll start from the basics. Consider the following permutation $\pi$ on the set $\{1, 2, 3, \dots, 10\}$ : $\begin{aligned} \pi(1) &= 9, \\ \pi(2) &= 10, \\ \pi(3) &= 8, \\ \pi(4) &= 6, \\ \pi(5) &= 4, \\ \pi(6) &= 1, \\ \pi(7) &= 7, \\ \pi(8) &= 3, \\ \pi(9) &= 5, \\ \pi(10) &= 2. \end{aligned}$ (This is just like assigning names to people, except we're using numbers. In other words, imagine we assign a number from 1 to 10 to everyone.) One way to work with a permutation is to write down its cycles. So for the permutations above, $\pi$ takes 1 to 9, 9 to 5, 5 to 4, 4 to 6, then 6 back to 1. Similarly, it takes 2 to 10 and 10 to 2, 3 to 8 and 8 to 3, and 7 to itself. So we can write down the cycles of the permutation $\pi$ this way: $(1, 9, 5, 4, 6) (2, 10) (3, 8) (7).$ This representation is known as the cycle decomposition of a permutation. Your question is to determine the expected length of the longest cycle in a random permutation.

To do so, we can list all the cycle types, and how many permutations there are of each type. The cycle type refers to the length of the cycles in the permutation. For the example above, the cycle type is 1, 2, 2, 5, because there is one cycle of length 1, two cycles of length 2, and one cycle of length 5.

This is what the table would look like for permutations on the set $\{1, 2, 3, 4, 5\}$ : $\begin{array}{cc} \text{Cycle Type} & \text{Number of Permutations} \\ \hline 1, 1, 1, 1, 1 & 1 \\ 1, 1, 1, 2 & 10 \\ 1, 1, 3 & 20 \\ 1, 2, 2 & 15 \\ 1, 4 & 30 \\ 2, 3 & 20 \\ 5 & 24 \end{array}$

So for 5 people, the expected length of the longest cycle is $\frac{1 \cdot 1 + 10 \cdot 2 + 20 \cdot 3 + 15 \cdot 2 + 30 \cdot 4 + 20 \cdot 3 + 24 \cdot 5}{120} = \frac{137}{40}.$ Everything would be done similarly for 10 people; once you determine the numbers in the table, the rest is a routine calculation.

Having said all this, I doubt there is any nice, general formula for your problem, i.e. one that would generalize to $n$ people. You could consider the expected number of cycles in a random permutation; it turns out that this question has a relatively nice answer.

Jon Haussmann - 4 years, 6 months ago

Oh, thanks, I understood everything you said :D

But what about the expected number of cycles? Can you please give a hint? O.o

Manuel Kahayon - 4 years, 6 months ago

Oh, wait, I'm getting a nice formula...

Manuel Kahayon - 4 years, 6 months ago

$\large E(x) = \frac{\displaystyle \sum_{i=1}^{x-1} E(i) + x}{x}$ ?

Manuel Kahayon - 4 years, 6 months ago

I got that by considering the cycle which person 1 is in. AMAZING! It's $1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{x}$ :D

Manuel Kahayon - 4 years, 6 months ago

Well done!

Here is a simple counting proof. Let $n$ be the number of people, and let $1 \le k \le n$ . We count the number of $k$ -cycles (cycles of length $k$ ) among all $n!$ permutations.

First, we determine the number of different possible $k$ -cycles. There are $\binom{n}{k}$ ways to choose the $k$ numbers to go into the $k$ -cycle, then $(k - 1)!$ ways to arrange them to form a $k$ -cycle. This gives $\binom{n}{k} (k - 1)!$ possible $k$ -cycles.

Now, each particular $k$ -cycle appears in $(n - k)!$ different permutations (because there are $n - k$ elements remaining), so the expected number of $k$ -cycles is $\frac{\binom{n}{k} (k - 1)! (n - k)!}{n!} = \frac{1}{k}.$

Finally, summing over $1 \le k \le n$ , we find that the expected number of cycles is $1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}.$

Jon Haussmann - 4 years, 5 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$