Estoy buscando el método por el cual la alteración parcial de la fórmula $D_{n,k}$ fue derivado. Me pueden determinar los valores para valores pequeños de N empíricamente, pero ¿en el caso general, la fórmula se levantó todavía alude mí.
Los enlaces, libros y una explicación que será apreciado.
La fórmula es:
$D_{n,k} = {n \choose k}!(n-k)$
Enlaces:
Aquí es un muy general de la solución. No hay una fórmula fundamental en la combinatoria llamado la exponencial de la fórmula, y una declaración de que es como sigue. Dado un grupo finito $G$ que actúa sobre un conjunto $X$, su ciclo de índice polinomio está dado por
$$Z_G = \frac{1}{|G|} \sum_{g \in G} z_1^{c_1(g)} z_2^{c_2(g)} ... $$
donde $c_i(g)$ es el número de ciclos de longitud $i$ en la acción de la $g$$X$. En particular, la notación $Z_{S_n}$ indican que el ciclo de índice polinomio de $S_n$ que actúa sobre un $n$-elemento definido en la forma habitual; es una generación de la función de la codificación de las proporciones relativas de ciclo diferente tipos de permutaciones.
La exponencial de la fórmula , a continuación, los estados que
$$\sum_{n \ge 0} Z_{S_n} t^n = \exp \left( z_1 t + \frac{z_2 t^2}{2} + \frac{z_3 t^3}{3} + ... \right).$$
En mi opinión este es uno de los más bellos de las fórmulas matemáticas y una razón importante por la que me interesé en la combinatoria fue porque me topé con esta fórmula, mientras que la solución de un Putnam problema (que se describe en el post del blog he enlazado más arriba).
¿Cómo se aplican a este problema? Set$z_2 = z_3 = ... = 1$$z_1 = z$. A continuación, el lado izquierdo de la fórmula exponencial es una función de la generación de la cual cuenta con las permutaciones de acuerdo a cómo muchos puntos fijos ($1$-ciclos) que tienen. En otras palabras,
$$Z_{S_n}(z, 1, 1, ...) = \frac{1}{n!} \sum_{g \in S_n} z^{c_1(g)} = \frac{1}{n!} \sum_{k=0}^n D_{n,k} z^k.$$
El lado derecho de la fórmula exponencial, por otro lado, es
$$\exp \left( zt + \log \frac{1}{1-t} - t \right) = \frac{e^{-t}}{1 - t} e^{zt}.$$
Así obtenemos el hermoso concisa fórmula
$$\sum_{n \ge 0} \frac{t^n}{n!} \sum_{k=0}^n D_{n,k} z^k = \frac{e^{-t}}{1 - t} e^{zt}.$$
Los coeficientes de $\frac{e^{-t}}{1 - t}$ son obtenidas por medio de establecimiento $z = 0$; dan la costumbre, la alteración de los números, por ejemplo, el número de permutaciones de $n$ elementos sin puntos fijos, y esto también puede ser visto directamente desde la generación de la función desde
$$\frac{e^{-t}}{1 - t} = \sum_{n \ge 0} \left( \sum_{k=0}^n \frac{(-1)^k}{k!} \right) t^n$$
que es equivalente a la fórmula $D_{n,0} = n! \sum_{k=0}^n \frac{(-1)^k}{k!} \sim \frac{n!}{e}$. (De hecho, usted puede leer este asintótica directamente desde la generación de la función.) La de arriba, a continuación, da
$$D_{n,k} = {n \choose n-k} D_{n-k,0} = \frac{n!}{k!} \sum_{i=0}^{n-k} \frac{(-1)^i}{i!}.$$
Por supuesto, hay una manera mucho más directa prueba de ello: observar que la especificación de una permutación de $n$ elementos con $k$ puntos fijos es equivalente a especificar el $n-k$ elementos que no son puntos fijos, la especificación de un punto fijo-libre de permutación de estos. Esto inmediatamente le da $D_{n,k} = {n \choose n-k} D_{n-k,0}$, por lo que es suficiente para calcular los $D_{n,0}$, y esto se puede hacer por la norma de inclusión-exclusión en el argumento.
(En el interés de la integridad, el estándar de inclusión-exclusión argumento es como sigue: primero empezamos con todas las $n!$ permutaciones. Luego restamos los que fix $1$, y los que fix $2$, etc., así que restar $n \cdot (n-1)!$. Pero esto es overcounting: tenemos que volver a agregar los que fijar tanto en$1$$2$, o más en general, tanto en $i$ $j$ diferentes $i, j$, por lo tanto, añadir de nuevo ${n \choose 2} \cdot (n-2)!$. Pero esto es overcounting: tenemos que restar los que solucionar cualquier triplete... y así sucesivamente. Esto le da a cada término de la fórmula $n! \sum_{k=0}^n \frac{(-1)^k}{k!}$ uno-por-uno.)
Mi punto es que en la presentación de la generación de los argumentos de la función no es que es más fácil en este caso, sino que se generaliza a mucho más complicado de los problemas en una manera que minimiza el esfuerzo mental: por ejemplo se puede utilizar para el conteo de permutaciones por cuántas $2$-ciclos que tienen, o por $c_3(g) + 17 c_5(g)$, o lo que sea, y la generación de la función también es una manera conveniente de organizar el cálculo del valor esperado y la varianza de diversos permutación de estadísticas; véase, por ejemplo, esta matemática.SE la respuesta.
La respuesta por Qiaochu Yuan es excelente, pero tal vez admite cierta simplificación. Tenga en cuenta que la combinatoria de las especies $\mathcal{Q}$ de permutaciones por ciclos con los puntos fijos marcados está dada por $$\mathcal{P} = \mathfrak{P}(\mathcal{U}\mathfrak{C_1}(\mathcal{Z}) + \mathfrak{C_2}(\mathcal{Z}) + \mathfrak{C_3}(\mathcal{Z}) +\cdots)$$ lo que de inmediato los rendimientos de la generación de la función $$Q(z, u) = \exp\left(uz + \frac{z^2}{2} + \frac{z^3}{3} + \cdots\right) = \exp\left(uz -z + \log\frac{1}{1-z}\right) = \frac{1}{1-z} \exp\left(uz-z\right).$$ Los coeficientes de esta generación de la función de producir la rencontres números como en $$D_{n,k} = n! [z^n] [u^k] Q(z, u).$$ En realidad haciendo la extracción obtenemos $$D_{n,k} = n! [z^n] \frac{1}{1-z} \exp(-z) \frac{z^k}{k!} = \frac{n!}{k!} [z^{n-k}] \frac{1}{1-z} \exp(-z) = \frac{n!}{k!} \sum_{m=0}^{n-k} \frac{(-1)^m}{m.}.$$ Tal vez esto puede contribuir a una comprensión de los elementos esenciales de este tipo de cálculos.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
