Re: combination


sunnewton wrote:
> Hi, dear all,
>
> I need to show the following:
>
> Cm0*Cnk+Cm1*Cn(k-1)+Cm2*Cn(k-2)+....CmK*Cn0=C(m+n)k
>
> Where Cmi means possible ways of selecting i items from m items.
>
> The meaning of the equation seems straitforward,,but I don't know how
> to show it...
>
> need help..

This smells like homework, so I'll only give a hint.

If A = {a_1, a_2, ..., a_m} and B = {b_1, b_2, ..., b_n}, then C(m+n,k)
is the number of subsets of A union B of size k.

C(m,r) is the number of subset of A of size r, and C(n,k-r) is the
number of subsets of B of size k-r. What does C(m,r) * C(n,k-r) count?
(When do you multiply the size of two sets together?)

Then add together C(m,r) * C(n,k-r) for all r between 0 and k; you get
the left-hand side of your equation. Why should this be the number of
subsets of A union B of size k? (When do you add sizes of sets
together?)

--- Christopher Heckman

.

Relevant Pages
Quantcast