One Nice Solution: Count all pairs $(x, s)$ where s is a permutation with $x$ a fixed point of $x$. Clearly, if we fix $x$, then there are $(n-1)!$ possible permutations $s$. So the total count is $n!$. But if we count the number of permutations $s$ with exactly $k$ fixed points, then we get the sum in the question.

Hi e.lopes, it is nice that you copy & paste solutions quickly but could you please be so creative and develop your OWN IDEAS and write DETAILED SOLUTIONS!

A nice generalisation of this problem is http://www.mathlinks.ro/Forum/viewtopic.php?t=60832

Isn't it just an algebraic identity if you use the formula (which is easily proved with inclusion\exclusion) for derangements? $ p_n(0)=n! \sum_{i=0}^{n} \frac{(-1)^i}{i!}$ Hence: $ p_n(k)=\binom{n}{k}(n-k)! \sum_{i=0}^{n-k} \frac{(-1)^i}{i!}$ $ \sum_{k=0}^{n}k p_n(k)= \sum_{k=0}^{n} k\binom{n}{k}(n-k)! \sum_{i=0}^{n-k} \frac{(-1)^i}{i!}=\sum_{k=0}^{n} k\frac{n!}{k!} \sum_{i=0}^{n-k} \frac{(-1)^i}{i!}=n!\sum_{k=0}^{n}\frac{k}{k!} \sum_{i=0}^{n-k} \frac{(-1)^i}{i!}$ So all we need to show is that $ \sum_{k=0}^{n}\frac{k}{k!} \sum_{i=0}^{n-k} \frac{(-1)^i}{i!}=1$, which follows from straight-forward induction - if $ \sum_{k=0}^{n}\frac{k}{k!} \sum_{i=0}^{n-k} \frac{(-1)^i}{i!}=1$, then: $ \sum_{k=0}^{n+1}\frac{k}{k!} \sum_{i=0}^{n+1-k} \frac{(-1)^i}{i!}-\sum_{k=0}^{n}\frac{k}{k!} \sum_{i=0}^{n-k} \frac{(-1)^i}{i!}=\sum_{k=0}^{n}\frac{k}{k!} \frac{(-1)^{n+1-k}}{(n+1-k)!}+\frac{1}{n!}=\sum_{k=0}^{n} \frac{(-1)^{n+1-k}}{(n+1-k)!(k-1)!}+\frac{1}{n!}=\frac{\sum_{k=0}^{n} \binom{n}{n+1-k} (-1)^{n+1-k} + 1}{n!} = (1-1)^n/n!=0$ I don't think it was a suitable problem for an IMO. If you happen to know derangements it becomes an exercise.

Clearly, $ p_n(k)=\binom{n}{k}\cdot d_{n-k}$, where $ d_n$ is the number of derangements of $ \{1;2;\dots;n\}$. Evaluate $ \frac{p_n(k)}{p_{n-1}(k-1)}$ to note that $ p_n(k)=\dfrac{n}{k}\cdot p_{n-1}(k-1)$. Hence, $ \sum_{k=0}^{n}{kp_n(k)}=n\cdot\sum_{k=1}^{n}{p_{n-1}(k-1)}=n\cdot(n-1)!$ as the latter sum is the number of permutations of $ \{1;2;\dots;n-1\}$, which proves our claim and avoids the rather messy algebra.

