3 Permutations and Combinations

Theorem 3.1

✓

Suppose that a set \(S\) is partitioned into pairwise disjoint parts \(S_1,S_2, \ldots , S_m\). The number of objects in \(S\) can be determined by finding the number of objects in each of the parts, and adding the numbers so obtained:

\[ |S| = |S_1| + |S_2| + \cdots + |S_m| \]

Proof ▶

Theorem 3.2

✓

Let \(S\) be a set of ordered pairs \((a, b)\) of objects, where the first object \(a\) comes from a set of size \(p\), and for each choice of object a there are \(q\) choices for object \(b\). Then the size of \(S\) is \(p \times q\).

Proof ▶

Theorem 3.3

✓

Let \(A\) be a set and let \(U\) be a larger set containing \(A\). Let \(\overline{A} = U \setminus A = \{ x \in U : x \notin A \} \) be the complement of \(A\) in \(U\). Then the number \(|A|\) of objects in \(A\) is given by the rule: \(|A| = |U| - |\overline{A}|\).

Proof ▶

Theorem 3.4

✓

Let \(S\) be a finite set that is partitioned into \(k\) parts in such a way that each part contains the same number of objects. Then the number of parts in the partition is given by the rule: \(k = \frac{|S|}{\text{number of objects in a part}}\).

Proof ▶

Theorem 3.5

For \(n\) and \(r\) positive integers with \(r\leq n\),

\[ P(n,r) = n\times (n-1)\times \cdots \times (n-r+1). \]

Proof ▶

Theorem 3.6

The number of circular r-permutations of a set of \(n\) elements is given by

\[ \frac{P(n,r)}{r}=\frac{n!}{r\cdot (n-r)!}. \]

In particular, the number of circular permutations of \(n\) elements is \((n - 1)!\).

Proof ▶

Theorem 3.7

For \(0\leq r \leq n\),

\[ P(n,r)=r!\binom {n}{r} \]

Hence,

\[ \binom {n}{r} = \frac{n!}{r! (n-r)!}. \]

Proof ▶

Corollary 3.8

For \(0 \leq r \leq n\),

\[ \binom {n}{r} = \binom {n}{n-r}. \]

Proof ▶

Theorem 3.9

(Pascal’s formula) For all integers \(n\) and \(k\) with \(1 \leq k \leq n-1\),

\[ \binom {n}{k} = \binom {n-1}{k} + \binom {n-1}{k-1}. \]

Proof ▶

Theorem 3.10

For \(n \geq 0\),

\[ \binom {n}{0} + \binom {n}{1} + \binom {n}{2} + \cdots + \binom {n}{n} = 2 ^{n}, \]

and the common value equals the number of subsets of an n-element set.

Proof ▶

Theorem 3.11

Let \(S\) be a multiset with objects of \(k\) different types, where each object has an infinite repetition number. Then the number of r-permutations of \(S\) is \(k^{r}\).

Proof ▶

Theorem 3.12

Let \(S\) be a multiset with objects of \(k\) different types with finite repetition numbers \(n_1, n_2, ... , n_k\), respectively. Let the size of \(S\) be \(n = n_1 + n_2 + ... + n_k\). Then the number of permutations of \(S\) equals

\[ \frac{n!}{n_1!n_2!\dots n_k!}. \]

Proof ▶

Theorem 3.13

Let \(n\) be a positive integer and let \(n_1, n_2, ... ,n_k\) be positive integers with \(n = n_1 + n_2 + ... + n_k\). The number of ways to partition a set of \(n\) objects into \(k\) labeled boxes in which Box 1 contains \(n_1\) objects, Box 2 contains \(n_2\) objects, ..., Box k contains \(n_k\) objects equals

\[ \frac{n!}{n_1!n_2!\dots n_k!}. \]

If the boxes are not labeled, and \(n_1 = n_2 = ... = n_k\), then the number of partitions equals

\[ \frac{n!}{k!n_1!n_2!\dots n_k!}. \]

Proof ▶

Theorem 3.14

There are \(n\) rooks of \(k\) colors with \(n_1\) rooks of the first color, \(n_2\) rooks of the second color, . . . , and \(n_k\) rooks of the kth color. The number of ways to arrange these rooks on an n-by-n board so that no rook can attack another

\[ n!\frac{n!}{n_1!n_2!\cdots n_k!}=\frac{(n!)^2}{n_1!n_2!\cdots n_k!}. \]

Theorem 3.15

Let \(S\) be a multiset with objects of \(k\) types, each with an infinite repetition number. Then the number of r-combinations of \(S\) equals

\[ \binom {r+k-1}{r}=\binom {r+k-1}{k-1} \]

Proof ▶