- 2,100

- 16

For fixed [itex]n\in\mathbb{N}[/itex], how many permutations [itex]X\in S_n[/itex] there exists, so that [itex]X(t)=t[/itex] at least for some [itex]t\in\{1,2,3,\ldots,n\}[/itex]?

Is the solution to this well known? I couldn't solve it by the most direct approach that seemed to be the only apparent way. This is how far I got:

Question 1: How many ways is there to choose X so that X(1)=1? The answer is clearly (n-1)!.

Remark: It would not make sense to next ask that how many ways is there to choose X so that X(2)=2, because some of these X have already been counted.

Question 2: How many ways is there to choose X so that X(1)!=1 and X(2)=2? The X(1) must be different from 1 and 2, so it can be chosen in n-2 different ways. Remaining values X(3),...,X(n) can be chosen in (n-2)! different ways, so the answer is (n-2)*(n-2)!.

Question 3: How many ways is there to choose X so that X(1)!=1, X(2)!=2, and X(3)=3. The choice of X(1) has effect on how many ways the X(2) can be chosen. If we choose X(1)=2, then X(2) can be chosen in n-2 different ways. Remaining X(4),...,X(n) can be chosen in (n-3)! different ways. If we instead choose X(1)!=2, then X(1) can be chosen in n-2 different ways, X(2) can be chosen in n-3 different ways, and again remaining X(4),...,X(n) can be chosen in (n-3)! different ways. So the answer is ((n-2)+(n-2)*(n-3))*(n-3)!.

Question 4: How many ways is there to choose X so that X(1)!=1, X(2)!=2, X(3)!=3 and X(4)=4? If we choose X(1)=2, then [if we choose X(2)=3, then blabla. If we instead choose X(2)!=3, then blabla]. If we choose X(1)=3, then blabla. If we choose X(1)!=2 and X(1)!=3, then blabla. ARGH!

...

This doesn't seem to be giving the answer.

Is the solution to this well known? I couldn't solve it by the most direct approach that seemed to be the only apparent way. This is how far I got:

Question 1: How many ways is there to choose X so that X(1)=1? The answer is clearly (n-1)!.

Remark: It would not make sense to next ask that how many ways is there to choose X so that X(2)=2, because some of these X have already been counted.

Question 2: How many ways is there to choose X so that X(1)!=1 and X(2)=2? The X(1) must be different from 1 and 2, so it can be chosen in n-2 different ways. Remaining values X(3),...,X(n) can be chosen in (n-2)! different ways, so the answer is (n-2)*(n-2)!.

Question 3: How many ways is there to choose X so that X(1)!=1, X(2)!=2, and X(3)=3. The choice of X(1) has effect on how many ways the X(2) can be chosen. If we choose X(1)=2, then X(2) can be chosen in n-2 different ways. Remaining X(4),...,X(n) can be chosen in (n-3)! different ways. If we instead choose X(1)!=2, then X(1) can be chosen in n-2 different ways, X(2) can be chosen in n-3 different ways, and again remaining X(4),...,X(n) can be chosen in (n-3)! different ways. So the answer is ((n-2)+(n-2)*(n-3))*(n-3)!.

Question 4: How many ways is there to choose X so that X(1)!=1, X(2)!=2, X(3)!=3 and X(4)=4? If we choose X(1)=2, then [if we choose X(2)=3, then blabla. If we instead choose X(2)!=3, then blabla]. If we choose X(1)=3, then blabla. If we choose X(1)!=2 and X(1)!=3, then blabla. ARGH!

...

This doesn't seem to be giving the answer.

Last edited: