2 votos

Límites encontrados para una suma de coeficientes binómicos(generalización de la identidad de Vandermonde)

Estoy tratando de encontrar algunos límites superior e inferior para la siguiente expresión: $$\sum_{v=0}^t {{x-v}\choose{y}} \cdot {x\choose{v}}\cdot {z-x \choose {t-v}}$$ Dado que $x-t>y>0,z>x+t,t\geq 1$ .

La expresión exacta sólo puede obtenerse mediante la función hipergeométrica, que no es fácil de calcular: https://www.wolframalpha.com/input/?i=approx+sum_%28v%3D1%29%5Et++%28%28%28x-v%29+choose+y%29*%28x+choose+v%29*%28%28z-x%29+choose+t-v

Utilizando la identidad de Vandermonde, un límite superior es $${x\choose{y}}\cdot {z \choose {t}}$$ y un límite inferior es

$${x-t\choose{y}}\cdot {z \choose {t}}$$

Mi pregunta es si hay algo mejor \lower ¿que son más estrechas?

1voto

Matthew Scouten Puntos 2518

Bueno, el sumando es $$ {\frac {x!\, \left( z-v \right) !}{y!\, \left( x-v-y \right) !\,v!\, \left( t-v \right) !\, \left( z-t \right) !}} $$ donde $(z-t)! \le (z-v)! \le (z-1)!$ , $(x-t-y)! \le (x-v-y)! \le (x-1-y)!$ , y $ (\lfloor t/2 \rfloor)! (\lceil t/2 \rceil)! \le v! (t-v)! \le t! $ así que $$ \frac{x!}{y! (x-1-y)! t!} \le {\frac {x!\, \left( z-v \right) !}{y!\, \left( x-v-y \right) !\,v!\, \left( t-v \right) !\, \left( z-t \right) !}} \le \frac{x! (z-1)!}{y! (x-t-y)! (\lfloor t/2 \rfloor)! (\lceil t/2 \rceil)! (z-t)!}$$ Multiplica los lados izquierdo y derecho por $t$ para obtener los límites inferior y superior.

1voto

user90997 Puntos 1

Existe una solución exacta de forma cerrada para el siguiente sumatorio $S$ propuesto en el PO:

$$\sum_{v=0}^t \binom{x-v} y \binom xv \binom{z-x}{t-v}$$

Como se muestra a continuación, esto viene dado por

$$S=\binom xy \binom {z-y}{t} $$


Para probar esta solución, podemos empezar escribiendo los binomios utilizando factoriales. Recogiendo los factores fijos (es decir, los términos que no contienen $v$ ) fuera la suma y simplificando tenemos

$$S= \frac{x!(z-x)!}{ y!} \sum_{v=1}^t \frac{1}{(t-v)!\,(x-y-v)!\,\, (z-x-t+v)!v!}\\$$

Reescribiendo los factores del denominador de otra manera, tenemos $$S= \frac{x!(z-x)!}{ y!} \sum _{v=1}^{t} \frac {(-t)_{v}}{t!} \,\frac{[-(x-y)]_{v}}{(x-y)!}\, \frac{1}{(z-x-t+1)_{v}(z-x-t)!}\, \frac{1}{v!}$$

donde $(k)_v$ indica el símbolo de Pochhammer para el factorial ascendente. Recogiendo los nuevos términos fijos en el sumatorio y observando que $(-t)_v/v!=(-1)^v \binom tv$ tenemos

$$S=\frac{x!(z-x)!}{t!\,y!\,(x-y)!(z-x-t)!} \\ \sum _{v=0}^{t} (-1)^v \binom tv \,\frac{(y-x)_{v}} {(z-x-t+1)_{v}}\\ =\binom xy \binom {z-x}{t}\\ \sum _{v=0}^{t} (-1)^v \binom tv \,\frac{(y-x)_{v}} {(z-x-t+1)_{v}}$$

La suma puede expresarse mediante una función hipergeométrica, recordando que esta función está definida por la serie de potencias

