Well, a) says that the expectation of number of fixed points in a random permutation is $1$, b) says the same about the variance. Both are straightforward.

Sorry to revive this topic but could anyone pls complete the probabilistic method proof. What i understood from this Quote: Well, a) says that the expectation of number of fixed points in a random permutation is , b) says the same about the variance. Both are straightforward. That the question ask us to prove that the total expectation (which i guess means the probability to occur ,something like that) of total number of fixed points is 1. But what about the extra k in each summation

To start, read the first paragraph and the "Definition" section of this article: http://en.wikipedia.org/wiki/Expected_value The sum on the left is $n!$ times the definition of the expected number of fixed points; by linearity of expectation, the expected number of fixed points is 1.

amparvardi: are you sure your problem is right? since $p_n(k)=\binom{n}{k}D_{n-k}$ where $D_{n-k}=$derangement and $\sum_{k=0}^{n}\binom{n}{k}D_{n-k}=\sum_{k=0}^{n}p_n(k)=n!$

It is true that $\sum_{k} p_n(k) = n!$ for $n \geq 0$ and that $\sum_k k p_n(k) = n!$ for $n > 0$ and that $\sum_k (k - 1)^2 p_n(k) = n!$ for $n > 1$.

Here is the part of the problem that made it into the IMO itself: https://www.artofproblemsolving.com/Forum/viewtopic.php?t=60752 And here are related problems, including the other part: http://www.artofproblemsolving.com/Forum/viewtopic.php?t=63678 http://www.artofproblemsolving.com/Forum/viewtopic.php?t=129712 http://www.artofproblemsolving.com/Forum/viewtopic.php?t=60832 http://www.artofproblemsolving.com/Forum/viewtopic.php?t=23684 The probabilistic method applied in most of the proofs (even if the word "probability" never falls, but instead double summations are used) allows to construct and solve lots of similar problems. For instance, let $u\leq n$ be a positive integer. For every $\sigma \in S_n$, let $q_u\left(\sigma\right)$ be the number of all $u$-element subsets $U$ of $\left\{1,2,...,n\right\}$ such that the restriction of $\sigma$ to $U$ is monotonically increasing. For every nonnegative integer $k$, let $r_{n,u}\left(k\right)$ be the number of permutations $\sigma \in S_n$ satisfying $q_u\left(\sigma\right) = k$. Then, $\sum_{k=0}^{\binom{n}{u}} kr_{n,u}\left(k\right) = \binom{n}{u} \frac{n!}{u!}$. Another example: Again, let $u\leq n$ be a positive integer. For every $\sigma \in S_n$, let $c_u\left(\sigma\right)$ be the number of all length-$u$ cycles in the decomposition of $\sigma$ into disjoint cycles. For every nonnegative integer $k$, let $s_{n,u}\left(k\right)$ be the number of permutations $\sigma \in S_n$ satisfying $c_u\left(\sigma\right) = k$. Then, $\sum_{k=0}^{n} ks_{n,u}\left(k\right) = \frac{n!}{u}$. Also, $\sum_{k=0}^{n} k^2s_{n,u}\left(k\right)$ equals $\frac{n!}{u}$ if $n<2u$, and $\frac{n!}{u}+\frac{n!}{u^2}$ if $n\geq 2u$. Can you invent more of this kind of problems? Also, is there a closed form for $\sum_{k=0}^{\binom{n}{u}} k^2r_{n,u}\left(k\right)$ ? (I don't know the answer to this, nor does the OEIS!)

One can also compute the two by first finding out $p_n(k)$ using PIE: $p_nk=\binom{n}{k}(n-k)!-\binom{n}{k+1}(n-k-1)!+\binom{n}{k+2}(n-k-2)!+\dots+(-1)^{n-k}0!$ So it suffices to prove that $\sum{k\binom{n}{k}(n-k)!}-\sum{k\binom{n}{k+1}(n-k-1)!}+\dots+\sum{(-1)^kk0!}$ which is not too hard if one uses the standard identities $k\binom{n}{k}=n\binom{n-1}{k-1}$,etc.Too avoid boring manipulations(though I never felt bored),one can also express the terms of the above in terms of some function of $D_n$,and then use well-known derangement identities.

Just to explain it more clearly. Let $X$ be number of fixed points of the permutations. It is clear that $X$ takes values in the set $\{0,1, 2, \ldots, n\}.$ Thus, on one hand, by the definition of the expected value \[E[X]=0\cdot p_0 + 1\cdot p_1 + \cdots + n\cdot p_n\] where $p_i$ is the probability that the permutation has $i$ fixed points. Obviously, $p_i=\dfrac{p_n(i)}{n\mathrm{!}}.$ So we get that $E[X]=\dfrac{S}{n\mathrm{!}}$, where $S$ is our LHS from the statement. On the other hand, $E[X]=q_1 + q_2 + \cdots + q_n$ where $q_i$ is the probability that $i$ is a fixed point in the permutation. Obviously $q_1 = q_2 = \cdots = q_n = \dfrac{1}{n}$ so we get that $E[X]=1.\blacksquare$