All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 A small difference (Posted on 2011-02-07)
Given a set a(1), a(2), a(3)...a(n), n>1.
Let P0 be the number of permutations of n elements, in which no element a(i) is in place i.

Let P1 be the number of permutations of n elements, in which exactly one element is in its original place i.

Show that ABS(P0-P1)=1.

When is P0-P1 positive?

 No Solution Yet Submitted by Ady TZIDON No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 Exploration--no proof | Comment 1 of 2

The number of derangements (permutations where no element is in its original place) is given by Sloane's OEIS in A000166, where a formula is given: a(n)=[(n!+1)/e] for n>0. This represents the P0 of the puzzle.

The number of permutations with one element left in place is n times the number of ways of deranging n-1 elements, as there are n possible elements to be the one to be kept in place.  This is the P1 of the puzzle.

5   point 22
10   for N=1 to 24
20    Derang=int(!(N)/#e+0.5)
30    print N,Derang;Prev*N;Derang-Prev*N
40    Prev=Derang
50   next

produces the following table, which lists n, P0, P1 and P0-P1:

`1       0  0  02       1  0  13       2  3 -14       9  8  15       44  45 -16       265  264  17       1854  1855 -18       14833  14832  19       133496  133497 -110      1334961  1334960  111      14684570  14684571 -112      176214841  176214840  113      2290792932  2290792933 -114      32071101049  32071101048  115      481066515734  481066515735 -116      7697064251745  7697064251744  117      130850092279664  130850092279665 -118      2355301661033953  2355301661033952  119      44750731559645106  44750731559645107 -120      895014631192902121  895014631192902120  121      18795307255050944540  18795307255050944541 -122      413496759611120779881  413496759611120779880  123      9510425471055777937262  9510425471055777937263 -124      228250211305338670494289  228250211305338670494288  1`

The puzzle asks only for the difference given to hold for n > 1, which it does on the above table. It would, however, hold also for n = 1 if the value for the previous number, 0, were taken as 1, as it appears on Sloane's list of the sequence.

This is of course no general proof.  That might come from some analysis of the recursive formulae given in Sloane's OEIS.

Edited on February 7, 2011, 2:44 pm
 Posted by Charlie on 2011-02-07 14:35:47

 Search: Search body:
Forums (0)