Demostración combinatoria (y algebraica) de una identidad con números de Lah

Question

Pregunta Se trata de demostrar la siguiente identidad

$$ L_{n+1, k+1}=\sum_{i=0}^nL_{i,k}(n+k+1)_{n-i}\tag{1} $$

donde $(n)_k$ denota el factorial descendente de longitud $k$ et $L_{n, k}$ denota el Números Lah . Esta pregunta es de Aigner Curso de Enumeración .

Contexto Soy libre de utilizar las caracterizaciones de los Números Lah $L_{n,k}$ como los coeficientes de conexión entre los factoriales ascendentes y los factoriales descendentes o que cuenta el número de formas de partición del conjunto $[n]$ en $k$ subconjuntos linealmente ordenados no vacíos y también han demostrado la identidad $$ (x+1)^{(n)}=\sum_{k=0}^n L_{n+1, k+1}(x-1)_k\tag{2} $$ donde $x^{(n)}$ denota el factorial ascendente. También conozco una recurrencia de dos términos para los Números de Lah, pero me gustaría demostrar (1) sin ella.

Intento

Prueba combinatoria Reescribiendo (1) como $$ L_{n+1, k+1}=\sum_{i=0}^nL_{n-i,k}(n+k+1)_{i}\tag{3} $$ mi idea es elegir y organizar $i$ para ser el mismo bloque que $1$ y luego dividir el resto de $n-i$ elementos en $k$ bloques ordenados linealmente. El problema es que tengo problemas para interpretar lo que $(n+k+1)_{i}$ significa en este contexto.

Prueba algebraica

Tengo dos ideas aquí y no he podido llegar lejos con ambas. Primero podemos usar el hecho de que $L_{i,k}=\frac{i!}{k!}\binom{i-1}{k-1}$ y sustituir en el RHS de (1) y manipular los coeficientes binomiales resultantes pero es un lío. Mi segunda idea era mostrar $$ \sum_{k=0}^n\left(\sum_{i=0}^nL_{i,k}(n+k+1)_{n-i}\right)(x-1)_k=(x+1)^{(n)}\tag{4} $$ y concluir utilizando (2), pero no pudo ir más allá de intercambiar la suma.

Cualquier ayuda sobre un enfoque combinatorio o algebraico es bienvenida.

Answer 1

$L_{n+1,k+1}$ es el número de particiones de $\{1,2,\dots,n,n+1\}$ en $k+1$ subconjuntos ordenados no vacíos. Sea el rango de dicha partición sea el mayor número $i$ para lo cual $i+1$ no está en el mismo subconjunto que cualquiera de $1,2,\dots,i$ . Entonces

$L_{i,k}(n+k+1)_{n-i}$ es el número de particiones con rango $i$ .

¿Por qué? Una partición de rango $i$ se puede especificar eligiendo primero una partición de $\{1,2,\dots,i+1\}$ en subconjuntos ordenados, añadiendo luego los elementos $\{i+2,i+3,\dots,n+1\}$ . Los elementos $\{1,2,\dots,i+1\}$ debe abarcar todos los $k+1$ subconjuntos, ya que por definición de rango, cada elemento posterior está en un subconjunto con un elemento anterior. Dado que $i+1$ está en un subconjunto diferente al de $\{1,2,\dots,i\}$ Hay $L_{i,k}$ formas de colocar los números $\{1,2,\dots,i+1\}$ . Entonces, el elemento $i+2$ puede añadirse a uno de estos subconjuntos en $k+i+2$ maneras (ya sea al inicio de uno de los $k+1$ subconjuntos, o inmediatamente después de uno de los $i+1$ elementos). A continuación, el elemento $i+3$ se puede añadir en $k+i+3$ formas, entonces $i+4$ se puede añadir en $k+i+4$ formas, etc.

Con todo esto, el número de formas de elegir la partición del rango $i$ es $$ L_{i,k}\cdot (k+i+2)\cdot(k+i+3)\cdot\ldots\cdot(n+k+1)=L_{i,k}(n+k+1)_{n-i}. $$

---

Nota al margen: la prueba combinatoria de tu post conduce a una prueba de la identidad similar $$ L_{n+1,k+1}=\sum_i L_{i,k}\binom{n}i(n+1-i)!=\sum_i L_{i,k}(n)_{n-i}\cdot(n+1-i). $$

Answer 2

Una prueba combinatoria parcial puede ser la siguiente:

El conjunto $S=\{1,2,\ldots , n+1\}$ puede dividirse en $k+1$ conjuntos ordenados no vacíos en $L_{n+1,k+1}$ formas.

Como alternativa, el elemento $k+1$ está en un conjunto ordenado por sí mismo en $L_{n,k}$ formas o aparece entre elementos en el $k+1$ conjuntos ordenados en $(n+k+1)L_{n,k+1}$ formas.

Por lo tanto, la recurrencia

$$L_{n+1,k+1}=L_{n,k}+(n+k+1)L_{n,k+1}\, .$$

Iterar:

$$\begin{align}L_{n+1,k+1}&=L_{n,k}+(n+k+1)(L_{n-1,k}+(n+k)L_{n-1,k+1})\\[1ex] &=L_{n,k}+(n+k+1)L_{n-1,k}+(n+k+1)(n+k)L_{n-1,k+1}\\[1ex] &=L_{n,k}+(n+k+1)L_{n-1,k}+(n+k+1)(n+k)(L_{n-2,k}+(n+k+1)L_{n-2,k+1})\\[1ex] &=L_{n,k}+(n+k+1)^\underline{1}L_{n-1,k}+(n+k+1)^\underline{2}L_{n-2,k}+(n+k+1)^\underline{3}L_{n-2,k+1}\\[1ex] &\hspace1.4ex\vdots\\[1ex] &=\sum_{i=0}^{n-k}(n+k+1)^\underline{i}L_{n-i,k}\, .\end{align}$$