How many permutations fix at least one element for fixed n?

[jostpuur]

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!

...

This doesn't seem to be giving the answer.

 

[jostpuur]

Or did I post this too soon again. The answer to the question 4 seems to be 2*((n-2)+(n-2)*(n-3))*(n-4)!. Perhaps some pattern arises if one proceeds by force...

 

[CompuChip]

Hint: the number of permutations that fixes at least one t plus the number of permutations that fixes none is the total number of permutations. Now try induction (how many are there for n = 2? If I now consider permutations of three elements, how many ways are there to make each of these into a permutation of all elements?)

(Disclaimer: looked at this briefly, but cannot guarantee it will work. Maybe I missed something.)