In the interest of completeness, I'll include a rather general technique: the relevant generating function is $ \sum_{n, k \ge 0} \frac {p_n(k)}{n!} x^n y^k = \frac {1}{1 - x} e^{yx - x}$ (see the proof here). This gives the obvious identity $ \sum_{k = 0}^{n} k p_n(k) = n!$ when $ y = 1$. Differentiating with repsect to $ y$, we obtain $ \sum_{n, k \ge 0} \frac {kp_n(k)}{n!} x^n y^{k - 1} = \frac {x}{1 - x} e^{yx - x}$ which, upon the substitution $ y = 1$, gives $ \sum_{k = 0}^{n} p_n(k) = 0$ when $ n = 0$ and $ n!$ otherwise. We have the following obvious generalization: $ \sum_{k = r}^{n} (k)_r p_n(k) = n!, n \ge r$ where $ (k)_r = k(k - 1)...(k - (r - 1)) = r! {k \choose r}$. Combined with a well-known identity involving the Stirling numbers of the second kind, this gives one proof of the result in this related thread about the sum $ \sum_{k = 0}^{n} k^r p_n(k) = \sum_{\pi \in S_n} \text{Fix}(\pi)^r$. ZetaX: was this the problem that inspired your thread?

Another solution: The following identities are quite obvious: (1) p_n(k)=\binom{n}{k}\cdot p_{n-k}(0) with p_0(0):=1 (2) \sum_{k = 0}^{n} p_n(k) = n! The rest is a simple index shift j = k-1: \sum_{k = 0}^{n} k \cdot p_n(k) = \sum_{k = 1}^{n} k \cdot \binom{n}{k}\cdot p_{n-k}(0) = n \cdot \sum_{j = 0}^{n-1} \binom{n-1}{j}\cdot p_{n-1-j}(0) = n \cdot \sum_{j = 0}^{n-1} p_{n-1}(j) = n \cdot (n-1)! = n!

Sorry, here the solution one can read: The following identities are quite obvious: (1) $ p_n(k)=\binom{n}{k}\cdot p_{n-k}(0)$ with $ p_0(0): =1$ (2) $ \sum_{k = 0}^{n} p_n(k) = n!$ The rest is a simple index shift j = k-1: $ \sum_{k = 0}^{n} k \cdot p_n(k) = \sum_{k = 1}^{n} k \cdot \binom{n}{k}\cdot p_{n-k}(0) = n \cdot \sum_{j = 0}^{n-1} \binom{n-1}{j}\cdot p_{n-1-j}(0)$ $ =n \cdot \sum_{j = 0}^{n-1} p_{n-1}(j) = n \cdot (n-1)! = n!$

My own preferred way to think about e.lopes original solution is as follows: Dividing both sides by $ n!$, we are being asked to show that the expected number of fixed points in a random permutation $ \sigma$ is $ 1$. But this is the sum of $ n$ indicator variables $ X_i$ corresponding to each $ i$ being fixed. By symmetry, the probability that $ \sigma(i)=i$ (the expectation of $ X_i$) is $ \frac{1}{n}$. The result follows from linearity of expectation.

Somewhat similar to above... This is basically a derangement problem! Thus, we use a probabilistic interpretation. We know the probability of a permutation having $k$ fixed points is \[\frac{p_{n}(k)}{n!}\], and so the expected value of fixed points is \[\sum_{k=0}^nk \frac{p_n(k)}{n!}\]. In derangement, we know that the expected value is 1 fixed, and thus \[\sum_{k=0}^nk \frac{p_n(k)}{n!} = 1\] or \[\sum_{k=0}^nk p_n(k) = n!\] as desired $\blacksquare$

Similar to above, let us calculate the expected number of fixed points there are in any permutation. The element $a$ is a fixed point with probability $\frac{1}{n}$ and there are $n$ elements, making the expected number of fixed points in any permutation to be $n\left(\frac1n\right)=1$. The total number of permutations is $n!$ therefore the total number of fixed points in all the subsets is $n!$. We can calculate this another way as well. $p_n(k)$ is the number of permutations with $k$ fixed points so $kp_n(k)$ is the total number of fixed points in the set of permutations with $k$ fixed points. Thus the total number of fixed points in all the permutations is $\sum_{k=0}^n kp_n(k)$, but this is also $n!$, as calculated above. So \[ \sum_{k=0}^n kp_n(k)=n!, \] as desired.

