Show that M(n,r) = M(n, r-1) + M(n-1, r) for n,r>=1 by acombinatorial argumentand by an algebraic argument using M(n,r) = C(n+r-1, r).

What combinatorial argument are they looking for here?

Printable View

- Aug 30th 2009, 03:54 AMDaRush19Multiset Addition Rule (proof required)
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 AMPlato
- Aug 31st 2009, 08:10 AMDaRush19
- Aug 31st 2009, 08:15 AMPlato
- Aug 31st 2009, 08:21 AMDaRush19
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.