Exponencial Funciones De Generación De Alteraciones

Question

Me han introducido el concepto de la exponencial en la generación de funciones de hace un par de días. Sin embargo, a mi entender de ellos son todavía bastante limitada, y me gustaría ver algunos ejemplos. A principios de este plazo, derivado de una fórmula para el número de alteraciones de tamaño $n$ utilizando el principio de inclusión/exclusión, es decir, que $D_n = n!\sum_{k=0}^{\infty}\frac{(-1)^k}{k!}$. ¿Cómo puedo deducir este resultado con el uso de exponenciales funciones de generación, sin necesidad de utilizar el principio de inclusión/exclusión que se derivan $D_n$. La fórmula que se utiliza para las funciones de generación se $\Phi_D(x) = \sum_{n=0}^{\infty}|D_n|\frac{x^n}{n!}$.

Si alguien podía caminar conmigo a través de este ejemplo, les agradecería mucho :) Gracias!

Answer 1

He aquí una manera. Comience con la recurrencia $d_{n+1}=nd_n+nd_{n-1}$ donde $d_n$ es el número de alteraciones de $[n]=\{1,\dots,n\}$. Multiplicar por $\frac{x^n}{n!}$ y suma más de $n\ge 0$:

$$\sum_{n\ge 0}d_{n+1}\frac{x^n}{n!}=\sum_{n\ge 0}nd_n\frac{x^n}{n!}+\sum_{n\ge 0}nd_{n-1}\frac{x^n}{n!}\;.\tag{1}$$

Vamos $$D(x)=\sum_{n\ge 0}d_n\frac{x^n}{n!}$$ be the exponential generating function in question. Then $$D\,'(x)=\sum_{n\ge 0}nd_n\frac{x^{n-1}}{n!}=\sum_{n\ge 1}d_n\frac{x^{n-1}}{(n-1)!}=\sum_{n\ge 0}d_{n+1}\frac{x^n}{n!}\;,\tag{2}$$

$$xD\,'(x)=x\sum_{n\ge 0}nd_n\frac{x^{n-1}}{n!}=\sum_{n\ge 0}nd_n\frac{x^n}{n!}\;,\tag{3}$$

y $$xD(x)=\sum_{n\ge 0}d_n\frac{x^{n+1}}{n!}=\sum_{n\ge 0}(n+1)d_n\frac{x^{n+1}}{(n+1)!}=\sum_{n\ge 1}nd_{n-1}\frac{x^n}{n!}=\sum_{n\ge 0}nd_{n-1}\frac{x^n}{n!}\;,\tag{4}$$ since by convention $d_{-1}=0$.

Compare $(2),(3)$, e $(4)$$(1)$, y verás que

$$D\,'(x)=xD\,'(x)+xD(x)\;,$$ or $$(1-x)D\,'(x)=xD(x)\;.$$ Este es un separables ecuaciones diferenciales,