Surely not a new idea, but willl post my soltion as well We count the number of pairs (fixed point, permutation) in two ways. Let there be $X$ such pairs. Note that each point is fixed point in $(n-1)!$ permutations, just fix one and randomly permute all other elements. Because there are $n$ points, we have that $X=n \cdot (n-1)!=n!$. On the other hand, from the perspective of permutations: each permutation with $k$ fixed points is counted $k$ times in $X$, once for each fixed point. Since there are $p_n(k)$ permutations with $k$ fixed points, they are together counted $kp_n(k)$ times in $X$. Summing up over all values of $k$ we get $X=\sum_{k=0}^n kp_n(k)$. The desired equality follows.

Probabilistic Method: Let $X$ be the number of fixed points in a random permutation. It is well known that $\mathbf{E}[X]=1$. Hence, $$1=\mathbf{E}[X]=\sum_{k} k\mathbf{P}[X=k]=\sum_{k} k \cdot \frac{p_{n}(k)}{n!} \Leftrightarrow \sum_{k} k p_n(k)=n!$$ Double Counting: Consider a $n! \times n$ matrix. Label the rows $P_1, P_2, \cdots P_{n!},$ and the columns $1, 2 \cdots n$. Here, each row corresponds to a permutation of $\{1, 2, \cdots n\}$. Let $N$ be the total number of fixed points over all these permutations. We count $N$ in two ways. Rows: The number of fixed points $k$ appears $P_{n}(k)$ times. Columns: Each element is a fixed point in exactly $(n-1)!$ permutations. Hence, $$\sum_{k} k p_n(k)=N=n \cdot (n-1)!=n!$$

Consider a permutation $a_1,a_2,...,a_n$ of $1,2,...,n$. We shall put exactly one star over some number in the new permutation such that, the number with the star over it is a fixed point. Over all permutations of $1,2,...,n$, there are $\sum_{k=0}^n kp_n(k)$ ways to put a star over some fixed point of the permutation. On the other hand, if we pick the position of the star first, then there are $n\cdot (n-1)! = n!$ ways to do so, since there are $n$ possible elements to put the star over and $(n-1)!$ ways to permute the rest. Therefore, $$\sum_{k=0}^nk p_n(k)=n!.$$

Let the set of permutations of this set be $\Gamma$. We define $F(\pi)$ for a permutation $\pi$ as the number of fixed points and $F_{\pi}$ as the set of fixed points under $\pi$. We compute that \[\sum_{k=0}^n kp_n(k) = \sum_{\pi \in \Gamma}F(\pi) = \sum_{\pi \in \Gamma, k \in F_{\pi}} 1.\]Thus, for each $k$ in the set $\{1,2,3,\cdots , n\}$, this sum counts the number of times it is a fixed point of a permutation. But clearly, each $k$ is the fixed point of a permutation exactly $(n-1)!$ ways, so the sum is \[\sum_{k=0}^n kp_n(k) = \sum_{k=1}^n (n-1)! = n!,\]as desired.

A given position has a $\tfrac{1}{n}$ chance of being a fixed point. Hence, the expected number of fixed points of a permutation is $\frac{1}{n} \cdot n=1$. However, the expected number of fixed points can also be calculated as \[\sum_{k=0}^{n} k \cdot \frac{p_n(k)}{n!}=0\cdot \frac{p_n(0)}{n!}+1\cdot \frac{p_n(1)}{n!}+2\cdot \frac{p_n(2)}{n!}+\dots +n \cdot \frac{p_n(n)}{n},\]since the probability of $k$ fixed points is equal to $\frac{p_n(k)}{n!}.$ We can set the two expected values equal, getting \[\sum_{k=0}^{n} k \cdot \frac{p_n(k)}{n!}=1\]\[\sum_{k=0}^nk p_n(k)=n!.\]

