# Multiset Addition Rule (proof required)

• Aug 30th 2009, 03:54 AM
DaRush19
Show that M(n,r) = M(n, r-1) + M(n-1, r) for n,r>=1 by a combinatorial argument and by an algebraic argument using M(n,r) = C(n+r-1, r).

What combinatorial argument are they looking for here?
• Aug 30th 2009, 04:07 AM
Plato
Quote:

Originally Posted by DaRush19
Show that M(n,r) = M(n, r-1) + M(n-1, r) for n,r>=1 by a combinatorial argument
What combinatorial argument are they looking for here?

Suppose you consider a class of n people, one of whom is David.
How many ways can a committee of r people be chosen?
Is that number the same as counting the committees having David as a member plus the number of committees not having David as a member?
• Aug 31st 2009, 08:10 AM
DaRush19
Quote:

Originally Posted by Plato
Suppose you consider a class of n people, one of whom is David.
How many ways can a committee of r people be chosen?
Is that number the same as counting the committees having David as a member plus the number of committees not having David as a member?

But how does this example (which I'm familiar with from combinations) work for multisets- since they contain identical objects?
• Aug 31st 2009, 08:15 AM
Plato
Quote:

Originally Posted by DaRush19
But how does this example (which I'm familiar with from combinations) work for multisets- since they contain identical objects?

Then this a missunderstanding about notation.
What does M(a,b) mean?
• Aug 31st 2009, 08:21 AM
DaRush19
It's the number of multisets (a set where repeated elements are allowed) containing r objects from a set containing n distinct objects. Or the number of ways to place r identical balls in n distinct boxes.