Probability and Card Shuffling

Date: Thu, 3 Nov 1994 12:30:41 +0100
From: Henrik Johansson
Subject: Probability question

Intro: if I have n shuffled cards, numbered from 0 to n-1, the
probability that no card will have the same number on it as its
position in the deck is not very hard to figure out...

Problem: If I have n shuffled cards in k colours numbered from 0 to
(n/k)-1, what is the probability that no card will have the same
number on it as its position in the deck modulo n/k?

Standard example: n = 52, k = 4, cards numbered from 0 to 12.  A card
with number 3 mustn't be on positions 3, 16, 29, or 42.

I stumbled onto this problem a few years ago but haven't managed to
solve it.  Neither has any of my teachers.  A simulation gave that
about one shuffle out of 64 (if I remember correctly) was successful.

/hj

Date: Thu, 3 Nov 1994 08:51:31 +0900
X-Sender: mpatter1@cc.swarthmore.edu

Hi Henrik-

        Thanks for writing to us.  I played with this problem for a little
while, but I didn't get very far.  One way to look at it is to split up the
shuffled deck into n/k piles. This makes the problem look a little more
like the "Intro" problem that you gave - remember - the intro problem 
is just the same as the harder one when k=1.

        There are more doctors coming on call all day.  Maybe one of 
them can help.

Thanks again for writing to us,
Margaret  M.D. on call