Prueba combinatoria para series de números de Stirling y coeficientes binomiales

Question

Prueba combinatoria para series de números de Stirling y coeficientes binomiales

Matemáticas
combinatoria
números de stirling
pruebas combinatorias
coeficientes binomiales

Clubr

Estoy luchando con la siguiente pregunta de una tarea para un curso de introducción a la combinatoria.

Muestre, por medio de un argumento combinatorio, que se cumple lo siguiente:
$\begin{aligned} {\binom{norte + 1}{k + 1}} & = \sum_{r = k}^{norte} (\binom{norte}{r}) {\binom{r}{k}} \end{aligned}$ $\begin{aligned} {n+1 \brace k+1}&=\sum_{r=k}^{n}\binom{n}{r} {r \brace k} \end{aligned}$

Usando la identidad familiar

{\binom{norte}{k}} = {\binom{norte - 1}{k - 1}} + k {\binom{norte}{k - 1}}

$\begin{equation} {n \brace k}={n-1 \brace k-1}+k{n \brace k-1} \end{equation}$

Puedo demostrar algebraicamente que

{\binom{norte + 1}{k + 1}} = \sum_{metro = k}^{norte} (k + 1)^{norte - metro} {\binom{metro}{k}} .

$\begin{equation} {n+1 \brace k+1}=\sum_{m=k}^{n}(k+1)^{n-m}{m \brace k}. \end{equation}$

Al hacer esto, esperaba poder introducir coeficientes binomiales para determinar si la definición recursiva del número de Stirling de segunda especie conduciría a una demostración algebraica. Desafortunadamente, los términos exponenciales permanecieron incluso después de sustituir

(k + 1)^{norte - metro} = \sum_{i = 1}^{norte - metro} (\binom{norte - metro}{i}) k^{i}

$\begin{equation} (k+1)^{n-m}=\sum_{i=1}^{n-m}\binom{n-m}{i}k^{i} \end{equation}$

lo que daría la definición:

{\binom{norte + 1}{k + 1}} = \sum_{metro = k}^{norte} [\sum_{i = 1}^{norte - metro} (\binom{norte - metro}{i}) k^{i}] {\binom{metro}{k}}

$\begin{equation} {n+1 \brace k+1}=\sum_{m=k}^{n} \left[ \sum_{i=1}^{n-m}\binom{n-m}{i}k^{i} \right] {m \brace k} \end{equation}$

Por supuesto, si hubiera tenido éxito, esperaba convertir este entendimiento en una modificación de la prueba combinatoria para la identidad recursiva, $S(n,k)=S(n-1,k-1)+kS(n-1,k)$ (donde hay dos casos: uno en el que $n$ es un singleton y el otro en el que $n \in A$ , dónde $|A|>1$ ).

Si alguien tiene alguna recomendación o sugerencia sobre cómo realizar la prueba combinatoria (o incluso la algebraica, que personalmente me interesa), ¡apreciaría mucho la ayuda!

Gracias

Respuestas (1)

Prueba combinatoria para series de números de Stirling y coeficientes binomiales

Marko Riedel · Answer 1

Comience por componer el reclamo usando convenciones estándar. Buscamos demostrar que

{\binom{norte + 1}{k + 1}} = \sum_{metro = k}^{norte} (\binom{norte}{metro}) {\binom{metro}{k}} .

${n+1 \brace k+1} = \sum_{m=k}^n {n\choose m} {m\brace k}.$

La demostración combinatoria es extremadamente sencilla. El lado izquierdo es el número de particiones de un conjunto de $n+1$ elementos distinguibles en $k+1$ subconjuntos indistinguibles. (Grupo de permutación $S_{k+1}$ y sin posicionamiento en los subconjuntos, un conjunto de conjuntos). El lado derecho cuenta la misma estadística. Supongamos que tenemos una partición en $k+1$ subconjuntos y el elemento con la etiqueta $n+1$ ha entrado en un subconjunto de tamaño $n-m+1$ . (Hay $n-m$ otros elementos en este subconjunto.) Entonces debemos haber elegido $m$ elementos del otro $n$ artículos para el otro $k$ subconjuntos y los dividió $m$ artículos en $k$ subconjuntos, dando una contribución de

(\binom{norte}{metro}) {\binom{metro}{k}} .

${n\choose m} {m\brace k}.$ La suma cuenta todos los tamaños de subconjuntos totales posibles para los subconjuntos que no contienen

n + 1

$n+1$ , a partir de

k

$k$ porque ninguno de los subconjuntos puede estar vacío.

La demostración algebraica utiliza funciones generadoras exponenciales. Recuerde que las particiones en subconjuntos tienen la siguiente especificación combinatoria:

PAG ({PAG}_{\geq 1} (Z)) .

$\mathfrak{P}(\mathfrak{P}_{\ge 1}(\mathcal{Z})).$ Esto implica inmediatamente que la función generadora de los números de Stirling de segunda clase es

