¿Por qué $S(n,k)=\sum 1^{a_1-1}2^{a_2-1}\cdots k^{a_k-1}$?

Question

He estado tratando de ponerme en algunos combinatoria, y en mi lectura, me parece que $$ S(n,k)=\sum 1^{a_1-1}2^{a_2-1}\cdots k^{a_k-1} $$ donde la suma se toma sobre todas las composiciones $a_1+\cdots+a_k=n$. Aquí $S(n,k)$ indica los números de Stirling del segundo tipo. Estoy tratando de entender por qué hay una combinatoria razón para que esta igualdad. Así, para cada partición $\pi$ $\{1,\dots,n\}$ a $k$ bloques, no debería ser un asociado composición $a_1+\cdots+a_k=n$ tal que exactamente $1^{a_1-1}2^{a_2-1}\cdots k^{a_k-1}$ particiones están asociados con esta composición.

He leído que por la definición de $a_1+\cdots+a_i$ menos $r$ tal de que la eliminación de $1,2,\dots,r$ $\pi$ da un resultado de la partición ha $k-i$ bloques, muestra que esta asociación.

Mi pregunta es, ¿por qué este método de trabajo? La explicación es escasa, por lo que yo estaba esperando para ver más detalles. Gracias.

Answer 1

Si $\pi$ $k$- partición de $[n]$, vamos a $m_0(\pi),\dots,m_{k-1}(\pi)$ ser el máximo de elementos de la $k$ partes de $\pi$, en orden descendente, de modo que, necesariamente,$m_0(\pi)=n$. La eliminación de los enteros $\{1,\dots,m_{k-i}(\pi)\}$ elimina $i$ partes de la partición, dejando $k-i$ partes.

Set $m_k(\pi)=0$, y para $i=1,\dots,k$ deje $a_i(\pi)=m_{i-1}(\pi)-m_i(\pi)\ge 1$; claramente $$a_1(\pi)+\cdots+a_k(\pi)=n$$ is a $k$-composition of $$ n.

Reclamo: Vamos a $b_1+\cdots+b_k$ cualquier $k$-composición de $n$; luego hay $1^{b_1-1}\cdot2^{b_2-1}\cdot\ldots\cdot k^{b_k-1}$ $k$-particiones $\pi$ $[n]$ tal que $a_i(\pi)=b_i$$i=1,\dots,k$.

Como ejemplo, tome $n=5,k=3$, y la composición de la $1+2+2=5$. Que $3$-particiones $\pi$ $[5]$ ha $a_1(\pi)=1,a_2(\pi)=2$, e $a_3(\pi)=2$? Para tal $\pi$ debemos tener $m_0(\pi)=5$, $m_1(\pi)=5-1=4$, y $m_2(\pi)=4-2=2$. Con un poco de trabajo nos encontramos con que las particiones en cuestión son de $$\begin{align*} &\big\{\{1,3,4\},\{2\},\{5\}\big\},\\ &\big\{\{1,3,5\},\{2\},\{4\}\big\},\\ &\big\{\{1,2\},\{3,4\},\{5\}\big\},\\ &\big\{\{1,2\},\{3,5\},\{4\}\big\},\\ &\big\{\{1,4\},\{3,5\},\{2\}\big\},\text{ and}\\ &\big\{\{1,5\},\{3,4\},\{2\}\big\}, \end{align*}$$ so there are indeed $1^{1-1}\cdot2^{2-1}\cdot3^{2-1}$ de ellos.

Prueba de Reclamación: Supongamos, ahora, que $b_1+\cdots+b_k$ $k$- composición de $n$. Para que una $k$-partición de $\pi$ $[n]$ para satisfacer la condición de que $a_i(\pi)=b_i$$i=1,\dots,k$, que debe satisfacer la condición de que $m_i(\pi)=m_{i+1}(\pi)+b_{i+1}$ $i=0,\dots,k-1$ (en el que mostramos $m_k(\pi)=0$).

En particular, $m_{k-1}=b_k$, por lo que hay $b_k-1$ enteros positivos a menos de $m_{k-1}$; claramente cada uno de ellos puede ir en cualquiera de las $k$ partes de $\pi$. Hay $b_{k-1}-1$ enteros positivos a menos de $m_{k-2}$ y mayor $m_{k-1}$; no pueden ir en la parte cuyo máximo elemento es $m_{k-1}$, pero pueden ir a cualquier otra de las $k-1$ partes de de $\pi$. Y en general hay $b_i-1$ enteros positivos que son menos de $m_{i-1}$ y mayor que $m_i$, cada uno de los cuales puede ir a cualquiera de las $i$ partes de $\pi$ cuyo máximo los elementos están en el conjunto $\{m_0(\pi),\dots,m_{i-1}(\pi)\}$ poco no en cualquiera de las partes con menor máximo de elementos. Por lo tanto, estos $n-k$ no consumo máximo de elementos que pueden ser distribuidos entre las $k$ partes en

$$\prod_{i=1}^k i^{b_i-1}=1^{b_1-1}\cdot2^{b_2-1}\cdot\ldots\cdot k^{b_k-1}$$

diferentes maneras. $\dashv$

Answer 2

Una mancha de generatingfunctionological enfoque utiliza una fórmula de recursión. Vamos

$$f_k(x)=\sum_{n=k}^\infty \left\{n\atop k\right\}x^n.$$

$$=\left\{k\atop k\right\}x^k+\sum_{n=k}^\infty\left\{n+1\atop k\right\} x^{n+1}$$

$$=x^k+x\sum_{n=k}^\infty\left(k\left\{n\atop k\right\}+\left\{n\atop k-1\right\}\right)x^n$$

$$=x^k+x\left(kf_k(x)+f_{k-1}(x)-\left\{k-1\atop k-1\right\}x^{k-1}\right)$$

$$=kxf_k(x)+xf_{k-1}(x).$$

Con $f_1(x)=x/(1-x)$ $f_k(x)=x/(1-kx)\cdot f_{k-1}(x)$ obtenemos por inducción

$$f_k(x)=\frac{x}{1-kx}\;\cdots\;\frac{x}{1-2x}\frac{x}{1-x}=\prod_{l=1}^k\frac{x}{1-lx}$$

$$\large =\prod_{l=1}^k\left(\sum_{m_l=1}^\infty l^{m_l-1}x^{m_l}\right)=\sum_{n=k}^\infty \left(\sum_{m_1+\cdots+m_k=n}1^{m_1-1}2^{m_2-1}\cdots k^{m_k-1}\right)x^n.$$

Igualar los coeficientes entre las dos series y, a continuación, nuestro trabajo aquí está hecho.