[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
 Adition Principle:
if $\forall i \not= j, S_i \cap S_j = \emptyset$, we have $S = S_1 + S_2 + \cdots + S_n$.

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$.

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$.

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})$.
Categories: OI Note Mathematics Introductory Combinatorics
Leave a Reply