这是台湾清华赵启超教授离散数学9A9B课程的笔记。

• Enumeration 9A
  • Principles of Counting
    • 加法原理和乘法原理
      • Addition Principle
      • Multiplication Principle
    • Ordered Selections with Repetition
    • Ordered Selections without Repetition
• Enumeration 9B
  *
  • Permutations
  • Unordered Selections with Repetition

Enumeration 9A

Principles of Counting

加法原理和乘法原理

Addition Principle

If $A$ and $B$ are finite sets and $A \cap B =\emptyset$, that is $A$ and $B$ are disjoint, then $|A \cup B| =|A|+|B|$.

Multiplication Principle

If $A$ and $B$ are finite sets, then $|A \times B| =|A||B|$.
Recall that $A \times B =\{(a,b):a\in A, b\in B \}$.

Ordered Selections with Repetition

The number of ordered selections, repetition allowed, of $m$ things from a set of size $n$ is $n^m$

Example 1
$|A|=m$ and $|B|=n$. Let $F$ donote the set of functions from $A$ to $B$.
$F=n \cdot n \cdot n\cdot \dotsc n=n^m$

Example 2
$|S|=n$. Power set of $S$ is $P(S)=2\cdot 2\cdot \dotsc 2 = 2^n$

Ordered Selections without Repetition

The number of ordered selections, without repetition, of $m$ things from a set of size $n$ is $n(n-1)(n-2)\dotsc (n-m+1)$

Enumeration 9B

Example 3
$|A|=m$ and $|B|=n$
How many injective(one-to-one) functions from A to B are there?
Answer: $n(n-1)(n-2)\dotsc (n-m+1)$

Permutations

A permutation of a nonempty finite set $A$ is a bijection from $A$ to $A$.
(Frequently, we take $A=\mathbb{N}_n=\{1,2,\dotsc ,n\}$).

Example 4
$n=5$ and $\alpha(1)=2, \alpha(2)=4, \alpha(3)=5, \alpha(4)=1, \alpha(5)=3$,
that is
$\alpha=\begin{pmatrix} 1 & 2 & 3& 4 & 5\\ 2 &4 &5 & 1&3 \end{pmatrix}$
$\alpha$ is a permutation.

Denote the set of all permutations of $\mathbb{N}_n$ by $S_n$
$|S_n|=n(n-1)\dotsc 1=n!$ (n! is read as n factorial)
$n!\overset{\bigtriangleup }{=} n(n-1)!$ when$n>1$
$0!\overset{\bigtriangleup }{=} 1$

Example 5
Given 10 people $p_1, p_2, \dotsc , p_{10}$.

1. In how many ways can the people be lined up in a row?
   Answer: $10!=3628800$
2. How may lineups are there if $p_2, p_6, p_9$ want to stand together?
   Answer: Let $G=\{ p_2, p_6, p_9\}$ of permutations in $\{ p_1, p_3, p_4, p_5, p_7, p_8, p_{10}, G\}$ , $G= 3!$
   Total of desired permutations = $8!\cdot 3! = 241920$.

Unordered Selections with Repetition

In next Note