Combinatorial Proof For Counting Equivalance

65 Views Asked by At

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.

1

There are 1 best solutions below

1
On

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?