Home > Just Math
A small difference (Posted on 20110207) 

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(P0P1)=1.
When is P0P1 positive?
Solution

Comment 2 of 2 

Let P0_{n} be the number of derangements of n elements and P1_{n} be the number of
permutations in which one element has remained in its original position.
A derangement of [a(1),a(2),......,a(n)] can have in its first position any of the
n1 elements a(2),...,a(n). Suppose that its first element is a(k). Now, a(1) will
appear either in the kth position or elsewhere.
If a(1) appears in position k
then the remaining n2 elements a(2),a(3),...a(k1),a(k+1),...,a(n) must be
deranged in positions 2,3,.....(k1),(k+1),...,n which can be done in P0_{n2} ways.
Otherwise, the remaining n1 elements a(1),a(2),....a(k1),a(k+1),...,a(n) must
be arranged in positions 2,3,....,n in such a way that none of them
remains in its original position and a(1) is not in position k. This is equivalent to
deranging [a(2),a(3),.....a(k1),a(1),a(k+1),.....a(n)] since such a derangement
ensures that a(1) will not be in the kth position, and can be done in P0_{n1} ways.
It follows that P0_{n} = (n  1)(P0_{n2} + P0_{n1}), and this can be rewritten as
P0_{n}  nP0_{n1} = (P0_{n1}  [n  1]P0_{n2}). (1)
As Charlie observed, P1_{n} = nP0_{n1} since 1 element in its original position leaves
n  1 elements to be deranged. So (1) can be rewritten and extended by
induction to give: P0_{n}  P1_{n} = (P0_{n1}  P1_{n1}) = ...........= (1)^{n1}(P0_{1}  P1_{1}).
Since P0_{1} = 0 and P1_{1} = 1, it follows that P0_{n}  P1_{n} = (1)^{n}
Thus, P0_{n}  P1_{n} = 1 and P0_{n}  P1_{n} is positive when n is even

Posted by Harry
on 20110209 21:56:33 


Please log in:
Forums (0)
Newest Problems
Random Problem
FAQ 
About This Site
Site Statistics
New Comments (5)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On
Chatterbox:
