Combinatorics/probability: matching pairs in match-questions and expectation value Define a matching problem to be the following:


*

*$n$ numbered boxes and $n$ numbered cards

*you have to place all the cards. No empty boxes and no left behind cards are allowed.


So you end up with a permutation of length $n$. The number of possible permutations being $n!$
Let $X$ be the variable of $x$ matching places in an ordering.
Only 1 permutation is correct. So $P(X=n)=\frac{1}{n!}$
I would like to calculate $P(X=2)$, $P(X=3)$ and so on. 
$P(X=1)=0$ obviously...
I tackled this problem the cowardly way by writing a program that generates all permutations of length $n$, calculates the Hamming distance between the first element, builds a frequency table and consequently a probability table.
So I have my answers... but I still feel a bit, well... dirty by going brute force.
Therefore my first question is how can I calculate the probability table for $X$ directly (without resorting to brute force)?
My second question has to do with the expectation value $E(X)$. By calculation in the same program I saw that $\forall n .E(X)=n-1$. $\forall n$ is in my case very finite and is concluded from running tests for $n<10$.
But nonetheless I have trouble understanding why this is the case. Maybe by understanding my first question, I will gain insight in my second... Your help is appreciated. 
 A: First of all, if I understand you correctly, $\mathbb{P}(X=1)$ is not zero! Your $X$ is a well known object, called the number of fixed points of a permutation, namely $X(\pi) = $ #$\{k \in [n]: \pi(k) = k\}$ for any permutation $\pi \in S_n$. It's easy to see that the distribution of $X$ is given by
$\mathbb{P}(X = k) = \frac{1}{n!} \binom{n}{k} D_{n-k}$,
where $D_m$ is the number permutations of $m$ objects that are derangements, i.e. the number of permutations $\pi \in S_m$ with no fixed points. (This comes from choosing a $k$ subset of $[n]$ to be the fixed points, and then choosing a derangement on the remaining elements.) There are some formulas for $D_m$, but I don't know if there is a simple explicit formula. 
To get the expectation of $X$, one can do the following simple expectation computation: note that 
$X(\pi) = \sum_{k=1}^n 1\{\pi(k) = k\}$,
so by linearity of expectation, 
$\mathbb{E}X = \sum_{k=1}^n \mathbb{P}(\Pi(k) = k) = \sum_{k=1}^n \frac{1}{n} = 1.$
A related fact: for large $n$, $\mathbb{P}(X = k) \approx \frac{1}{e k!}$, i.e. $X$ is asymptotically Poisson distributed (with rate $1$). 
