# Combinatorial Proof For Counting Equivalance

The questions asks to prove combinatorially.

${10}\choose{5}$ = ${4}\choose{4}$ + ${5}\choose{4}$ + ${6}\choose{4}$ + ${7}\choose{4}$ + ${8}\choose{4}$ + ${9}\choose{4}$

So I know that the LHS is choosing 5 objects from 10 objects.

If we let there be 4 objects and say 6 special objects.

The right side is:

${4}\choose{4}$ = Choose 4 from a 4 objects.

${5}\choose{4}$ = Choose 4 from 4 objects and 1 Special Object

${6}\choose{4}$ = Choose 4 from 4 objects and 2 special objects

${7}\choose{4}$ = Choose 4 from 4 objects and 3 special objects

${8}\choose{4}$ = Choose 4 from 4 objects and 4 special objects

${9}\choose{4}$ = Choose 4 from 4 objects and 5 special objects

Thus the right side counts the same thing as the left side. Does this work as a combinatorial proof? If not how could I improve my approach. Thank you.

• I have no idea what you mean by special objects, and so far you haven't done anything. You want to chose 5 numbers out of the set 1, 2, \dots, 10. The last number chosen is 10, 9, 8, 7, 6, or 5. Hence... – fredgoodman Mar 17 '18 at 20:28
• @fredgoodman Suppose, instead you had to choose 10 children and form a team of 5. These 10 children include 4 boys and 6 girls. Does that clear it up slightly? – Safder Aree Mar 17 '18 at 20:31
• It makes it clear that you are quite confused, as you have just told the story which goes with a completely different identity. – fredgoodman Mar 17 '18 at 20:45
• Yes. I am confused. – Safder Aree Mar 17 '18 at 20:47
• I am sorry you are confused. You may need to talk to someone face to face. Or else quietly ponder the hint given by Foobaz John. – fredgoodman Mar 17 '18 at 20:48

## 1 Answer

Hint

Partition the $5$ element subsets of $\Omega=\{1,2,\dotsc,10\}$ based on their maximum element. How many $5$ element subsets of $\Omega$ have $10$ as their maximum element, $9$ as their maximum element and so on?

• I'm having trouble understanding what to do here. – Safder Aree Mar 17 '18 at 20:38