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?
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?
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.