Prueba combinatoria (y algebraica) de una identidad que involucra números Lah

Question

Prueba combinatoria (y algebraica) de una identidad que involucra números Lah

Matemáticas
combinatoria
Matemáticas discretas
coeficientes binomiales

Sri-Amirthan Theivendran

Pregunta La pregunta es para probar la siguiente identidad

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

dónde $(n)_k$ denota el factorial descendente de longitud $k$ y $L_{n, k}$ denota los Números de Lah . Esta pregunta es de A Course in Enumeration de Aigner .

Contexto Soy libre de usar las caracterizaciones de los Números de Lah $L_{n,k}$ como los coeficientes de conexión entre los factoriales ascendentes y descendentes o que cuenta el número de formas de dividir el conjunto $[n]$ en $k$ subconjuntos linealmente ordenados no vacíos y también han probado la identidad

\begin{matrix} (2) & (X + 1)^{(norte)} = \sum_{k = 0}^{norte} L_{norte + 1, k + 1} (X - 1)_{k} \end{matrix}

$(x+1)^{(n)}=\sum_{k=0}^n L_{n+1, k+1}(x-1)_k\tag{2}$ dónde

x^{(n)}

$x^{(n)}$ denota el factorial ascendente. También estoy al tanto de una recurrencia de dos términos para los números de Lah, pero me gustaría probar (1) sin ella.

Intentar

Reescritura de prueba combinatoria (1) como

\begin{matrix} (3) & L_{norte + 1, k + 1} = \sum_{i = 0}^{norte} L_{norte - i, k} (norte + k + 1)_{i} \end{matrix}

$L_{n+1, k+1}=\sum_{i=0}^nL_{n-i,k}(n+k+1)_{i}\tag{3}$ mi idea es elegir y arreglar

i

$i$ elementos para ser el mismo bloque que

1

$1$ y luego dividir el resto

n - i

$n-i$ elementos en

k

$k$ bloques ordenados linealmente. El problema es que tengo problemas para interpretar lo que

(n + k + 1)_{i}

$(n+k+1)_{i}$ significa en este contexto.

Prueba algebraica

Tengo dos ideas aquí y no pude 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 lado derecho de (1) y manipular los coeficientes binomiales resultantes, pero es un desastre. Mi segunda idea era mostrar

\begin{matrix} (4) & \sum_{k = 0}^{norte} (\sum_{i = 0}^{norte} L_{i, k} (norte + k + 1)_{norte - i}) (X - 1)_{k} = (X + 1)^{(norte)} \end{matrix}

$\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 concluí usando (2) pero no pude ir más allá de intercambiar la suma.

Cualquier ayuda sobre un enfoque combinatorio o algebraico es bienvenida.

Respuestas (2)

Prueba combinatoria (y algebraica) de una identidad que involucra números Lah

Mike Earnest · 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 tal partición el número más grande $i$ para cual $i+1$ no está en el mismo subconjunto que ninguno 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, luego agregando los elementos $\{i+2,i+3,\dots,n+1\}$ . Los elementos $\{1,2,\dots,i+1\}$ debe abarcar todo $k+1$ subconjuntos, ya que por definición de rango, cada elemento posterior está en un subconjunto con un elemento anterior. Desde $i+1$ está en un subconjunto diferente 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$ se puede agregar a uno de estos subconjuntos en $k+i+2$ maneras (ya sea al comienzo de uno de los $k+1$ subconjuntos, o inmediatamente después de uno de los $i+1$ elementos). A continuación, elemento $i+3$ se puede agregar en $k+i+3$ maneras, entonces $i+4$ se puede agregar en $k+i+4$ maneras, y así sucesivamente.

Poniendo todo esto junto, el número de formas de elegir la partición de rango $i$ es

L_{i, k} \cdot (k + i + 2) \cdot (k + i + 3) \cdot \dots \cdot (norte + k + 1) = L_{i, k} (norte + k + 1)_{norte - i} .

$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 en su publicación conduce a una prueba de identidad similar

L_{norte + 1, k + 1} = \sum_{i} L_{i, k} (\binom{norte}{i}) (norte + 1 - i)! = \sum_{i} L_{i, k} (norte)_{norte - i} \cdot (norte + 1 - i) .

$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).$

Jaja, no era obvio para mí! Estuve atascado en este problema durante mucho tiempo hasta que vi tu respuesta. Diría que mi respuesta es solo una nueva redacción de la suya que no menciona explícitamente la recurrencia de dos términos @N.Shales
Tal vez por eso tenía sentido para mí. Aún así, no sabía cómo convertir mi recurrencia en una biyección, así que es bueno ver que lo lograste :)

esquistos del norte · Answer 2

Una prueba combinatoria parcial puede ir de la siguiente manera:

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

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

De ahí la recurrencia

L_{norte + 1, k + 1} = L_{norte, k} + (norte + k + 1) L_{norte, k + 1} .

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

Iterando:

\begin{aligned} L_{norte + 1, k + 1} & = L_{norte, k} + (norte + k + 1) (L_{norte - 1, k} + (norte + k) L_{norte - 1, k + 1}) \\ = L_{norte, k} + (norte + k + 1) L_{norte - 1, k} + (norte + k + 1) (norte + k) L_{norte - 1, k + 1} \\ = L_{norte, k} + (norte + k + 1) L_{norte - 1, k} + (norte + k + 1) (norte + k) (L_{norte - 2, k} + (norte + k + 1) L_{norte - 2, k + 1}) \\ = L_{norte, k} + (norte + k + 1)^{\underline{1}} L_{norte - 1, k} + (norte + k + 1)^{\underline{2}} L_{norte - 2, k} + (norte + k + 1)^{\underline{3}} L_{norte - 2, k + 1} \\ ⋮ \\ = \sum_{i = 0}^{norte - k} (norte + k + 1)^{\underline{i}} L_{norte - i, k} . \end{aligned}

$\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}$

Prueba combinatoria (y algebraica) de una identidad que involucra números Lah

Sri-Amirthan Theivendran

Respuestas (2)

Mike Earnest

esquistos del norte

Mike Earnest

esquistos del norte

esquistos del norte

¿Trayectorias de coeficientes binomiales?

Contando las formas en la cuadrícula si uno puede moverse de (x,y)(x,y)(x,y) a (x+a,x+b)(x+a,x+b)(x+a, x +b) para x,y,a,b≥0x,y,a,b≥0x,y,a,b\geq 0 arbitrario.

Problema combinatorio: bolas negras y blancas divididas en k grupos con límites, y luego seleccionando una secuencia de solo bolas negras.

Número de rutas en una cuadrícula de S a M

Prueba combinatoria de x(n)=∑nk=1L(n,k)(x)kx(n)=∑k=1nL(n,k)(x)kx^{(n)} = \sum_{k = 1}^n L(n,k)(x)_k

Explicación combinatoria de por qué n2=(n2)+(n+12)n2=(n2)+(n+12)n^2 = {n \elegir 2} + {n+1 \elegir 2}

Demostración de identidades mediante interpretación combinatoria de coeficientes binomiales

Extraer coeficientes para resolver la relación de recurrencia

Probabilidad de que dos elementos particulares se agrupen en una partición aleatoria con tamaños fijos

Un gráfico máximo conectado GGG sin ciclos de longitud de al menos k+1k+1k+1 tiene |V(G)|≤k|V(G)|≤k|V(G)| \leq k o tiene un vértice cortado cuando k≥2k≥2k \geq 2