En el número de Stirling

Question

Deje $H(n,k)$ el número de secuencias de $b_1,b_2, \ldots, b_n$ tal: que el elemento mayor es $k$, todos los números de $1,2,\ldots,k$ ocurren, y la primera aparición de $i$ ocurre antes de la primera aparición de $i+1$ todos los $i \in \{1,2,\cdots, k-1\}$.

Mi objetivo es mostrar que la $H(n,k)= S_{n,k}$ donde $S_{n,k}$ indica el número de Stirling del segundo tipo.

Aquí está mi enfoque: empecé por la comprensión de cómo estas secuencias parecen y se me ocurrió la siguiente:

• $H(2,1) = |\{11\}| =1 = S_{2,1}$

• $H(2,2) = |\{12\}| =1 = S_{2,2}$

• $H(3,2) = |\{112, 121,122\}| =3 = S_{3,2}$

Yo calculada par más para ver lo que pasa. Aquí está mi observación: me di cuenta de que $$H(3,2)=1+2(1) = H(2,1) + H(2,2)$$ and that quickly let me realize that $H(n,k)$ will satisfy the well known Stirling number of the second kind relation reccurence which is $$S_{n,k}= S_{n-1,k-1}+ kS_{n-1,k}.$$ Thus, I claim that $H(n,k)= S_{n,k}$.

Traté de mostrar esto por inducción, pero no estoy mostrar si esto tiene sentido: $$H_{n+1,k+1}=H_{n,k} + (k+1) H_{n,k+1}= S_{n,k} + (k+1) S_{n,k+1}= S_{n+1,k+1}$$

Pensé que esta pregunta está relacionada con la Express $F(n,k)$ a través de los Números de Stirling si ...

Es esto suficiente? Cualquier ayuda se agradece.

Answer 1

Es más fácil hacer esto por bijection: dada una partición de $\{1,2,\dots,n\}$ a $k$ partes (las cosas contadas por los números de Stirling) ordenar las piezas por su elemento más pequeño, y escribir una secuencia $b_1, b_2, \dots, b_n$ donde $b_i$ es el índice de la parte que contiene la $i$.

Por ejemplo, para la partición de $\{1,3,7\}, \{2\}, \{4,5,6\}$, podemos escribir la secuencia de $1, 2, 1, 3, 3, 3, 1$.

Por supuesto, tenemos que comprobar que las distintas particiones de dar secuencias distintas, y que cada secuencia con un máximo de $k$ en el que la primera aparición de $i$ ocurre antes de la primera aparición de $i+1$ se obtiene de esta manera.

Si quieres demostrar que $H(n,k) = S_{n,k}$ mostrando que satisfacen la misma recurrencia, es también importante comprobar que tienen la misma base de los casos: que ambos son $1$ al $k=1$ o $n=k$.

Answer 2

Resolví una recurrencia similar$P_{n,k}=1 + P_{n-1,k-1}+ P_{n-1,k}$ en un contexto diferente. La solución fue ...$$P_{n, k}=\sum_{j=1}^{k}{n \choose j}$ $ Tenga en cuenta que esta suma binomial no tiene forma cerrada. Puede ser que esto te sea útil ...