Date: Thu, 8 Jan 2004 15:51:23 -0500 (EST)
From: Dan Hoey <Hoey@aic.nrl.navy.mil>
To: Eugene Salamin <gene_salamin@yahoo.com>
Subject: Re: [math-fun] Secret Santa problem
cc: math-fun <math-fun@mailman.xmission.com>

Eugene Salamin <gene_salamin@yahoo.com> wrote:

> Here is one way to generate derangements with equal probability.  Place
> numbers 2 to n in a hat.  Draw a number; it becomes p(1).  Put 1 into
> the hat and withdraw 2 if it is not p(1).  Draw a number; it becomes
> p(2).  Replace 2 if it is not p(1), and withdraw 3 if it is not p(1) or
> p(2).  Draw a number; it becomes p(3).  And so on.

I think you can derange  1,...,n-1  and have nothing to pick for p(n).

Dan