eklhad@ihnet.UUCP (K. A. Dahlke) (02/17/85)
< 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
nachum@uiucdcs.UUCP (02/19/85)
Such permutations are called "derangements".
The number of derangements of n items is
k
n (-1) -1
n! sum ----- = round(n! e )
k=0 k!
The problem is solved, for example, in Knuth vol. 1 p. 177ff.gjerawlins@watdaisy.UUCP (Gregory J.E. Rawlins) (02/20/85)
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
gwyn@brl-tgr.ARPA (Doug Gwyn <gwyn>) (02/21/85)
> How many permutations of the digits 0-9 have no digits in common
This should be easy: How many unrestricted permutations are there?
How many permutations 0xxxxxxxxx are there? x1xxxxxxxx? etc.
Subtract the latter 10 quantities from the first. Voila!hopp@nbs-amrf.UUCP (Ted Hopp) (02/23/85)
> > How many permutations of the digits 0-9 have no digits in common > This should be easy: How many unrestricted permutations are there? > How many permutations 0xxxxxxxxx are there? x1xxxxxxxx? etc. > Subtract the latter 10 quantities from the first. Voila! Not quite. You then have to add back all the permutations 01xxxxxxxx, 0x2xxxxxxx, etc. that you counted twice. Then you have to subtract back the permutations 012xxxxxxx, 01x3xxxxxx, etc. that you added in twice. Then you have to .... -- Ted Hopp {seismo,umcp-cs}!nbs-amrf!hopp
gwyn@brl-tgr.ARPA (Doug Gwyn <gwyn>) (02/23/85)
> > This should be easy: How many unrestricted permutations are there? > > How many permutations 0xxxxxxxxx are there? x1xxxxxxxx? etc. > > Subtract the latter 10 quantities from the first. Voila! Sorry, I did indeed blunder with this one. Please ignore the above.
ndiamond@watdaisy.UUCP (Norman Diamond) (02/24/85)
> > How many permutations of the digits 0-9 have no digits in common > > This should be easy: How many unrestricted permutations are there? > How many permutations 0xxxxxxxxx are there? x1xxxxxxxx? etc. > Subtract the latter 10 quantities from the first. Voila! Sure; we subtract the permutation 0123456789 ten times; we subtract 0123456798 only eight times; etc. Voila, an incorrect answer! -- Norman Diamond UUCP: {decvax|utzoo|ihnp4|allegra}!watmath!watdaisy!ndiamond CSNET: ndiamond%watdaisy@waterloo.csnet ARPA: ndiamond%watdaisy%waterloo.csnet@csnet-relay.arpa "Opinions are those of the keyboard, and do not reflect on me or higher-ups."