COMBINATIONS
--------------------------

WANT FREE COACHING IN MATHS IN BANGALORE ?
CALL 9480193388 OR EMAIL freemaths10212@gmail.com

For details see post on 26-Feb-2015 at 6:00 am.

--------------------------
Let m and w be positive integers. Give a combinatorial argument to prove that for integers k ? 0,
SUM(from j=0 to k) C(m, j)*C(w, k-j) = C(m+w, k)
-----------------

CONSIDER 2 BASKETS OF FRUITS SAY ONE BASKET HAVING "M" NUMBER OF APPLES AND ANOTHER BASKET CONTAINING "W" NUMBER OF STRAW BERRIES , WITH BOTH M & W BEING POSITIVE INTEGERS ..LET THE FRUITS BE ALSO NUMBERED AS M1,M2,M3.....,MM ....AND ....W1,W2,W3, .....WW SO THAT THEY REMAIN DISTINCT FROM ONE ANOTHER ....

...... NOW SUPPOSE WE WANT TO MAKE A COLLECTION OF K DISTINCT FRUITS FROM BOTH BASKETS ...WE CAN DO THIS IN 2 WAYS ..

1...TAKE " J " NUMBER OF FRUITS FROM FROM BASKET ONE AND THEN TAKE THE REST OF "( K - J ) " FRUITS FROM BASKET 2 ...MAKING A TOTAL J FRUITS ....

IN THIS WAY ....IF WE TAKE ..

i)...J=0 FROM B1 & J=K FROM B2 , WE HAVE ...C[M,0]*C[W,K]...COMBINATIONS

ii)...J=1 FROM B1 & J=K-1 FROM B2 , WE HAVE ...C[M,1]*C[W,K-1]...COMBINATIONS

iii).....J=2 FROM B1 & J=K-2 FROM B2 , WE HAVE ...C[M,2]*C[W,K-2].COMBINATIONS

....ETC....TILLL.....

FOR ..J=K FROM B1 & J=0 FROM B2 , WE HAVE ...C[M,K]*C[W,0]...COMBINATIONS

=================

ADDING THEM ALL WE GET THE TOTAL NUMBER OF COMBINATIONS AS ....

C[M,0]*C[W,K] +C[M,1]*C[W,K-1] + C[M,2]*C[W,K-2]+....+ C[M,K]*C[W,0]

= SUM(from j=0 to k) [ C(m, j)*C(w, k-j)] ....THE LEFT SIDE OF THE GIVEN EQN. TO BE PROVED ..

NOW WE CAN DO THE SAME BY ANOTHER METHOD ...NAMELY ..

COMBINE THE 2 BASKETS OF FRUITS IN TO ONE AND SELECT K FRUITS FROM THE TOTAL OF M+W FRUITS ...THIS CAN BE DONE IN ..C [ M+W , K ] WAYS ..

OBVIOUSLY SINCE BOTH METHODS RESULT IN THE SAME OUT COME THEIR VALUES SHALL BE EQUAL ...SO WE CONCLUDE THAT ...

SUM(from j=0 to k) [ C(m, j)*C(w, k-j)] . = C[ M+W , K ]