0

Guest

Courses New

proof of dearrangement formula.[n!(1-1/1!+1/2!-1/3!+............+(-1)^n*1/n!]

proof of dearrangement formula.[n!(1-1/1!+1/2!-1/3!+............+(-1)^n*1/n!]

Grade:

1 Answers

SHAIK AASIF AHAMED
askIITians Faculty 74 Points
9 years ago
Hello student,
Please find the answer to your question below
ADerangementis a permutation in which no element is mapped to itself. LetD(n)be the number of derangements ofnitems.
Here is method of computingD(n).
Let us count the number of derangements ofnitems so thatP(P(n))=n. There aren−1choices forP(n), and for each of those choices,D(n−2)ways to arrange the othern−2items. Thus, there are(n−1)D(n−2)derangements ofnitems so thatP(P(n))=n.
Let us count the number of derangements ofnitems so thatP(P(n))≠n. There aren−1choices forP(n), and for each choice, there is a derangement ofn−1items identical toPexcept that they mapP−1(n)→P(n). Thus, there are(n−1)D(n−1)derangements ofnitems so thatP(P(n))≠n.
Therefore,D(n)=(n−1)(D(n−1)+D(n−2)).........(1)

Method 2 (count permutations):Count the number of permutations ofnitems by counting how many fix exactlykitems.
There are(nk)ways to choose thekitems to fix, thenD(n−k)ways to arrange then−kitems that are not fixed. Since there aren!permutations ofnitems, we get n!=∑k=0n(nk)D(n−k).........(2)
and therefore, rearranging(2)yields
D(n)=n!−∑k=1n(nk)D(n−k)............(3)

Method 3 (inclusion-exclusion):LetSibe the set of permutations ofnitems which fix itemi. Then the number of permutations inkof theSiwould be the permutations that fixkitems. There are(nk)ways to choose thekitems to fix, and(n−k)!ways to arrange the othern−kitems. Thus, the number of permutations that fix at least1item would be∑k=1n(−1)k−1(nk)(n−k)!=∑k=1n(−1)k−1n!k!....(4)
Since there aren!permutations in total, the number of permutations that don't fix any items is
D(n)=n!−∑k=1n(−1)k−1n!k!=∑k=0n(−1)kn!k!≈n!e.........(5)
In fact, the difference
∣∣∣n!e−D(n)∣∣∣=∣∣∣∣∑k=n+1∞(−1)kn!k!∣∣∣∣=∣∣∣1n+1−1(n+1)(n+2)+1(n+1)(n+2)(n+3)−…∣∣∣<1n+1.........(6)
This method yields directly thatD(n)is the closest integer ton!eforn>0.

Think You Can Provide A Better Answer ?

Other Related Questions on Algebra

View all Questions »

ASK QUESTION

Get your questions answered by the expert for free

Answer and earn gift vouchers

Win Gift vouchers upto Rs 500/-

View courses by askIITians

Design classes One-on-One in your own way with Top IITians/Medical Professionals

Click Here Know More

Complete Self Study Package designed by Industry Leading Experts

Click Here Know More

Live 1-1 coding classes to unleash the Creator in your Child

Click Here Know More

a Complete All-in-One Study package Fully Loaded inside a Tablet!

Click Here Know More