[latexpage]

Chapter 2: Permutation and Combination

This is a reading note of Introductory Combinatorics by Richard A. Brualdi.

There are several important aspects within this chapter that I will include in this.

• Four Basic Counting Principle
• Permutation & Combination within Single Set
• Permutation & Combination within Multiple Sets
• Finite Possibility

Introduction to Set

We define a partition of a set $S = S_1 \cup S_2 \cup S_3 \cdots \cup S_n$ and $S_i \cap S_j = \emptyset (i \not=j)$. We also define the number of elements in $S_i$ as $|S_i|$.

Four Basic Counting Principle

1. Adition Principle:

   if $\forall i \not= j, S_i \cap S_j = \emptyset$, we have $|S| = |S_1| + |S_2| + \cdots + |S_n|$.

2. Multiplication Principle:

   If there are n sets, then the ways of choosing a ordered sequence $(a_1,a_2,a_3,\cdots,a_n)$ is $|S_1| \times |S_2| \times |S_3| \times \cdots \times |S_n|$.

3. Subtraction Principle:

   Let $A$ be a set, and $U$ be a larger set which includes set $A$. Let $\bar{A} = U\space \backslash\space A = {x \in U : x \notin A} $. We call $\bar{A}$ a complement of the original set $A$. We can also know that $|\bar{A}| = |U| – |A|$.

4. Division Principle:

   Let set $S$ be a finite set, if we divide the set into $k$ parititions with identical number of elements, then we have $|S_i| = \frac{|S|}{k}, 1 \leq i \leq k$ .

Permutation & Combination within Single Set

Permutation

<

p>Given a set $S$ , we want to count the ways of arranging $r$ of its elements into a sequence, then we define it as $P(n,r) = \Pi_{n – r + 1}^{n}$. Also, specifically, we define $0! = 1$.

Corollary:

If we arrange $r$ elements into a circle, then we have the ways of arrangment are $\frac{P(n,r)}{r} = \frac{n!}{r \cdot (n – r)!}$. By a simple observation, we can see that the $n$ circular arrangement of a set size $n$ is $(n – 1)!$.

Combination

Given a set $S$, we want to choose a unordered subset $A$ which has size $r$ from it, the number of ways is denoted as $\binom{n}{r} = \frac{n!}{r!(n – r)!}$.

Pascal Theorem: $\binom{n}{k} = \binom{n – 1}{k} + \binom{n – 1}{k – 1}$

The proof of above theorem can be done by substituting the variables into the combination calculation formula.

Colloary:

The number of subsets of $S$ is $\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^n$, where $n = |S|$.

Permutation & Combination within Multiple Sets

Permutation within Multiple Sets

Given $n$ sets $S_1, S_2,\cdots,S_n$, we have following two ways of counting formulas for permutation:

• If in set $S_i$ the number of elements within is infinite, then the ways of putting them into a sequence length $r$ is $n^r$ .
• If for all set $S_i$ the number of elements is finite, then the ways of putting all of the elements into a sequence is $\frac{(\sum_{i = 1}^{n}|S_i|)!}{\Pi_{i = 1}^{n}|S_i|!}$ .

Combination within Multiple Sets

Given $n$ sets $S_1, S_2,\cdots,S_n$, we have following counting formulas for combination:

• If in set $S_i$ the number of elements within is infinite, then the ways of putting them into a set sized $r$ is $\binom{r + n – 1}{r}$.

The method of counting ways of arranging finite sets is included in Chapter 6, so it will not be discussed here.

Finite Possibility

• For a sample space(can be understood as event set) $S$, if every sample can occur with equal possibility, then we say this experiment as random. We define the possibility of occurence of a sample in set $S$ is $Pr(x_i) = \frac{1}{|S|} \space\space (x_i \in S)$.

  We can push this further by defining a set of event set $E \subseteq S$ and the possibility of any event in set $E$ is $Pr(E) = \frac{|E|}{|S|}$.

  Note that we can also apply subtraction theorem in this, $Pr(\bar{E}) = 1 – Pr(E) \leftrightarrow Pr(E) = 1 – Pr(\bar{E})$.