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

Question

I am trying to find some upper and lower bounds for the following expression: $$\sum_{v=0}^t {{x-v}\choose{y}} \cdot {x\choose{v}}\cdot {z-x \choose {t-v}}$$ Given that $x-t>y>0,z>x+t,t\geq 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 $${x\choose{y}}\cdot {z \choose {t}}$$ and a lower bound is

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

My question is there any better upper\lower bounds, that are more tight?

Answer 1

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 =15\cdot 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} =3003\cdot 75582=226972746$$

Answer 2

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.

Answer 3

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 {x\choose{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 $0\leq v\leq 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 {x\choose{v}}\cdot {z-x \choose {t-v}},$$

and that proves that both equations are equal.