Prueba combinatoria y algebraica de una identidad que implica números de Stirling de segunda clase {n+1k+1}=∑i(ni){ik}{n+1k+1}=∑i(ni){ik}{n+1 \brace k+1}=\sum_i \binom{n}{i}{i\brace k}

La cuestión es probar la identidad.

$${n+1\brace k+1}=\sum_i \binom{n}{i}{i\brace k}\tag{1}$$

a través de una prueba combinatoria y una prueba algebraica. La pregunta es de A Course in Enumeration de Aigner .

Las llaves indican números de Stirling de segunda clase. He logrado probar la identidad usando el método polinomial (que mostraré a continuación), pero no he avanzado mucho en la prueba combinatoria.

Mi intento : el lado izquierdo representa el número de formas de particionar un$n+1$conjunto de elementos (digamos$[n+1]=\{1,\dotsc, n+1\}$) en$k+1$conjuntos Cada uno de los sumandos del lado derecho representa elegir$i$elementos donde$k \leq i\leq n$de$[n]$y luego dividirlos en$k$conjuntos Probablemente haya algún tipo de clasificación de la partición de un$n+1$elemento establecido en$k+1$establece pero no lo estoy viendo.

Prueba algebraica:

ampliamos$(x+1)^n$de dos maneras diferentes. Primero, tenga en cuenta que

$$(x+1)^n=\sum_{i=0}^n\binom{n}{i}x^i=\sum_{i=0}^n\binom{n}{i}\sum_{k=0}^i {i\brace k} (x)_k=\sum_{k=0}^n(x)_k\left[\sum_{i=k}^n \binom{n}{i}{i\brace k} \right]\tag{2}$$ por el teorema del binomio donde $(x)_k$es el factorial descendente de la longitud $k$. Para la segunda forma escribe $(x+1)^n$como $$\sum_{k=0}^n{n\brace k}(x+1)_{k} =\sum_{k=0}^n{n\brace k}[(x)_k+k(x)_{k-1}]= \sum_{k=0}^n\left[{n\brace k}+(k+1){n\brace k+1}\right](x)_k\tag{3}$$ y concluya usando la relación de recurrencia para los números de Stirling.