GRAMO (z, tu) = Exp (tu (Exp (z) - 1)) .

$G(z, u) = \exp(u(\exp(z)-1)).$ Ahora tenemos

{\binom{norte + 1}{k + 1}} = (norte + 1)! [z^{norte + 1}] [{tu}^{k + 1}] Exp (tu (Exp (z) - 1)) = (norte + 1)! [z^{norte + 1}] \frac{(Exp (z) - 1)^{k + 1}}{(k + 1)!} .

${n+1 \brace k+1} = (n+1)! [z^{n+1}] [u^{k+1}] \exp(u(\exp(z)-1)) \\= (n+1)! [z^{n+1}] \frac{(\exp(z)-1)^{k+1}}{(k+1)!}.$ Este último término es

(norte + 1)! \frac{1}{norte + 1} [z^{norte}] {(\frac{(Exp (z) - 1)^{k + 1}}{(k + 1)!})}^{'} = norte! [z^{norte}] \frac{(k + 1) (Exp (z) - 1)^{k}}{(k + 1)!} Exp (z) = norte! [z^{norte}] Exp (z) \frac{(Exp (z) - 1)^{k}}{k!} .

$(n+1)! \frac{1}{n+1} [z^n] \left(\frac{(\exp(z)-1)^{k+1}}{(k+1)!}\right)'\\ = n! [z^n] \frac{(k+1)(\exp(z)-1)^k}{(k+1)!} \exp(z) = n! [z^n] \exp(z) \frac{(\exp(z)-1)^k}{k!}.$ Expandiendo el producto de las dos exponenciales esto produce

norte! \sum_{metro = 0}^{norte} \frac{1}{(norte - metro)!} [z^{metro}] \frac{(Exp (z) - 1)^{k}}{k!} = \sum_{metro = 0}^{norte} \frac{norte!}{metro! (norte - metro)!} metro! [z^{metro}] \frac{(Exp (z) - 1)^{k}}{k!} = \sum_{metro = 0}^{norte} \frac{norte!}{metro! (norte - metro)!} {\binom{metro}{k}} = \sum_{metro = k}^{norte} (\binom{norte}{metro}) {\binom{metro}{k}} .

$n! \sum_{m=0}^n \frac{1}{(n-m)!} [z^m] \frac{(\exp(z)-1)^k}{k!} = \sum_{m=0}^n \frac{n!}{m! (n-m)!} m! [z^m] \frac{(\exp(z)-1)^k}{k!} \\= \sum_{m=0}^n \frac{n!}{m! (n-m)!} {m \brace k} = \sum_{m=k}^n {n\choose m} {m \brace k}.$

Observe que la prueba combinatoria y la algebraica son muy similares.

Prueba combinatoria para series de números de Stirling y coeficientes binomiales

Clubr

Respuestas (1)

Marko Riedel

Marko Riedel

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}

Prueba combinatoria de la identidad 3n=∑nk=0(nk)2k3n=∑k=0n(nk)2k3^n=\sum_{k=0}^n \binom nk 2^k

¿Cuál es la prueba combinatoria para la fórmula de S(n,k)S(n,k)S(n,k) - Números de Stirling de segunda especie?

Interpretación combinatoria de la identidad: ∑j=0b(bj)2(n+j2b)=(nb)2∑j=0b(bj)2(n+j2b)=(nb)2\sum\limits_{j=0} ^b\binom{b}{j}^2\binom{n+j}{2b}=\binom{n}{b}^2

Cómo probar que (nr)(nr)n \choose r = n+1−rrn+1−rr\frac{n+1-r}{r} (nr−1)(nr−1)n \choose r -1 sin usar la expansión factorial de (nr)(nr)n \choose r? [cerrado]

Prueba combinatoria de que los coeficientes binomiales centrales son los más grandes

Prueba combinatoria para la identidad ∑nk=0(nk)(−2)k=(−1)n∑k=0n(nk)(−2)k=(−1)n\sum_{k=0}^n \binom{n}{k}\left(-2\right)^k = (-1)^n

Prueba combinatoria de identidad de tipo binomial

Verificación de la solución: Demuestre que ∑ni=0(n+an−i)(i+a+1i)=2n(n+aa)+2n−1(n+aa+1)∑i=0n(n+an− i)(i+a+1i)=2n(n+aa)+2n−1(n+aa+1)\sum_{i=0}^{n}{\binom{n+a}{ni}\ binom{i+a+1}{i}}=2^{n}\binom{n+a}{a}+2^{n-1}\binom{n+a}{a+1} para n ≥1n≥1n\geq 1

Prueba combinatoria de ∑k=0n(nk)3k=4n∑k=0n(nk)3k=4n\sum\limits_{k=0}^n {n \choose k}3^k=4^n