divide it by n! and now what we are having on the left hand side is probability that we can find a fixed point in any permutation and now we know that this is true because we can find atleast 0 fixed points in any permutation reason for the left hand side is that the weight of k means that we have k point in the permutations so we get overall fixed points inn the particular permutation and then the other thing is caluclating the probability that the permutaion has k fixed points

Isn't this well-known? If I recall correctly, a similar problem appeared in the Global Section of the OTIS Excerpts. Anyways, my solution is below. Notice $\sum_{k = 0}^{n} k \cdot p_n(k)$ counts the total number of fixed points over all $n!$ permutations, as the multiplicity of fixed points per each permutation is accounted for in the sum. Now, we count the total number of fixed points in another fashion. If $i$ is fixed where $1 \le i \le n$, then there's $(n-1)!$ possible permutations of the other $n-1$ letters, i.e. $(n-1)!$ permutations where $i$ is fixed. Hence, the total number of fixed points is just $$\underbrace{(n-1)! + (n-1)! + \ldots + (n-1)!}_{\text{n times}} = n \cdot (n-1)! = n!$$as desired. $\blacksquare$

Sample a random permutation of $\{1, 2, \cdots, n\}$ and compute the number of fixed points. The expected value of this quantity is $1$ which is quite easy to show through the linearity of expectation. However this quantity is also just \[\frac{1}{n!} \sum_{k=0}^nk p_n(k).\]This finishes.

The expected number of fixed points of a permutation of $\{1,2,3,\ldots,n\}$ is $\frac{\sum_{k=0}^n kp_n(k)}{n!}$. Now note that there is $\frac{1}{n}$ probability for any specific element to be in its original position. By the Linearity of Expectation, the expected number of fixed points is $n\cdot \frac{1}{n}=1$. This proves the desired result.

Let $S$ be the set of all permutations of $1,2,\ldots,n$. We will count the number of ways to choose a pair $(s,i)$ such that $s\in S$ with $k$ fixed points has a fixed point $i$. First, there are $p_n(k)$ ways to choose the permutation $s$ with $k$ fixed points, and then $k$ choices for the fixed point $i$. There are thus $$\sum_{k=0}^{n}{kp_n(k)}$$such pairs. We can choose a fix $i$ first, for which we have $n$ choices, and then permute the remaining $n-1$ elements, so $n!$ ways in total. Note that we to not count the permutations with $0$ fixed points here, but in the above sum $kp_n(k)=0$ for $k=0$ anyways. Thus $$\sum_{k=0}^{n}{kp_n(k)}=n!$$

The quantity $k.p_n(k)$ represents the number of all fixed point in those permutations which has $k$ fixed point. So their sum is the total number of fixed points. And the number of all fixed point is $n!$ counting by the columns. Remark: The case $k=0$ is not that redundant. Though it is obvious, it can give a realization what $k.p_n(k)$ actually mean, in other words there is not fixed point in all the permutations with $0$ fixed point.

The expected number of fixed points of a particular permutation is $n \cdot \frac 1n = 1$, so we have $n! \cdot 1 = n!$ total fixed points across all permutations, which is essentially what the question is asking for. $\blacksquare$

We claim that the expected number of fixed points of a random permutation of $\{1,2, \cdots, n\}$ is $1$. To see this, consider an arbitrary element $i$ $(1 \leq i \leq n)$. The probability that $i$ is a fixed point is $\dfrac 1n$, so $i$ contributes $\dfrac 1n$ to the total number of expected fixed points. Since there are $n$ elements, by Linearity of Expectation, the expected number of fixed points is $n \cdot \dfrac 1n = 1$, proving the claim. The expected number of fixed points of a random permutation of the set $\{1,2, \cdots, n\}$ can also be expressed as$$\dfrac{\sum_{k=0}^n k p_n(k)}{n!}$$since there are a total of $n!$ permutations. It follows from the claim that$$\dfrac{\sum_{k=0}^n k p_n(k)}{n!} = 1$$which is the desired result. $\blacksquare$