2 - Combinatorics, The Product Rule

Combinatorics

Combinatorics - a fancy word for counting

For us, determining the size of some set. We define the things we want to count as the elemtns of some set

$S$ and we want to determine the size of that set.

The product rule

If a procedure

$P$ has

$m$ steps (step 1, step 2…, step

$m$), we define the number of ways to execute the

$i$th step as

$N_i$. Then the number of ways to execute

$P$ is

$N_1\ast N_2\ast ...\ast N_m$

The number of ways of doing

$N_i$ does not depend on the previous steps.

Ex: Ordering fast food meals

2 steps when ordering fast food

1. Drink: Coke/Beer
2. Food: Burger/Club sandwhich/Chicken burger

Step 1: Choose Coke or Beer

$N_1=2$
Step 2: Choose a meal

$N_2=3$

$N_1\ast N_2=2\ast 3=6$ Different ways we can do this procedure

If

$P$ generates elements from some set

$S$ and

• (Onto) For each
  $x\in S$, there is an execution of
  $P$ that generates
  $x$ and
• (One-to-one) Any two different executions of
  $P$ generate distinct elements of
  $S$

Then

$|S|=N_1\ast N_2\ast N_m$

Ex:

Our set

$S$ is the set of meals

$S=\{(C,B),(C,CB),(C,CS),(B,B),(B,CB),(B,CS)\}$

$|S|=2\ast 3=6$

Less trivial example

Bitstrings

A bitstring is a sequence of 0's and 1's

$S_n$ is equal to the set of all bitstrings of length

$n$ (integers

$n\ge 0$)

$S_3=\{000,001,010,011,100,101,110,111\}$

$|S|=8$

We can count the number of bit strings for any given

$n$ using the product rule

# of ways to execute this prodcedure

$N_1\ast N_2\ast ...\ast N_n=2\ast 2\ast ...\ast 2=2^n$

This procedure is both onto and one-to-one so the cardinality of the set of every bitstring of length

$n$

$S_n$ =

$|S_n|=2^n$

Example with functions

Let

$A$ and

$B$ be two sets.

$|A|=m,|B|=n$

Question: How many functions

$f:A\to B$ are there?

Example of one function mapping from

$A\to B$

Procedure

Let

$x_1...x_m$ be the elements of

$A$ in some order

    for i = 1 to m:
        choose the value f(x_i) from B

• $m$ steps
• $N_1=n=N_2=N_3=...=N_m$

$\therefore$ # of executions is

$n^m$

Injective functions

A function

$f:A\to B$ is one-to-one (injective) if for each

$x,y\in A,x\ne y,f(x)\ne f(y)$

Not this

Question: How many one-to-one functions

$f:A\to B$ are there?

Answer is 0 if

$|A|>|B|$

What if

$|A|\le |B|$?

The procedure is similar

Answer =

$n\ast (n-1)\ast (n-2)\ast ...\ast (n-m+1)=n!/(n-m)!$

Unconventional example

We have

$m$ books

$B_1...B_m$
We have a bookcase with

$n$ shelves

We want to know how many ways can we place the books

$B_1...B_m$ onto the shelves

• Which books go on which shelves
• What order the books are on within each shelf

Procedure

for i = 1 to m:
    -Take B_i and either:
        - Choose a shelf j and make B_i on shelf j
        - Choose one of the previous placed books and place B_i immediately to the right

One possible ordering

As can be seen, the first book can go on any of the 4 shelves. The second book can go on any of the 4 shelves or to the right of the first book. The third book can go on any of the 4 shelves or to the right of the first or second book and this pattern continues.

Answer =

$(n+m-1)\times (n+m-2)\times ...\times (n)=(n+m-1)!/(n-1)!$

tags: COMP2804 Combinatorics