4
$\begingroup$

I am struggling on how to approach combinatoric proof problems. The identity to prove is $$\binom{10}{5} = \binom{8}{3} + \binom{8}{4} +\binom{8}{4} + \binom{8}{5}$$

I can prove this algebraically but the question says prove combinatorially. I also could use pascals identity to solve the RHS to the LHS.

How would I describe this combinatorially? Any guidance would be greatly appreciated.

$\endgroup$

2 Answers 2

8
$\begingroup$

Think of $\binom{10}{5}$ as the number of ways to choose a team of $5$ children from a group of $10$.

Now suppose we have a group of $8$ girls and $2$ boys, Matthew and Paul. $\binom{8}{5}$ counts how many teams have $5$ girls. $\binom{8}{4}$ counts how many teams have $4$ girls and Matthew. $\binom{8}{4}$ counts how many teams have $4$ girls and Paul. $\binom{8}{3}$ counts how many teams have $3$ girls and both Matthew and Paul.

$\endgroup$
0
6
$\begingroup$

There are a few standard combinatorial interpretations of $\binom nk$. Let's try one: suppose $\binom{10}5$ refers to the number of ways to pick $5$ objects from among $10$.

The right side speaks of picking from among $8$. To match the left side, let's assume we have $8$ objects plus $2$ special objects, and we're looking for the number of ways to pick a total of $5$ from among that group. Can you see how you get the expression on the right?

$\endgroup$
2
  • $\begingroup$ I understand the the 10 choose 5. However I don't quite understand how the extra 2 becomes the RHS identity. Could you elaborate for me please? $\endgroup$ Commented Mar 12, 2018 at 16:45
  • 1
    $\begingroup$ @SafderAree Let's say we have objects A, B, plus 8 more objects. We now have four cases for choosing a group of 5: AB+3, A+4, B+4, and 5 without choosing A or B. $\endgroup$
    – BallBoy
    Commented Mar 12, 2018 at 16:54

You must log in to answer this question.

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