$${\displaystyle {}_{2}F_{1}(a,b,c;d)=\sum _{n=0}^{\infty }{\frac {(a)_{n}(b)_{n}}{(c)_{n}}}{\frac {d^{n}}{n!}}}$$

y que cuando $a$ o $b$ es un entero no positivo se reduce a la suma finita

$$\displaystyle {}_{2}F_{1}(-a,b,c;z)=\sum _{n=0}^{a}(-1)^{n}{\binom {a}{n}}{\frac {(b)_{n}}{(c)_{n}}}z^{n}$$

Por lo tanto, establecer $a=t$ , $b=y-x$ , $c=z-x-t+1$ , $d=1$ y $n=v$ obtenemos

$$S=\binom xy \binom {z-x}{t} \\ 2F_1(-t,y-x,z-x-t+1;1)$$

que es equivalente a la expresión dada por WA en el enlace del OP, con la única diferencia de que aquí la suma parte de $v=0$ .

Ahora podemos utilizar la conocida identidad

$$\displaystyle {}_{2}F_{1}(a,b;c;1)={\frac {\Gamma (c)\Gamma (c-a-b)}{\Gamma (c-a)\Gamma (c-b)}}$$

para obtener

$$S=\binom xy \binom {z-x}{t} \\ {\frac {\Gamma (z-x-t+1)\Gamma (z-y+1)}{\Gamma (z-x+1)\Gamma (z-y-t+1)}} $$

y luego

$$S=\binom xy \binom {z-x}{t} {\frac { (z-x-t)! (z-y)!}{ (z-x)!(z-y-t)!}} \\ =\binom xy \binom {z-y}{t} $$


Como ejemplo, pongamos $x=6$ , $y=2$ , $z=10$ y $t=3$ . La suma original da

$$\sum_{v=0}^3 \binom{6-v} 2 \binom 6v \binom{4}{3-v}=840$$

como muestra WA aquí . En consecuencia

$$\binom 62 \binom 83 =15\cdot 56=840$$

Como otro ejemplo con números más grandes, pongamos $x=15$ , $y=5$ , $z=24$ y $t=8$ . La suma original da

$$\sum_{v=0}^8 \binom{15-v} 5 \binom {15}v \binom{9}{8-v}=226972746$$

como muestra WA aquí . En consecuencia

$$\binom {15}5 \binom {19}{8} =3003\cdot 75582=226972746$$

0voto

user3563894 Puntos 21

He resuelto mi pregunta independientemente a la solución algebraica presentada aquí usando combinatoria. Demostraré que $$\sum_{v=0}^t {{x-v}\choose{y}} \cdot {x\choose{v}}\cdot {z-x \choose {t-v}}={{x}\choose{y}}\cdot {z-y \choose {t}} $$

Tenemos $z$ bolas, numeradas de $1$ a $z$ . Entre ellas, $x$ de ellos son verdes y $z-x$ son rojos.

Contemos el número de opciones a seleccionar $y$ bolas verdes y, a continuación, seleccione $t$ bolas (que pueden ser rojas o verdes) de las restantes $z-y$ bolas. Seleccionando el $y$ bolas verdes se denomina primera etapa y seleccionando $t$ bolas es el segunda fase .

El número de opciones en la primera etapa es ${{x}\choose{y}}$ y el número de opciones de la segunda etapa es ${z-y \choose {t}}$ . Por lo tanto, el número de opciones es $${{x}\choose{y}}\cdot {z-y \choose {t}}.$$

Alternativamente, podemos contar el número de opciones, dado que hemos seleccionado $v$ bolas verdes en la segunda etapa (es decir, donde $0\leq v\leq t$ ). Existen ${{x}\choose{v}}$ formas de elegir estas bolas verdes. A continuación, seleccionamos ${{x-v}\choose{y}}$ bolas verdes para la primera etapa, y ${{z-x}\choose{t-v}}$ para las bolas rojas de la segunda etapa. Por tanto, el número de opciones es $$\sum_{v=0}^t {{x-v}\choose{y}} \cdot {x\choose{v}}\cdot {z-x \choose {t-v}},$$

y eso demuestra que ambas ecuaciones son iguales.

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