11 votos

Prueba de la identidad de Abel combinatoria

Pregunta

Derivar la identidad $$ \sum_{k}\binom{tk+r}{k}\binom{tn-tk+s}{n-k} \frac{r}{tk+r}=\binom{tn+r+s}{n}\tag0{}$$

Esta pregunta es de Aigner es Un curso en la Enumeración.

Contexto

Una construcción dada antes de este problema es útil en la determinación de la identidad.

A saber, cualquiera de generación de función $F(z)=\sum_{n\geq 0}a_n z^n$$a_0=1, a_1\neq 0$, define un polinomio secuencia $\exp(x\log F(z))=F(z)^x=\sum_{n\geq 0}p_{n}(x)z^n$ donde$p_n(1)=a_n$$p_n(0)=[n=0]$. Me mostró que $p_n$ es un polinomio de grado $n$ y que $$ p_n(x+y)=\sum_{k=0}^np_{k}(x)p_{n-k}(y)\etiqueta{1} $$ así como $$ (x+y)\sum_{k=0}^nkp_{k}(x)p_{n-k}(y)=nxp_n(x+y).\la etiqueta{2} $$ Mi intento

La ecuación (0) se veía como una manifestación de la convolución en (1) con $p_n(x)=\binom{tn+x}{n}$. Pero yo era incapaz de encontrar una expresión para $\sum_{n\geq 0 } \binom{tn+x}{n} z^n$ en forma cerrada. Es similar a $$ \sum_{n\geq 0}\binom{n+k}{n}z^n=\frac{1}{(1-z)^{k+1}} $$ pero el $tn$ en el coeficiente binomial es tirar los que me fuera.

Cualquier ayuda con un intento de utilizar el contexto descrito anteriormente, pero se prefiere otras soluciones son bienvenidos también.

5voto

Marko Riedel Puntos 19255

Vemos que nuestra identidad está en el hecho de

$$\sum_{k=0}^n {tk+r\elegir k} {tn-tk+s\elegir n-k} - \sum_{k=0}^n {tk+r\elegir k} {tn-tk+s\elegir n-k} \frac{tk}{tk+r} \\ = {tn+r+s\elegir n}.$$

Aunque sería preferible para resolver este uso formal de potencia de la serie sólo parece que tenemos complejo de variables para este. Con los números enteros $t,r,s \ge 1$ y empezando por la primera suma se introduce

$${tk+r\elegir k} = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{k+1}} (1+w)^{tk+r} \; dw$$

y

$${tn-tk+s\elegir n-k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-k+1}} (1+z)^{tn-tk+s} \; dz.$$

Esta última integral se desvanece al$k\gt n$, por lo que podemos extender la suma de el infinito, la obtención de

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{tn+s}}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^{r}}{w} \sum_{k\ge 0} z^k (1+z)^{-tk} \frac{1}{w^k} (1+w)^{tk} \; dw \; dz.$$

Ahora con $\epsilon$ $\gamma$ pequeña en un barrio de el origen obtenemos que para este convergen debemos tener $\epsilon/(1-\epsilon)^t \lt \gamma/(1+\gamma)^t.$ Vamos a ver que podemos resolver esto con un restricción adicional, a saber, que $\gamma \gt\epsilon.$ Haciendo el suma encontramos

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{tn+s}}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^{r}}{w} \frac{1}{1-z(1+w)^t/w/(1+z)^t} \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{tn+s}}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} (1+w)^{r} \frac{1}{w} {- z(1+w)^t/(1+z)^t} \; dw \; dz.$$

El polo en $w=0$ ha sido cancelado. Hay un poste en $w=z$ sin embargo y con los parámetros elegidos es en el interior del contorno. Tenemos para el residuo

$$\left.(1+w)^r \frac{1}{1-z(1+w)^{t-1}/(1+z)^t}\right|_{w=z} = (1+z)^r \frac{1}{1-z/(1+z)}$$

La derivada tendría que haber desaparecido si el poste no había sido fácil. Sustituyendo en el exterior de la integral obtenemos

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{tn+r+s+1}}{z^{n+1}} \frac{1}{1-(t-1)z} \; dz.$$

Continuando con la segunda suma obtenemos

$$\sum_{k=1}^n {tk+r\elegir k} {tn-tk+s\elegir n-k} \frac{tk}{tk+r} t = \sum_{k=1}^n {tk+r-1\elegir k-1} {tn-tk+s\elegir n-k} \\ = t \sum_{k=0}^{n-1} {tk+t+r-1\elegir k} {t(n-1)-tk+s\elegir (n-1)-k}.$$

