Click here to read the complete problem statement.
cool… derangement problem 
This problem is asking us to find the number of permutations of a set of n elements such that there is at least one fixed point.
Let S={1,2,3,…,n}.
A map from S to S such that every distinct element maps to another distinct element is a permutation of the set S.
The total number of possible permutations for a set of n elements is n!.
We are interested in the number of permutations where there exists at least one i such that Arifa(i)=i. This means we are looking for permutations that have at least one fixed point.
It’s easier to calculate the complement: the number of permutations that have no fixed points. These are called derangements.
Let Dn denote the number of derangements of n elements.
The formula for Dn is:
Dn=n!∑k=0nk!(−1)k=n!(0!1−1!1+2!1−3!1+…+n!(−1)n)
We are given n=10. So, we need to calculate D10.
D10=10!(0!1−1!1+2!1−3!1+4!1−5!1+6!1−7!1+8!1−9!1+10!1)
This formula can also be approximated as Dn≈en!.
Let’s calculate D10:
D10=10!(1−1+21−61+241−1201+7201−50401+403201−3628801+36288001)
A more practical way to calculate Dn for small n is using the recurrence relation:
Dn=(n−1)(Dn−1+Dn−2) for n≥2, with D0=1 and D1=0.
Let’s calculate the first few derangements:
D0=1
D1=0
D2=(2−1)(D1+D0)=1(0+1)=1 (e.g., for {1,2}, only (2,1) is a derangement)
D3=(3−1)(D2+D1)=2(1+0)=2 (e.g., for {1,2,3}, (2,3,1), (3,1,2))
D4=(4−1)(D3+D2)=3(2+1)=9
D5=(5−1)(D4+D3)=4(9+2)=4(11)=44
D6=(6−1)(D5+D4)=5(44+9)=5(53)=265
D7=(7−1)(D6+D5)=6(265+44)=6(309)=1854
D8=(8−1)(D7+D6)=7(1854+265)=7(2119)=14833
D9=(9−1)(D8+D7)=8(14833+1854)=8(16687)=133496
D10=(10−1)(D9+D8)=9(133496+14833)=9(148329)=1334961
The total number of possible maps (permutations) for n=10 is 10!.
10!=10×9×8×7×6×5×4×3×2×1=3,628,800.
The number of maps where there exists at least one i such that Arifa(i)=i is the total number of permutations minus the number of derangements.
Number of maps with at least one fixed point = n!−Dn
For n=10:
Number of maps = 10!−D10
Number of maps = 3,628,800−1,334,961
Number of maps = 2,293,839.
The final answer is 2293839.