3
$\begingroup$

How do I show the following?

$$ \sum_{x=0}^{n} x {N_1 \choose {n-x}} {N_2 \choose x} = N_2 {N_1 + N_2 - 1 \choose n-1} $$

I tried breaking down the left hand side into factorials and pulling out $N_2$, but that did not help. How does one deal with these summmations in general?

$\endgroup$
2
  • $\begingroup$ Where did you see this from? One strategy for this kind of problem could be double counting. Count the same thing with two difference methods. $\endgroup$
    – Sarah
    Feb 4, 2017 at 6:59
  • $\begingroup$ You have a kind of convolution, so try to simplify the LHS to the Cauchy product of two sums. The identity $x\binom{N_2}{x}=N_2\binom{N_2-1}{x-1}$ and a change of index is the key. $\endgroup$
    – Masacroso
    Feb 4, 2017 at 8:56

5 Answers 5

3
$\begingroup$

$$ \binom{N_2}{x} = \frac{N_2}{x}\binom{N_2-1}{x-1} $$

With this, the sum gets transformed to

$$ \sum_{x=1}^n x\binom{N_1}{n-x}\binom{N_2}{x} = N_2\sum_{x=1}^n\binom{N_1}{n-x}\binom{N_2-1}{x-1}. $$

The rest is easy with a combinatorial argument. Starting the index with $0$ or $1$ doesn't make a difference.

$\endgroup$
1
  • $\begingroup$ $$\sum_{x=0}^nx\binom{N_1}{n-x}\binom{N_2}x=\sum_{x=1}^nx\binom{N_1}{n-x}\binom{N_2}x$$ $\endgroup$
    – bof
    Feb 4, 2017 at 7:34
2
$\begingroup$

There are $N_1$ men and $N_2$ women. You want to select a team of $n$ people; and from this team of $n$, select a leader who is a woman. How many ways can you do this?

(1) Pick a number $x$ between $1$ and $n$. Select $x$ women, then select a leader from these $x$, then select $n-x$ men. There are $$\sum_{x=1}^{n}{N_2\choose x}x{N_1\choose n-x}$$ ways to do this. This is the LHS of your identity (the $x=0$ term contributes nothing; if $x$ exceeds the number of women, then selecting $x$ women is impossible, but $N_2\choose x$ is zero as well.)

(2) Select a woman to be leader, then select $n-1$ people for the rest of the team. There are $$ N_2{N_1+N_2-1\choose n-1} $$ ways to do this. This is the RHS of your identity.

EDIT: You can generalize to the problem of selecting a team of $n$ people containing a subteam of $k$ women. The same argument gives: $$\sum_{x=k}^n{N_2\choose x}{x\choose k}{N_1\choose n-x}={N_2\choose k}{N_1+N_2-k\choose n-k}\tag1 $$

$\endgroup$
2
  • $\begingroup$ Is it possibly to modify this argument for $ \sum_{x=1}^{n}{N_2\choose x}x^2{N_1\choose n-x}$? $\endgroup$ Feb 4, 2017 at 12:45
  • $\begingroup$ @AgnishomChattopadhyay Yes, see edit. You should be able to derive an expression for $\sum_{x=1}^{n}{N_2\choose x}x^2{N_1\choose n-x}$ using two applications of (1) (with $k=2$ and $k=1$). $\endgroup$
    – grand_chat
    Feb 4, 2017 at 19:49
1
$\begingroup$

Just to complete the Nilabro Saha's answer we have $$ S=\sum_{k=0}^{n}k\dbinom{N_{1}}{n-k}\dbinom{N_{2}}{k}=N_{2}\sum_{k=0}^{n}\dbinom{N_{1}}{n-k}\dbinom{N_{2}-1}{k-1} $$ and using the Pascal's triangle $$S=N_{2}\sum_{k=0}^{n}\dbinom{N_{1}}{n-k}\dbinom{N_{2}}{k}-N_{2}\sum_{k=0}^{n}\dbinom{N_{1}}{n-k}\dbinom{N_{2}-1}{k} $$ and so using the Chu-Vandermonde identity we get $$S=N_{2}\left(\dbinom{N_{1}+N_{2}}{n}-\dbinom{N_{2}+N_{2}-1}{n}\right)=\color{red}{N_{2}\dbinom{N_{2}+N_{2}-1}{n-1}}$$ as wanted.

