Results 1 to 5 of 5

Math Help - Multiset Addition Rule (proof required)

  1. #1
    Junior Member
    Joined
    Aug 2009
    Posts
    28

    Multiset 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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1783
    Awards
    1
    Quote Originally Posted by DaRush19 View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Aug 2009
    Posts
    28
    Quote Originally Posted by Plato View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1783
    Awards
    1
    Quote Originally Posted by DaRush19 View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Aug 2009
    Posts
    28
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Addition Rule- Extended
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: March 24th 2011, 04:36 PM
  2. Proof of k-multiset coefficients, part 1
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 19th 2010, 04:55 AM
  3. Probability; addition rule
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: January 25th 2009, 11:03 AM
  4. Probability Addition Rule Help!!!
    Posted in the Statistics Forum
    Replies: 1
    Last Post: January 30th 2007, 07:06 AM
  5. [SOLVED] Addition rule
    Posted in the Statistics Forum
    Replies: 1
    Last Post: April 24th 2006, 07:20 AM

Search Tags


/mathhelpforum @mathhelpforum