jostpuur
Feb10-08, 01:28 AM
For fixed n\in\mathbb{N}, how many permutations X\in S_n there exists, so that X(t)=t at least for some t\in\{1,2,3,\ldots,n\}?
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! :frown:
...
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! :frown:
...
This doesn't seem to be giving the answer.