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

Home > Just Math
A small difference (Posted on 2011-02-07) Difficulty: 3 of 5
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.)
Some Thoughts 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  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

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information