$$\frac{D\,'(x)}{D(x)}=\frac{x}{1-x}=-1+\frac1{1-x}\;,$$

la que ahora se puede resolver por $D(x)$ por el primer año de cálculo.

---

He aquí otra manera, más rápido, pero sneakier. Para cualquier conjunto particular $K$ $k$ elementos de $[n]$ hay $d_{n-k}$ permutaciones de $[n]$ que $K$ como su conjunto de puntos fijos. Hay $\binom{n}k$ tales subconjuntos $K$, por lo que hay $\binom{n}kd_{n-k}$ permutaciones de $[n]$ con exactamente $k$ puntos fijos. Desde allí se $n!$ permutaciones de $[n]$ total, $$\sum_{k=0}^n\binom{n}kd_{n-k}=n!\;.\tag{5}$$ The lefthand side of $(5)$ is the $n$-th term of the binomial convolution of the sequences $\langle 1,1,1,\dots\rangle$ and $\langle d_n:n\in\Bbb N\rangle$, por lo que la exponencial de generación de función (egf) de la secuencia

$$\left\langle\sum_{k=0}^n\binom{n}kd_{n-k}:n\in\Bbb N\right\rangle=\langle n!:n\in\Bbb N\rangle$$

es el producto de la egfs de $\langle 1,1,1,\dots\rangle$$\langle d_n:n\in\Bbb N\rangle$. Claramente $$\sum_{n\ge 0}n!\frac{x^n}{n!}=\sum_{n\ge 0}x^n=\frac1{1-x}$$ and $$\sum_{n\ge 0}1\cdot\frac{x^n}{n!}=e^x\;,$$ so $$e^xD(x)=\frac1{1-x}\;,$$ and $$D(x)=\frac{e^{-x}}{1-x}\;.$$

Answer 2

Hay un camino más corto incluso que el de los dos en la de Brian bonita respuesta. A partir de la recurrencia de la $D_n = n D_{n-1} + (-1)^n$, se multiplica por $x^n/n!$ y suma más de $n \geq 1$ para obtener \begin{align} &\sum_{n \geq 1} D_n \frac{x^n}{n!} = \sum_{n \geq 1} n D_{n-1} \frac{x^n}{n!} + \sum_{n \geq 1} (-1)^n \frac{x^n}{n!} \\ \implies & G_D(x) - 1 = x \sum_{n \geq 1} D_{n-1} \frac{x^{n-1}}{(n-1)!} + e^{-x} - 1, \text{ as %#%#%} \\ \implies & G_D(x) = x G_D(x) + e^{-x}, \end{align} lo cual nos indica que la exponencial de generación de función es $D_0 = 1$$

Answer 3

De otra manera: Hay $n!$ permutaciones en todos. Una permutación con $k$ puntos fijos que baraja el otro $n - k$ elementos de su alrededor, sin puntos fijos, el $k$ puntos fijos puede ser seleccionado en $\binom{n}{k}$ maneras. Así: $$ n! = \sum_{0 \le k \le n} \binom{n}{k} d_{n -k} $$ Este es un binomio de convolución, el uso de Mike spivey se la notación que da: $$ \begin{align*} \frac{1}{1 - x} &= G_D(x) e^x \\ G_D(x) &= \frac{e^{-x}}{1 - x} \end{align*} $$

Answer 4

Otro par de maneras.

Método 1. $$\mathcal{D} = \operatorname{S\scriptsize ET}(\operatorname{{C\scriptsize YC}_{> 1}}) \implies D(z) = \exp\left(\ln \frac1{1-z} - z\right) = \frac{e^{-z}}{1-z}.$$

Explicación: Una alteración, una permutación sin puntos fijos, es un conjunto de ciclos de cada uno de los que contienen más de un elemento. El FEAG para estos ciclos puede ser adquirido por cualquiera de tomar las FEAG para todos los ciclos, es decir,$C(z) = \ln\frac1{1-z}$, y restando el término "$z$" que corresponde a la única ciclo de longitud $1$, o, si usted no sabe $C(z)$, con explícita a contar como $$C_{>1}(z) = \sum_{n \ge 2} (n-1)! \frac{z^n}{n!} = \sum_{n\ge 2}\frac{z^n}{n} = \ln \frac1{1-z} - z$$

Y como alteraciones son conjuntos de tales ciclos, sus EGF es la exponencial de la ayuda del FEAG de estos ciclos. (Este conjunto→exp-de-EGFs hecho es también conocida como la exponencial de la fórmula.)

---

Tenga en cuenta que el anterior planteamiento también fácilmente se da la generación de función para el número de permutaciones con todos los ciclos de longitud mayor que $r$ cualquier $r$ (alteraciones es la $r=1$ de los casos): $$D_r(z) = \exp\left(\sum_{n > r} \frac{z^r}r\right) = \frac{e^{-z-z^2/2 - \dots - z^r/r}}{1-z}.$$ Por supuesto, el $r=0$ de los casos simplemente da el FEAG de todas las permutaciones, $\exp\ln\frac1{1-z} = \frac1{1-z}$, como se esperaba.

---

Método 2.
Esta es una generación de funciones de un análogo de la inclusión-exclusión principio. A pesar de que es demasiado para este problema, aquí es como una ilustración.

Deje $\mathcal{P}$ es la clase de todas las permutaciones, y deje $\mathcal{Q}$ es la clase de todas las permutaciones con algún subconjunto de sus fija puntos (posiblemente ninguno, posiblemente todos) especialmente distinguido. Ver de una manera diferente, a cualquier miembro de $\mathcal{Q}$ es adquirido por la toma de una permutación arbitraria y la inserción de un conjunto de puntos fijos en él: $\mathcal{Q} = \mathcal{P} \star \operatorname{S\scriptsize ET}(\mathcal{Z})$. El uso de la variable $z$ a marcar el tamaño y la variable $v$ a marcar el distinguido puntos fijos, se obtiene la (bivariado) EGF $Q(z,v) = \frac1{1-z}e^{zv}$.

Ahora si $P(z, u)$ es el FEAG para permutaciones donde $z$ marcas de tamaño y $u$ marcas de los puntos fijos, la ley de "distinguir" algunos de los puntos fijos corresponde a la sustitución de $1 + v$ $u$ en el FEAG para permutaciones: cada punto fijo (marcado por $u$) es distinguido (marcado por $v$) o no (sin marcar). Así que tenemos $Q(z, v) = P(z, 1 + v)$ o, equivalentemente,$P(z, u) = Q(z, u - 1) = \dfrac{e^{z(u-1)}}{1-z}$. El FEAG de alteraciones se consiguió mediante el establecimiento $u = 0$ en el de arriba: $$D(z) = P(z, 0) = \frac{e^{-z}}{1-z}$$

---

Este enfoque también se da el EGF número de permutaciones con exactamente $k$ puntos fijos, como el coeficiente de $u^k$ en el: es $\dfrac{z^k}{k!}\dfrac{e^{-z}}{1-z}$.

---

Referencias: Tanto el de arriba es del libro de la Analítica de la Combinatoria por Flajolet y Sedgewick, páginas 122-123 y 207-208, respectivamente.

---

Por supuesto, una simple observación es que cualquier permutación es un trastorno junto con un conjunto de puntos fijos agregado, por lo que $$\mathcal{P} = \mathcal{D} \estrellas \operatorname{S\scriptsize ET}(\mathcal{Z}) \implica P(z) = D(z) e^z \implica D(z) = \frac{e^{-z}}{1-z} $$ que es el mismo que Brian M. Scott segundo enfoque y vonbrand la respuesta.