Podemos reciclar el anterior cálculo y encontrar

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{t(n-1)+t+r-1+s+1}}{z^{n}} \frac{t}{1-(t-1)z} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{tn+r+s}}{z^{n+1}} \frac{z}{1-(t-1)z} \; dz.$$

Restando las dos, el resultado es

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{tn+r+s}}{z^{n+1}} \frac{(1+z)-z}{1-(t-1)z} \; dz = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{tn+r+s}}{z^{n+1}} \; dz.$$

Este evalúa a

$${tn+r+s\choose n}$$

por la inspección y hemos demostrado el teorema.

Para mostrar que el polo en $w=z$ es el único dentro del contorno aplicar Rouch del teorema de

$$h(w) = w(1+z)^t - z(1+w)^t$$

con $f(w) = w (1+z)^t$ $g(w) = z (1+w)^t.$ $|g(w)| < |f(w)|$ on $|w|=\gamma$ and since $f(w)$ tiene sólo una raíz que no lo qué $h(w)$, el cual debe ser$w=z.$, por lo que requieren

$$|g(w)| \le |z| (1+\gamma)^t \lt \gamma |1+z|^t = |f(w)|.$$

Ahora $\gamma/(1+\gamma)^t$ comienza en cero y se incrementa desde $(1+\gamma-\gamma t)/(1+\gamma)^{t+1}$ es positivo para $\gamma \lt 1/(t-1)$ with a local maximum there. Since $|z|/|1+z|^t \le \epsilon / (1-\epsilon)^t$ we may choose $\epsilon$ para que esto tenga un valor de el rango de $\gamma/(1+\gamma)^t$ $[0, 1/(t-1)].$ Crear instancias de $\gamma$ a la derecha de este punto se obtiene un valor de $\gt \epsilon$ que cumple los requisitos del teorema. Aquí tenemos utilizado que $\epsilon/(1+\epsilon)^t \lt \epsilon/(1-\epsilon)^t \lt \gamma/(1+\gamma)^t$ by construction. No need for Rouche when $t=1.$

3voto

Mike Earnest Puntos 4610

Aquí es una solución más acorde con Aigner consejos del. Mucho de esto es levantado directamente de Knuth de la Convolución de Polinomios, disponible en arXiv.


Estás tratando de usar$(1)$$p_n(x)=\binom{tn+x}{n}$, pero resulta que el método correcto es el uso de $(2)$ $$p_n(x)=\binom{tn+x}{n}\frac{x}{x+tn}.$$El resultado es $$ (x+y)\sum k\binom{tk+x}{k}\frac{x}{x+tk}\binom{t(n-k)+y}{n-k}\frac{y}{y+t(n-k)}=nx\binom{tn+x+y}{n}\frac{x+y}{x+y+tn} $$ La cancelación de la $x$$x+y$, y la aplicación de la absorción de identidades $\binom{tn+x+y}{n}=\frac{tn+x+y}{n}\binom{tn+x+y-1}{n-1}$, e $\binom{tk+x}{k}=\frac{tk+x}{k}\binom{tk+x-1}{k-1}$, obtenemos $$ \sum_k \binom{tk+x-1}{k-1}\binom{t(n-k)+y}{n-k}\frac{y}{y+t(n-k)}=\binom{tn+x+y-1}{n-1} $$ Finalmente, el resultado de la siguiente manera mediante la sustitución de $n$$n+1$, invirtiendo el orden de la suma de ($k\leftarrow n+1-k $), y la sustitución de $x$$x-t+1$.


Por supuesto, usted todavía tiene que encontrar una función $F(z)$ para los que $$F(z)^x=\sum_{n\ge0}p_n(x)z^n=\sum_{n\ge0}\binom{tn+x}{n}\frac{x}{tn+x}z^n\tag{*}.$$ It turns out that the answer is $$F(z)=\sum_{n\ge0}\binom{tn+1}{n}\frac{z^n}{tn+1}\tag{**}$$ Esta es una función que satisface $$ F(z) = 1+zF(z)^t\etiqueta{***} $$ Usted puede tomar (***) como una definición de la $F$, y recuperar (**) a través de Lagrange de la inversión. Knuth le da una interesante combinatoria prueba de cómo (**) implica (*) en Concreto de las Matemáticas, de la sección 7.5. Creo que debe haber una manera de mostrar (***) implica (*) a través de Lagrange de la inversión, pero hasta ahora no han tenido éxito.

1voto

Markus Scheuer Puntos 16133

