Results 1 to 2 of 2

Math Help - Combinatorics Multiplication Principles

  1. #1
    Newbie
    Joined
    Jan 2013
    From
    Toronto
    Posts
    2

    Combinatorics Multiplication Principles

    Hi in my book the multiplication principle is stated as follows.

    Suppose a procedure can be broken into m successive ordered stages,with r1 different outcomes in the first stage
    r2 different out comes in the second stage... And rm different outcomes in the mth stage. if the number of ooutcomes at each stage is independent of the choices in the previous stages and if the composite outcomes are all distinct then the procedure has r1*r2....*rm different composite outcomes.

    But all the multiplication states theoretically is that |r1xr2x..xrm|= |r1|*|r2|*...*|rm|

    so when you use it don't you have to prove there is bijection between the thing that you are counting and some cross product of sets? Why is this always skipped?

    For example if you want to count the number of ways to put r distinct balls in n distinct boxes no restrictions on the number of balls in the box, traditionally you break it up into choosing the box for each ball. So there are n boxes for the first ball n for the second ect so the answer is n^r.

    But technically don't you have to show there is a bijection between the possible arrangements of the balls in the boxes and the cross product of the set of the boxes r times? I guess the purpose of the first part of the principle to set up a bijection but should you always trust it, can it be proven it always creates a bijecttive pairing?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2008
    Posts
    1,035
    Thanks
    49

    Re: Combinatorics Multiplication Principles

    Quote Originally Posted by rummi View Post
    But technically don't you have to show there is a bijection between the possible arrangements of the balls in the boxes and the cross product of the set of the boxes r times?
    Quote Originally Posted by rummi View Post
    don't you have to prove there is bijection between the thing that you are counting and some cross product of sets? Why is this always skipped?
    But the thing you are counting IS some cartesian (cross?) product of sets!

    E.g. the set of possible arrangements of the balls in the boxes IS the cartesian product of r sets of n positions.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: May 25th 2012, 04:14 PM
  2. Replies: 3
    Last Post: May 12th 2011, 06:30 AM
  3. Is the first principles?
    Posted in the Calculus Forum
    Replies: 2
    Last Post: April 21st 2010, 04:41 AM
  4. Replies: 2
    Last Post: June 8th 2008, 01:45 PM
  5. About 'first principles'
    Posted in the Calculus Forum
    Replies: 1
    Last Post: August 19th 2006, 06:57 AM

Search Tags


/mathhelpforum @mathhelpforum