Una identidad sobre los números de Rencontres

Question

Que haya $n$ personas con asientos marcados $1$ a $n$ . Sea $p_k$ sea el número de arreglos tales que exactamente $k$ Las personas se dirigen a su asiento designado (el $i$ a persona es designada con el número de asiento $i$ ) y el resto no.

Demuestra que $$\sum_{k = 0}^n k*p_k = n!$$

Answer 1

Tenemos para las permutaciones con puntos fijos marcados la combinatoria clase

$$\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})).$$

Esto da la función generadora mixta

$$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).$$

La cantidad deseada viene dada entonces por (el término $u^k z^n/n!$ que representa una permutación de $n$ elementos con $k$ puntos fijos) debe contribuir $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}.$$

Esto es cero para $n=0$ y evalúa a

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

de lo contrario.

Answer 2

La suma cuenta el número de personas que van a su asiento designado, sumado sobre todas las permutaciones. Hay $n!$ permutaciones y $n$ personas, y una persona tiene la misma probabilidad de ir a cualquier asiento en particular, por lo que va a su asiento designado en una fracción $\frac1n$ de todas las permutaciones. Por lo tanto, esta suma es $n!\cdot n\cdot\frac1n=n!$ .

Answer 3

Solución probabilística.

Tome una permutación aleatoria y deje que $X$ ser un número de personas que se sientan en su posición designada. Sea $X_i$ sea $1$ si $i$ -el hombre es designado otro $X_i=0$ . Por definición tenemos $$E(X) = \sum_{k=0}^n kP(X=k) = \sum_{k=0}^n k{p_k\over n!}$$

pero claramente desde $X = X_1+X_2+...+X_n$ tenemos $$E(X) = E(X_1)+...+E(X_n) = {1\over n}+...+{1\over n} = 1$$

y hemos terminado.