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?
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 0
2 1 0 1
3 2 3 -1
4 9 8 1
5 44 45 -1
6 265 264 1
7 1854 1855 -1
8 14833 14832 1
9 133496 133497 -1
10 1334961 1334960 1
11 14684570 14684571 -1
12 176214841 176214840 1
13 2290792932 2290792933 -1
14 32071101049 32071101048 1
15 481066515734 481066515735 -1
16 7697064251745 7697064251744 1
17 130850092279664 130850092279665 -1
18 2355301661033953 2355301661033952 1
19 44750731559645106 44750731559645107 -1
20 895014631192902121 895014631192902120 1
21 18795307255050944540 18795307255050944541 -1
22 413496759611120779881 413496759611120779880 1
23 9510425471055777937262 9510425471055777937263 -1
24 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 |
Exploration--no proof