Esta respuesta se basa en el Lagrange inversión teorema. Aquí se utiliza una variante de la que se afirma como G. 6 de Lagrange de la Inversión: ¿cómo y cuándo por D. Merlini, R. Sprugnoli y M. C. Verri. Se va como sigue:

Suponga $w=w(z)$ es un poder formal de la serie que es implícitamente da como $w=z\phi(w)$$\phi(0)\ne 0$. Entonces para cualquier poder formal de la serie de $F$ hemos \begin{align*} \sum_{k=0}^\infty\left([u^k]F(u)\phi(u)^k\right)w(z)^k=\left.\frac{F(w)}{1-z\phi^\prime (w)}\right|_{w=z\phi(w)}\tag{1} \end{align*} donde $[u^k]$ es el coeficiente de operador que denota el coeficiente de $u^k$ en una serie.

Empezamos con el lado izquierdo de la OPs identidad, la puso en una potencia de la serie $w=w(z)$ y observar que este es el Cauchy-producto de dos de alimentación de la serie. \begin{align*} \sum_{k=0}^\infty&\binom{tk+r}{k}\binom{tn-tk+s}{n-k}\frac{r}{tk+r}w^k\\ &=\left(\sum_{k=0}^\infty \binom{tk+r}{k}\frac{r}{tk+r} w^k\right)\left(\sum_{k=0}^\infty \binom{tk+s}{k} w^k\right)\tag{2} \end{align*}

Se derivan cerrado expresiones del poder formal de la serie en (2) a partir de la cual la reclamación fácilmente de la siguiente manera.

Empezamos con la mano derecha de la potencia de la serie en (2) y obtener \begin{align*} \color{blue}{\sum_{k=0}^\infty\binom{tk+s}{k}w(z)^k}&=\sum_{k=0}^\infty[u^k](1+u)^{tk+s}w(z)^k\tag{3}\\ &=\left.\frac{(1+w)^s}{1-zt(1+w)^{t-1}}\right|_{w=z(1+w)^t}\tag{4}\\ &=\left.\frac{(1+w)^s}{1-\frac{w}{(1+w)^t}t(1+w)^{t-1}}\right|_{w=z(1+w)^t}\tag{5}\\ &\,\,\color{blue}{=\left.\frac{(1+w)^s}{1-(t-1)w}\right|_{w=z(1+w)^t}}\tag{6} \end{align*}

Comentario:

  • En (3) se escribe el coeficiente binomial utilizando el coeficiente de operador y observar que podemos aplicar (1) con $\phi(w)=(1+w)^t$.

  • En (4) utilizamos el Lagrange inversión teorema (1) mediante el establecimiento $F(w)=(1+w)^s$.

  • En (5) hacemos la sustitución de $z=\frac{w}{(1+w)^t}$.

  • En (6) hacemos un poco de final de la simplificación.

Del mismo modo obtenemos un cerrado expresión para la mano izquierda de potencia de la serie en (2). Obtenemos \begin{align*} \color{blue}{\sum_{k=0}^\infty}&\color{blue}{\binom{tk+r}{k}\frac{r}{tk+r}w(z)^k}\\ &=\sum_{k=0}^\infty\left(\binom{tk+r}{k}-t\binom{tk+r-1}{k-1}\right)w(z)^k\tag{7}\\ &=\sum_{k=0}^\infty\left([u^k](1+u)^{tk+r}-t[u^{k-1}](1+u)^{tk+r-1}\right)w(z)^k\tag{8}\\ &=\sum_{k=0}^\infty\left([u^k](1-(t-1)u)(1+u)^{tk+r-1}\right)w(z)^k\tag{9}\\ &=\left.\frac{(1-(t-1)w)(1+w)^{r-1}}{1-zt(1+w)^{t-1}}\right|_{w=z(1+w)^t}\tag{10}\\ &=\left.\frac{(1-(t-1)w)(1+w)^{r-1}}{1-\frac{w}{(1+w)^t}t(1+w)^{t-1}}\right|_{w=z(1+w)^t}\tag{11}\\ &\,\,\color{blue}{=\left.(1+w)^r\right|_{w=z(1+w)^t}}\tag{12} \end{align*}

Comentario:

  • En (7) escribimos $\frac{r}{tk+r}=1-\frac{tk}{tk+r}$ y aplicar el binomio identidad $\binom{p}{q}=\frac{p}{q}\binom{p-1}{q-1}$.

  • En (8) se le aplica el coeficiente de operador dos veces.

  • En (9), usamos la linealidad del coeficiente de operador y aplicar la regla de $[u^p]u^qA(u)=[u^{p-q}]A(u)$.

  • En (10) funcionan de forma similar como el anterior y con $\phi(w)=(1+w)^t$$F(w)=(1-(t-1)w)(1-w)^{r-1}$.

  • En (11) hacemos la sustitución de $z=\frac{w}{(1+w)^t}$.

  • En (12) vamos a hacer algunos de final de la simplificación.

