TransWikia.com

Found bounds for a sum of binom coefficients(generalization of Vandermonde's identity)

Mathematics Asked on December 6, 2021

I am trying to find some upper and lower bounds for the following expression:
$$sum_{v=0}^t {{x-v}choose{y}} cdot {xchoose{v}}cdot {z-x choose {t-v}}$$
Given that $x-t>y>0,z>x+t,tgeq 1$.

Finding the exact expression can be done only by hypergeometric function, which is not easy to compute:
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

Using Vandermonde’s identity, an upper bound is $${xchoose{y}}cdot {z choose {t}}$$ and a lower bound is

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

My question is there any better upperlower bounds, that are more tight?

3 Answers

I have solved my question independently to the algebraic solution presented here using combinatorics. I will prove that $$sum_{v=0}^t {{x-v}choose{y}} cdot {xchoose{v}}cdot {z-x choose {t-v}}={{x}choose{y}}cdot {z-y choose {t}} $$

We have $z$ balls, numbered from $1$ to $z$. Among them, $x$ of them are green and $z-x$ are red.

Lets count the number of options to select $y$ green balls, and then select $t$ balls (which can be either red or green) from the remaining $z-y$ balls. Selecting the $y$ green balls is called the first stage, and selecting the $t$ balls is the second stage.

The number of options in the first stage is ${{x}choose{y}}$, and the number of options of the second stage is ${z-y choose {t}}$. Thus, the number of options is $${{x}choose{y}}cdot {z-y choose {t}}.$$

Alternatively, we can count the number of options, given that we have selected $v$ green balls in the second stage (i.e., where $0leq vleq t$). There are ${{x}choose{v}}$ ways to choose these green balls. We then select ${{x-v}choose{y}}$ green balls for the first stage, and ${{z-x}choose{t-v}}$ for the red balls of the second stage. Thus the number of options is $$sum_{v=0}^t {{x-v}choose{y}} cdot {xchoose{v}}cdot {z-x choose {t-v}},$$

and that proves that both equations are equal.

Answered by user3563894 on December 6, 2021

There exists a closed-form exact solution for the following summation $S$ proposed in the OP:

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

As shown below, this is given by

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


To prove this solution, we can start by writing the binomials using factorials. Collecting the fixed factors (i.e. the terms not containing $v$) out the summation and simplifying we have

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

Rewriting the factors of the denominator in a different way, we have $$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!}$$

where $(k)_v$ indicates the Pochhammer symbol for rising factorial. Collecting the new fixed terms in the summation and noting that $(-t)_v/v!=(-1)^v binom tv$, we have

$$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}}$$

The sum can be expressed by a hypergeometric function, reminding that this function is defined by the power series

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

and that when either $a$ or $b$ is a nonpositive integer it reduces to the finite sum

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

So, setting $a=t$, $b=y-x$, $c=z-x-t+1$, $d=1$, and $n=v$, we get

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

which is equivalent to the expression given by WA in the link of the OP, with the only difference that here the sum starts from $v=0$.

Now we can use the well known identity

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

to get

$$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)}} $$

and then

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


As an example, let us set $x=6$, $y=2$, $z=10$, and $t=3$. The original summation gives

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

as shown by WA here. Accordingly

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

As another example with larger numbers, let us set $x=15$, $y=5$, $z=24$, and $t=8$. The original summation gives

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

as shown by WA here. Accordingly

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

Answered by Anatoly on December 6, 2021

Well, the summand is $$ {frac {x!, left( z-v right) !}{y!, left( x-v-y right) !,v!, left( t-v right) !, left( z-t right) !}} $$ where $(z-t)! le (z-v)! le (z-1)!$, $(x-t-y)! le (x-v-y)! le (x-1-y)!$, and $ (lfloor t/2 rfloor)! (lceil t/2 rceil)! le v! (t-v)! le t! $ so $$ 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)!}$$ Multiply left and right sides by $t$ to get lower and upper bounds.

Answered by Robert Israel on December 6, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP