La suma de los números de Stirling de ambos tipos

Question

Deje $a_k$ el número de formas de dividir un conjunto de $n$ elementos $orderly$,
lo que significa que el orden de los subconjuntos de los asuntos, pero el orden de los elementos de cada subconjunto no.

Mi tarea:

Demostrar, que
$$\sum_{k=1}^n \left[n\atop k\right] a_k = n!2^{n-1}$$

La única cosa que tengo hasta el momento es:

$$a_k = \sum_{i=1}^{k} \left\{n\atop k\right\} \frac{1}{i!}$$

Traté de cambiar el orden de esta suma $\sum\limits_{k=1}^n \left[n\atop k\right]\sum\limits_{i=1}^{k} \left\{n\atop k\right\} \frac{1}{i!}$

y tiene algo así como que: $\sum\limits_{k=1}^n \frac{1}{k!}\sum\limits_{i=k}^{n} \left[n\atop i\right]\left\{i\atop k\right\}$

Mi siguiente idea fue combinatoria prueba, pero no puedo pensar en uno, o hice algún error crucial de arriba, lo que hace que mis esfuerzos bastante inútil.

Puede alguien me guía de cómo realizar esta tarea?
También me gustaría ser más agradecido para corregir mis errores - prefiero hacerlos aquí que en mi examen de la hoja de...

Answer 1

Aquí está una combinatoria argumento para demostrar que

$$\sum_{k=1}^n \left[n\atop k\right] a_k = n!2^{n-1}\;,$$

donde $\left[n\atop k\right]$ es el número de permutaciones de $[n]=\{1,\dots,n\}$ tener $k$ ciclos, y $a_k$ es el número de orden de las particiones de los $k$ ciclos.

En primer lugar, $n!2^{n-1}$ es claramente el número de maneras de romper una permutación de $[n]$ ($=\{1,\dots,n\}$) en los segmentos mediante la inserción de puntos de corte entre los vecinos de los elementos de la partición; el número de segmentos que pueden estar en cualquier lugar de $1$ (no hay puntos de corte) a través de $n$ ($n-1$ los breakpoints).

Ahora lo consideran un segmentada de la partición. Por ejemplo, con $n=9$ podemos tener $$31\mid6259\mid478\;.\tag{1}$$ Each segment will correspond to an unordered set of cycles. To break a segment into cycles, mark each number in the segment that is larger than all of its predecessors within the segment: $$\underline{3}1\mid\underline{6}25\underline{9}\mid\underline{4}\underline{7}\underline{8}\;.$$ Clearly the first number in each segment will be marked. The substring from a marked number up to but not including the next marked number or the end of the segment is a cycle: $$(\underline{3}1)\mid(\underline{6}25)(\underline{9})\mid(\underline{4})(\underline{7})(\underline{8})\;.$$ The segmented partition $(1)$ thus corresponds to the $3$-tuple $\left\langle\{(31)\},\{(625),(9)\},\{(4),(7),(8)\}\right\rangle$ of sets of cycles partitioning the $6$ cycles of the permutation $(31)(4)(625)(7)(8)(9)$. This is one of the orderly partitions counted by the term $\left[9\en la cima de 6\right]a_6$ of the sum $\sum_{k=1}^9\left[9\cima de k\right]a_k$.

Por el contrario, si $\langle\{13\},\{(9),(526)\},\{(7),(8),(4)\}\rangle$ es un proceso ordenado de partición de $[9]$, se puede reconstruir el correspondiente segmentado permutación de la siguiente manera. Inserte primero la segmentación correspondiente a los conjuntos de la partición: $$(13)\mid(9)(526)\mid(7)(8)(4)\;.$$ Within each segment mark each number that is the largest number in its cycle: $$(1\underline{3})\mid(\underline{9})(52\underline{6})\mid(\underline{7})(\underline{8})(\underline{4})\;.$$ Rotate each cycle to bring the largest number to the front: $$(\underline{3}1)\mid(\underline{9})(\underline{6}52)\mid(\underline{7})(\underline{8})(\underline{4})\;.$$ Within each segment rearrange the cycles in descending order of maximal element: $$(\underline{3}1)\mid(\underline{6}52)(\underline{9})\mid(\underline{4})(\underline{7})(\underline{8})\;.$$ Finally, erase the markings and the parentheses, leaving only the segmentation: $$31\mid6529\mid478\;.$$

Un poco de reflexión mostrará que estas operaciones se definen, en general, un bijection entre segmentado permutaciones y ordenada de las particiones de los ciclos de permutaciones de $[n]$.

---

Hay un par de errores en sus cálculos.

