# 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 * N_2 *...*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 *N_2 = 2 * 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 *N_2 *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 * 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\geq 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 * N_2 * ... * N_n = 2 * 2 * ... * 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 \rightarrow B$ are there?

Example of one function mapping from $A \rightarrow 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 \rightarrow B$ is one-to-one (injective) if for each $x,y \in A, x \neq y, f(x) \neq f(y)$

Not this

Question: How many one-to-one functions $f:A \rightarrow B$ are there?

Answer is 0 if $|A| \gt |B|$

What if $|A| \leq |B|$?


The procedure is similar


Answer = $n * (n-1) * (n-2) * ... * (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`