An identity on Rencontres numbers

114 Views Asked by At

Let there be $n$ people with seats marked $1$ to $n$. Let $p_k$ be the number of arrangements such that exactly $k$ persons go to their designated seat (the $i$ th person is designated seat number $i$) and the remaining do not.

Show that $$\sum_{k = 0}^n k*p_k = n!$$

3

There are 3 best solutions below

1
On BEST ANSWER

We have for permutations with fixed points marked the combinatorial class

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}(\mathcal{U}\mathcal{Z} + \textsc{CYC}_{\ge 2}(\mathcal{Z})).$$

This gives the mixed generating function

$$G(z, u) = \exp\left(uz + \sum_{q\ge 2} \frac{z^q}{q}\right) = \exp\left(uz-z + \log\frac{1}{1-z}\right) \\= \frac{1}{1-z} \exp(uz-z).$$

The desired quantity is then given by (the term $u^k z^n/n!$ representing a permutation of $n$ elements with $k$ fixed points) should contribute $k z^n/n!$)

$$n! [z^n] \left. \frac{\partial}{\partial u} G(z, u) \right|_{u=1} \\ = n! [z^n] \left. \frac{1}{1-z} \exp(uz-z) z \right|_{u=1} \\ = n! [z^n] \frac{z}{1-z}.$$

This is zero for $n=0$ and evaluates to

$$\bbox[5px,border:2px solid #00A000]{n!}$$

otherwise.

1
On

The sum counts the number of people who go their designated seat, summed over all permutations. There are $n!$ permutations and $n$ people, and a person is equally likely to go to any particular seat, so they go to their designated seat in a fraction $\frac1n$ of all permutations. Thus this sum is $n!\cdot n\cdot\frac1n=n!$.

1
On

Probabilistic solution.

Take a random permutation and let $X$ be a number of people that seat on their designate position. Let $X_i$ be $1$ if $i$-th wo/man is designate else $X_i=0$. By definition we have $$E(X) = \sum_{k=0}^n kP(X=k) = \sum_{k=0}^n k{p_k\over n!}$$

but clearly since $X = X_1+X_2+...+X_n$ we have $$E(X) = E(X_1)+...+E(X_n) = {1\over n}+...+{1\over n} = 1$$

and we are done.