Math Is Fun Forum

kous

Member

Registered: 2013-10-29

Posts: 2

Combinatorial Question

Need help, must use combinatorial proof, algebraic proof is not acceptable.

Bob

Administrator

Registered: 2010-06-20

Posts: 10,582

Re: Combinatorial Question

hi kous

Welcome to the forum.

I thought I'd make a simpler question first using numbers.

Take the letters in the word MATHS.

How many 3 letter words can we make, if order does not matter ?

5 C 3 = (5 x 4 x 3)/(3 x 2 x 1)  = 10

Here they are:

(i)  MAT    MAH   MAS   MTH   MTS   MHS

(ii)  ATH   ATS   AHS

(iii) THS

Now I've grouped them like this because

(i)       n-1 C r-1 = 6   and   

(ii)     n-2  C r-1  = 3   

(iii)   n-3  C r-1   =  r-1  C  r-1  = 1

In words

(i)   number of ways of picking 2 letters from 4 if the M has already been picked.

(ii)  number of ways of picking 2 letters from 3 if the M is now disallowed and the A has already been picked.

(iii)  number of ways of picking 2 letters from 2 if the M and A are now disallowed and the T has already been picked.

So now 'scale up' this approach to n objects picking r

(i)  Assume we have already picked the first object and compute n-1  C    r-1  to get the rest of these combinations.

(ii)  Now disallow that first object and assume we have already picked the second object and compute n-2  C r-1.

(iii) Now disallow both the first and second objects and assume we have already picked the third and compute n-3  C r-1

........and so on until we have just r objects left ........

(r) Disallow all but the last three objects, assuming we have picked the first of these three and compute r-1  C    r-1

Adding all of the above gives the RHS of the required formula.

But we also know that the calculation can be done using the LHS.

Hence we have a combinatorial proof. 

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

kous

Member

Registered: 2013-10-29

Posts: 2

Re: Combinatorial Question

Thank you so much!!! That is such a clear solution to the problem, makes perfect sense!