$\left\{k\atop i\right\}$ es el número de particiones de $k$ objetos distintos en $i$ no vacía de conjuntos cuando ni el orden dentro del subconjunto ni el orden de los subconjuntos de los asuntos. Por lo tanto, el número de orden de las particiones es $\sum_{i=1}^k\left\{k\atop i\right\}i!$, no $\sum_{i=1}^k\left\{k\atop i\right\}\frac1{i!}$. La suma deseada es entonces

$$\sum_{k=1}^n\sum_{i=1}^k\left[n\atop k\right]\left\{k\atop i\right\}i!=\sum_{i=1}^ni!\sum_{k=i}^n\left[n\atop k\right]\left\{k\atop i\right\}$$

Answer 2

Comenzar por la observación de que la especie de orden de las particiones tiene el especificación $$\mathfrak{S}(\mathcal{U}\mathfrak{P}_{\ge 1}(\mathcal{Z})).$$ Esto le da a la bivariante de generación de función $$G(z, u) = \frac{1}{1-u(\exp(z)-1)}.$$

Por lo tanto la generación de la función de la $a_n$ es $$G(z) = G(z, 1) = \frac{1}{2-\exp(z)} = \frac{1}{2} \frac{1}{1-\exp(z)/2}.$$

Sustituyendo esto en la suma de los rendimientos $$\sum_{k=1}^n \left[n\cima de k\right] k! [z^k] \frac{1}{2} \frac{1}{1-\exp(z)/2}.$$

Llame a esta suma $P_n$ e introducir la exponencial de generación de función $$P(z) = \sum_{n\ge 1} P_n \frac{z^n}{n!}.$$

Tenemos para la suma $$\sum_{k=1}^n \left[n\cima de k\right] k! [z^k] \frac{1}{2} \frac{1}{1-\exp(z)/2} = \frac{1}{2} \sum_{k=1}^n \left[n\cima de k\right] k! [z^k] \sum_{q\ge 0} \frac{\exp(qz)}{2^p} \\= \frac{1}{2} \sum_{k=1}^n \left[n\cima de k\right] \sum_{q\ge 1} \frac{q^k}{2^p}.$$

Esto da para $P(z)$ que $$P(z) = \frac{1}{2}\sum_{q\ge 1} \sum_{n\ge 1} \frac{z^n}{n!} \sum_{k=1}^n \left[n\cima de k\right] \sum_{q\ge 1} \frac{q^k}{2^p} = \frac{1}{2} \sum_{q\ge 1} \sum_{k\ge 1} \frac{q^k}{2^p} \sum_{n\ge k} \left[n\cima de k\right] \frac{z^n}{n!}.$$

Recordemos que las especies de los números de Stirling de primera especie es dada por $$\mathfrak{P}(\mathcal{U}\mathfrak{C}_{\ge 1}(\mathcal{Z})).$$ Esto le da a la bivariante de generación de función $$H(z, u) = \exp\left(u\log\frac{1}{1-z}\right).$$

Sustituyendo esto en $P(z)$ rendimientos $$\frac{1}{2} \sum_{q\ge 1} \sum_{k\ge 1} \frac{q^k}{2^p} \sum_{n\ge k} \frac{z^n}{n!} n! [z^n] [u^k] \exp\left(u\log\frac{1}{1-z}\right) \\ =\frac{1}{2} \sum_{q\ge 1} \sum_{k\ge 1} \frac{q^k}{2^p} \sum_{n\ge k} z^n [z^n] \frac{1}{k!} \left(\log\frac{1}{1-z}\right)^k.$$

Ahora el interior de la suma de la aniquila el coeficiente de extractor, así que conseguir $$\frac{1}{2} \sum_{q\ge 1} \sum_{k\ge 1} \frac{q^k}{2^p} \frac{1}{k!} \left(\log\frac{1}{1-z}\right)^k = \frac{1}{2} \sum_{q\ge 1} \frac{1}{2^p} \left(-1 + \exp\left(q\log\frac{1}{1-z}\right)\right) \\ = -\frac{1}{2} + \frac{1}{2} \sum_{q\ge 1} \frac{1}{2^p} \left(\frac{1}{1-z}\right)^q = -\frac{1}{2} + \frac{1}{2} \frac{1/2/(1-z)}{1-1/2/(1-z)} \\ = -\frac{1}{2} + \frac{1}{2} \frac{1}{2(1-z)-1} = -\frac{1}{2} + \frac{1}{2} \frac{1}{1-2z}.$$

La conclusión es que $$P_n = n! [z^n] P(z) = n! [z^n] \frac{1}{2} \frac{1}{1-2z} = n! \times \frac{1}{2} \times 2^n = 2^{n-1} n!$$ como se reivindica.

Otro cálculo que refererences Wilf del generatingfunctionology.