I take Nicole's comment to mean she gives up, although Nicole, it turns out that your comment has a deep relation to this problem and raises a new question.
To find out on average how many items are left unmoved by a random permutation, you can consider every permutation and how many are left unmoved by each, add them all up and divide by the total number of permutations. To avoid mathsy notations I'm going to write a tiny program that calculates this total.
total = 0
# Check what every permutation does to every item, if it leaves it
# in the same place then increase the total by 1
for p in perms:
for i in 1..N:
if p(i) == i:
total = total + 1
Now, here's the key to this problem - swap the loops. The final answer stays the same we just end up adding things up in a different order.
total = 0
# Check what every permutation does to every item, if it leaves it
# in the same place then increase the total by 1
for i in 1..N:
for p in perms:
if p(i) == i:
total = total + 1
So now what we're doing is looping over the items and counting how many permutations leave that item in place and that's something we
can work out. The number of permutations that fix a given item is (N-1)! (where ! is factorial) because when you fix 1 item, you're left with N-1 other items which you move around however you like so it's just the number of permutations of N-1 items which is (N-1)!. So now the code can be just
total = 0
# Check what every permutation does to every item, if it leaves it
# in the same place then increase the total by 1
for i in 1..N:
total = total + (N-1)!
which is just adding (N-1)! N times. That's N x (N-1)! which is just N!. Now we have to divide that by the total number of permutations which is also N! to get an average of 1.
You can also get to this answer by drawing a grid with all the permutations across the top and all the items down the side. You put a tick in a cell in the grid if the permutation on the top leaves the item on the left unmoved. Now count the ticks. Doing it column by column is hard but doing it row by row is easy because there will be (N-1)! ticks in each row.
So the conclusion is that if you do a perfect shuffle of a deck of cards, on average 1 card will end up in the same places as before.
So where does Nicole's comment come in? I knew it was Ralph Wiggum who said it but I couldn't remember the context turns out. I found it here. It's
Lisa: Hey Ralph, want to come with me and Alison to play "Anagrams"?
Alison: We take proper names and rearrange the letters to form a
description of that person.
Ralph: My cat's breath smells like cat food.
and what we've just shown is that given a random anagram, you'd expect 1 letter on average to end up in the same place - well kind of, that's only true if there are no repeated letters. I hadn't thought of this in terms of anagrams before and that adds a nice twist in terms of repeated letters. Thanks Nicole!
So the new puzzle is - given a string written in scrabble tiles (it can have repeated letters), if you mess up the tiles and make a new string at random, how many letters do you expect to be in the same place as before?
