Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site watdaisy.UUCP
Path: utzoo!watmath!watdaisy!gjerawlins
From: gjerawlins@watdaisy.UUCP (Gregory J.E. Rawlins)
Newsgroups: net.math
Subject: Re: permuting 0123456789
Message-ID: <6987@watdaisy.UUCP>
Date: Tue, 19-Feb-85 21:04:30 EST
Article-I.D.: watdaisy.6987
Posted: Tue Feb 19 21:04:30 1985
Date-Received: Thu, 21-Feb-85 07:41:32 EST
References: <201@ihnet.UUCP>
Reply-To: gjerawlins@watdaisy.UUCP (Gregory J.E. Rawlins)
Distribution: net
Organization: U of Waterloo, Ontario
Lines: 39
Summary: 

In article <201@ihnet.UUCP> eklhad@ihnet.UUCP (K. A. Dahlke) writes:
>< 3792156048 >
>
>A problem in combinatorics.
>	How many permutations of the digits 0-9 have no digits in common
>with the identity permutation (0123456789)?
>Examples:   2317495680 cannot be counted, since 4 and 8 are in the correct
>position.  9876543210 is included, since no digit is in the correct position.
>I have derived a recursive formula, but I really wanted the answer
>(f(n)) in closed form.  Any ideas?
>-- 
>	Having, is not so pleasing a thing after all, as wanting.
>	It is not logical, but it is often true.
>Karl Dahlke    ihnp4!ihnet!eklhad


	This is just the number of derangements of n things. A
*derangement* of the integers 0,1,..,n is a permutation p0,p1,..,pn,
such that p0<>0,p1<>1,...pn<>n. The number of derangements of n
things Dn = n!(sum i from 0 to n of (-1)**i * (1/i!) ).
	So D1 = 0, D2 = 1, D3 = 2, D4 = 9 etc. The value you want is
D10.
	There are several recurrences for Dn, the simplest being
		Dn = nD(n-1) + (-1)**n for n>=2
	As a result of this recurrence the number of derangements are
sometimes call the "subfactorials" or recontres numbers.
	Using the recurrence (or the formula :-) we get D10=1334961.
	As a side note, note that Dn/n! approaches 1/e as n->inf, as
i recall the convergence is quite rapid and for n> ~mumble~
where ~mumble~ is quite small (around 10?) Dn is basically
n!/e.
		greg


-- 
Gregory Rawlins CS Dept.,U.Waterloo,Waterloo,Ont.N2L3G1 (519)884-3852
gjerawlins%watdaisy@waterloo.csnet                              CSNET
gjerawlins%watdaisy%waterloo.csnet@csnet-relay.arpa              ARPA
{allegra|clyde|linus|inhp4|decvax}!watmath!watdaisy!gjerawlins   UUCP