I came across an interesting application of permutations during Secret Santa with my blocking group and some friends a couple weeks ago. In Secret Santa, you are assigned another member of your group whom you must secretly buy a gift for. After all the gifts have been bought and put under the tree, a person is randomly drawn and must pick up the gift with his/her name on it. After the person unwraps the gift, he/she must guess who bought the gift. Once the buyer is revealed, he/she goes next and picks up the gift with his/her name on it. The game goes on until all the gifts under the tree are gone. This year’s Secret Santa was especially interesting. The game was going on normally until the 5th individual guessed who had bought her gift. It happened to be the 1st person to pick a gift and the cycle was completed. A new one had to be started in order for the game to continue. This got me thinking immediately about permutations of thirteen elements and the game of Secret Santa. When all the gifts had been picked, the gift selecting cycle had a structure identical to this permutation…
(assuming you assign ever person a number)
(9 4 6 7 13)(2 12 3 5 11 1 10 8) A permutation with 1 cycle of 5 and 1 cycle of 8
The previous year, we had a Secret Santa with the same group and the gift cycle structure had the same structure as this permutation
( 1 7 13 4 2 11 9 12 3 8 5 10 6)
One full cycle of 13 is rare among all the cycle structures possible with the 13! possible permutations. I think we were pretty lucky.
Anyway, thought this was interesting. Happy Holidays.
I was reading your blogs with interest and came across this Secret Santa permutation question. At first I thought that, yes a full cycle was rare. Then I started quantifying it.
For n people, there are n! permuations of slips of names they can get (allowing for the sad scenario of people getting presents for themselves).
How many of these are complete cycles? WLOG assume the first number in the cyclic permutation is 1. Then we are left with n-1 remaining numbers in any order. So there are (n-1)! possible full-cycle permutations. Hence 1/n of the possible secret santa permutations is a full cycle. More if self-presenting is ruled out! I was surprised at how often these full cycles arose. I even hand worked a few examples to convince myslef I hadn’t made a silly mistake.
Thanks for a thought provoking few minutes! Now to ponder the number of ways of getting various cycle-combinations…
By: Richard on February 23, 2009
at 10:47 am