0
$\begingroup$

By counting the same set in two different ways (a combinatorial proof), prove that

$\Sigma_{k=1}^n$${k}\choose {m}$${n}\choose {k}$ = ${n}\choose {m}$$2^{n-m}$

I'm completely unsure about how to approach this problem. The above was all I was given but I'm unsure because I feel like $m$ is ambiguous and also what if $k$ is less than $m$.

Any advice or proofs appreciated!

$\endgroup$
2
  • 1
    $\begingroup$ Usually when $k < m$ we say that $\binom{k}{m} = 0$ (namely, there are 0 ways to choose $m$ elements from a $k$ element set). $\endgroup$
    – Mees de Vries
    Sep 6, 2016 at 21:51
  • 2
    $\begingroup$ Technically, it is only true for $m>0$. This can be fixed by adding the $k=0$ term to the left side. $\endgroup$
    – Thomas Andrews
    Sep 6, 2016 at 21:54

2 Answers 2

Reset to default
2
$\begingroup$

Suppose we want to choose 2 teams to play each other from a set of $n$ people,

where the first team has $m$ players.

1) On the right side, you are first selecting the players on the first team and then selecting some subset $\;\;\;$(possibly empty) of the remaining players as the second team.

2) On the left side, you are first selecting all the $k$ players, and then selecting the $m$ members of team 1 from $\;\;\;$among them.

(As Thomas Andrews points out, this is valid if $m>0$ for the formula as written.)

$\endgroup$
1
$\begingroup$

Here is a model for the counting:

RHS: Let there be $n$ boxes. In each box there is a white and a red ball. Now select $m$ of the boxes and pick precisely one ball from each of the remaining $n-m$ boxes.

LHS: Select first $k$ boxes among the $n$ and pick the red ball from the rest. Now select $m$ boxes among the $k$ and pick the white ball from the rest. (so in particular, $m\leq k \leq n$ and sum over $k$).

$\endgroup$

You must log in to answer this question.

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