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.

*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

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?

## 1 comment:

No problem, glad to be of help!

Post a Comment