Prueba combinatoria de identidad de tipo binomial

Question

Prueba combinatoria de identidad de tipo binomial

Matemáticas
combinatoria
pruebas combinatorias
coeficientes binomiales

Un soloPANCAKE

Estoy buscando una prueba combinatoria para lo siguiente:

Fijar un entero positivo $n$ y un entero no negativo $k$ . Muestra esa
$\sum a_{1} \dots a_{k} = (\binom{norte + k - 1}{2 k - 1})$ $\sum a_1\dots a_k={n+k-1\choose 2k-1}$ donde la suma oscila sobre todos $k$ -tuplas $\left(a_1,\ldots,a_k\right)$ de enteros que satisfacen $a_1+\dots +a_k=n$ con $a_i\ge 0$ $\forall i\in [k]$ .

Aquí, $\left[k\right]$ denota el conjunto $\left\{1,2,\ldots,k\right\}$ .

Supongo que he estado mirando el lado derecho con una mentalidad de tipo "barras y estrellas" modificada. voy a escribir $n+k-1$ estrellas y luego circulo $2k-1$ de ellos. Barreré de izquierda a derecha, poniendo estrellas en un balde, y cuando llego al segundo círculo, lo atravieso con una línea para comenzar un nuevo balde. Continúo poniendo cosas en ese balde pasando la siguiente estrella dentro de un círculo y luego dibujando una línea a través de la siguiente. esto debería darme $k$ baldes con $a_i$ cosas en cada uno (y con el $\sum a_i=n$ ya que tachamos cada segunda estrella dentro de un círculo).

¿Es esta la biyección correcta en algún sentido? Entiendo lo que hice, pero no estoy seguro si entiendo por qué lo que hice está bien (si lo está). Es decir, ¿cuál es el procedimiento inverso y qué cuenta realmente el lado izquierdo?

Respuestas (2)

Prueba combinatoria de identidad de tipo binomial

Brian M Scott · Answer 1

Estás en el camino correcto. El $k-1$ las estrellas en un círculo en las posiciones pares son los límites entre su $k$ baldes, y el otro $k$ las estrellas en un círculo eligen un elemento específico de cada cubo. De este modo, $\binom{n+k-1}{2k-1}$ cuenta el número de formas de dividir $n$ cosas en $k$ baldes y elige una cosa de cada balde.

Ahora considere un vector particular de contenidos, $\langle a_1,\dots,a_k\rangle$ , significado $a_i$ cosas en el $i$ -th balde. ¿Cuántas veces se contará este vector en ese coeficiente binomial? Una vez por cada forma de elegir un objeto de cada cubo, y hay $a_1a_2\dots a_k$ maneras de hacer eso. Así, el vector de contenido $\langle a_1,\dots,a_k\rangle$ se cuenta $a_1a_2\dots a_k$ veces en el coeficiente binomial. Y en el lado izquierdo simplemente está sumando esos productos sobre todos los vectores de contenido posibles.

(Identidad interesante; no la había visto antes).

Desde una vista de función generadora, el lado izquierdo es solo el $n$ coeficiente de ${(\frac{z}{(1 - z)^{2}})}^{k}$ $\left(\frac{z}{(1-z)^2}\right)^k$
Gracias señor, muy útil. La identidad provino de un problema en la Combinatoria enumerativa de Stanley.
@AsinglePANCAKE: De nada. (Debería haberlo adivinado: ¡un día de estos voy a tener que echarle un vistazo a fondo a ese libro!)

robarjohn · Answer 2

Tenga en cuenta que

\begin{matrix} (1) & 1 X^{1} + 2 X^{2} + 3 X^{3} + 4 X^{4} + \dots = \frac{X}{(1 - X)^{2}} \end{matrix}

$1x^1+2x^2+3x^3+4x^4+\dots=\frac{x}{(1-x)^2}\tag{1}$ si levantamos

(1)

$(1)$ hacia

k^{th}

$k^{\text{th}}$ potencia, el coeficiente de

x^{n}

$x^n$ sería la suma de todos los productos de

k

$k$ enteros positivos que suman

n

$n$ . Es decir, queremos encontrar el coeficiente de

x^{n - k}

$x^{n-k}$ en

(1 - x)^{- 2 k}

$(1-x)^{-2k}$ :

\begin{aligned} (- 1)^{norte - k} (\binom{- 2 k}{norte - k}) & = (\binom{norte + k - 1}{norte - k}) \\ (2) & = (\binom{norte + k - 1}{2 k - 1}) \end{aligned}

$\begin{align} (-1)^{n-k}\binom{-2k}{n-k} &=\binom{n+k-1}{n-k}\\[6pt] &=\binom{n+k-1}{2k-1}\tag{2} \end{align}$

Prueba combinatoria de identidad de tipo binomial

Un soloPANCAKE

Respuestas (2)

Brian M Scott

Tomas Andrews

Un soloPANCAKE

Brian M Scott

robarjohn

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

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

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

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

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}

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