Poner las formas cerradas (6) y (12) juntos podemos obtener \begin{align*} \sum_{k=0}^\infty&\color{blue}{\binom{tk+r}{k}\binom{t(n-k)+s}{n-k}\frac{r}{tk+r}}w(z)^k\\ &=\left.\frac{(1+w)^{r+s}}{1-(t-1)w}\right|_{w=z(1+w)^t}\\ &=\sum_{k=0}^\infty\color{blue}{\binom{tk+r+s}{k}}w(z)^k \end{align*} donde el último paso de la siguiente manera debido a (6) y la demanda de la siguiente manera.

Nota: Esta derivación puede ser encontrado en una forma ligeramente diferente en el papel por D. Merlini et al. se hizo referencia anteriormente.

1voto

Marko Riedel Puntos 19255

Trabajando con la consulta al final de la aceptó respuesta que nos puede mostrar que con $x,t$ enteros positivos y

$$F(z) = 1 + z F(z)^t$$

que

$$F(z)^x = \sum_{n\ge 0} {tn+x\choose n} \frac{x}{tn+x} z^n$$

el uso de la de Lagrange-Buermann fórmula.

Ponemos a $w = F(z)-1$, de modo que $z=w/(w+1)^t$ y

$$[z^n] F(z)^x = \frac{1}{n} [w^{n-1}] x (w+1)^{x-1} (w+1)^{tn} \\ = \frac{x}{n} [w^{n-1}] (w+1)^{tn+x-1} = \frac{x}{n} {tn+x-1\elegir n-1} \\ = \frac{x}{tn+x} {tn+x\elegir n}.$$

como se reivindica. Aquí hemos utilizado la $H(w) = (w+1)^x$ en la notación de la entrada de la Wikipedia.

0voto

En primer lugar, el uso de vandermonde, obtenemos:

$$\binom{tn-tk+s}{n-k} = \sum_{j=k}^n\binom{tn + s + r}{n-j}\binom{-r-tk}{j-k}$$

LHS = $$\sum_{k=0}^n\frac{r}{tk+r}\binom{tk+r}{k}\binom{tn-tk+s}{n-k}$$

$$= \sum_{k=0}^n\frac{r}{tk+r}\binom{tk+r}{k}\sum_{j=k}^n\binom{tn + s + r}{n-j}\binom{-r-tk}{j-k}$$

$$= \sum_{j=0}^n\binom{tn + s + r}{n-j}\sum_{k=0}^j\frac{r}{tk+r}\binom{tk+r}{k}\binom{-r-tk}{j-k}$$

Para el término $\binom{-r-tk}{j-k}$, podemos negar la parte superior del índice: $\binom{r}{k} = (-1)^k \binom{k-r-1}{k}$

LHS = $$\sum_{j=0}^n\binom{tn + s + r}{n-j}\sum_{k=0}^j\frac{(-1)^{j-k}r}{tk+r}\binom{tk+r}{k}\binom{j-k + r+tk-1}{j-k}$$

Ahora $$\frac{r}{tk+r}\binom{tk+r}{k}\binom{j-k + r+tk-1}{j-k} = \frac{r}{tk+r}\frac{(tk+r)!}{(tk+r-k)!k!}\frac{(j-k+r+tk-1)!}{(tk+r-1)!(j-k)!}$$

La cancelación de la $(tk+r)!$ desde el numerador y el denominador, se obtiene:

$$\frac{r}{1}\frac{(j-k+r+tk-1)!}{(tk+r-k)!j!}\frac{j!}{k!(j-k)!}$$

Multiplicando num y den por $(j-k+r+tk)$, obtenemos

$$\frac{r}{(j-k+r+tk)}\binom{j}{k} \binom{j-k+r+tk}{j}$$

Conectando de nuevo en LHS, obtenemos:

LHS = $$\sum_{j=0}^n\binom{tn + s + r}{n-j}\sum_{k=0}^j\frac{(-1)^{j-k}r}{(j-k+r+tk)}\binom{j}{k} \binom{j-k+r+tk}{j}$$

Ahora viene el salto de la fe:

para $j>0$, el interior de la suma se convierte en $0$. [prueba]

Y así LHS = $\binom{tn + s + r}{n}$

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X