$\endgroup$
1
  • $\begingroup$ We could just have used a combinatorial argument. :-) $\endgroup$ Feb 4, 2017 at 15:27
1
$\begingroup$

Here is a technique based upon the coefficient of operator $[t^q]$ to denote the coefficient of $t^q$ in a series. This way we can write e.g. \begin{align*} \binom{p}{q}=[t^q](1+t)^p \end{align*}

We obtain \begin{align*} \sum_{x\geq 1}&x \binom{N_1}{n-x}\binom{N_2}{x}\tag{1}\\ &=N_2\sum_{x\geq 1}\binom{N_1}{n-x}\binom{N_2-1}{x-1}\tag{2}\\ &=N_2\sum_{x\geq 0}\binom{N_1}{n-x-1}\binom{N_2-1}{x}\tag{3}\\ &=N_2\sum_{x\geq 0}[t^{n-x-1}](1+t)^{N_1}[u^x](1+u)^{N_2-1}\tag{4}\\ &=N_2[t^{n-1}](1+t)^{N_1}\sum_{x\geq 0}t^{x}[u^x](1+u)^{N_2-1}\tag{5}\\ &=N_2[t^{n-1}](1+t)^{N_1}(1+t)^{N_2-1}\tag{6}\\ &=N_2[t^{n-1}](1+t)^{N_1+N_2-1}\\ &=N_2\binom{N_1+N_2-1}{n-1}\tag{7} \end{align*} and the claim follows.

Comment:

  • In (1) we start the index from $x=1$ due to the factor $x$ and we increase the upper limit to $\infty$ without changing anything, since we are adding zeros only.

  • In (2) we use the binomial identity $\binom{p}{q}=\frac{p}{q}\binom{p-1}{q-1}$.

  • In (3) we shift the index to start from $x=0$.

  • In (4) we apply the coefficient of operator twice.

  • In (5) we use the linearity of the coefficient of operator and use the rule \begin{align*} [t^{p-q}]A(t)=[t^p]t^qA(t) \end{align*}

  • In (6) we apply the substitution rule of the coefficient of operator with $u:=t$ \begin{align*} A(t)=\sum_{x=0}^\infty a_xt^x=\sum_{x=0}^\infty t^x[u^x]A(u) \end{align*}

  • In (7) we select the coefficient of $t^{n-1}$.

$\endgroup$
4
  • $\begingroup$ Verified and (+1). $\endgroup$ Feb 4, 2017 at 20:27
  • $\begingroup$ @MarkoRiedel: Thanks Marko! :-) $\endgroup$ Feb 4, 2017 at 20:27
  • $\begingroup$ Quite possibly we could profit from your help at this MSE link. $\endgroup$ Feb 4, 2017 at 23:31
  • $\begingroup$ @MarkoRiedel: Sorry, Marko. I've had a short look at the problem, but couldn't find anything helpful. In fact, I'm rather busy with some other interesting problems. There's even one question you've pointed to me last december. I've already calculated most of it, but hadn't found time to finalise and publish it. :-; Best, $\endgroup$ Feb 9, 2017 at 8:23
1
$\begingroup$

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \sum_{x = 0}^{n}x{N_{1} \choose n - x}{N_{2} \choose x} & = \sum_{x = 0}^{\infty}x{N_{2} \choose x}\ \overbrace{% \oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{N_{1}} \over z^{n - x + 1}} \,{\dd z \over 2\pi\ic}}^{\ds{N_{1} \choose n - x}} \\[5mm] & = \oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{N_{1}} \over z^{n + 1}}\ \overbrace{% \sum_{x = 0}^{\infty}{N_{2} \choose x}x\,z^{x}} ^{\ds{N_{2}\,z\,\pars{1 + z}^{N_{2} - 1}}}\ \,{\dd z \over 2\pi\ic} \\[5mm] & = N_{2}\oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{N_{1} + N_{2} - 1} \over z^{n}} \,{\dd z \over 2\pi\ic} = \bbx{\ds{N_{2}{N_{1} + N_{2} - 1 \choose n - 1}}} \end{align}

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .