Thread: 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?

Originally Posted by rummi

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?

Originally Posted by rummi

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.