Definitions, Notation and Results

Definition 2.1   The cardinality of a set is the number of elements in the set. If a set has cardinality n, we often write n-set.

Notation 2.2   We use n! to denote the product $n(n-1)(n-2)\cdot 2\cdot 1$. It is read as n factorial. The numbers n! grow very rapidly. Some small values are 1! = 1, 2! = 2, 3! = 6, 4! = 24, 5! = 120, 6! = 720, and 7! = 5,040.

We adopt the convention that 0! = 1. This is done in order to simplify the statements of certain theorems. One useful fact to note about n!is that n! = n(n-1)!. Similarly, n! = n(n-1)(n-2)!. This observation allows some useful cancellation to take place when computing formulas involving factorials.

Notation 2.3   We use ${{n}\choose{k}}$ to denote the number of ways of selecting k distinct objects from n objects. Another common notation for this number is C(n,k). One standard way of reading it is to say ``n choose k''. It is also called a binomial coefficient.

The numbers ``n choose k'' occur all the time in counting problems because we frequently are choosing k objects in such a way that a given object may occur at most once (distinctness), and the order in which the objects are chosen is irrelevant. For example, when being dealt a hand of 5 cards, our main concern is with the final hand and not in the order in which we receive the cards. It is true that we may develop some anxiety as a hand develops if we watch each card as it arrives in our hand, but in analyzing our chances of winning the particular game, we start with the composition of the hand and do not consider the order in which they arrived.

Definition 2.4   A partition of a set A is a collection $A_1,A_2,\ldots,A_m$ of non-empty subsets of A such that

$$A=A_1\cup A_2\cup\cdots\cup A_m,$$

and

$$A_i\cap A_j=\emptyset$$

for all $i,j\in\{1,2,\ldots,m\}$, $i\neq j$. Each of the subsets in the collection is called a part of the partition.

The word partition makes sense for the previous concept because the set is being broken into non-empty pieces which have no overlap. This is one of the colloquial uses of the word partition as well.

Notation 2.5   We use $\pi(n;a_1,a_2,\ldots,a_m)$ to denote the number of ways of partitioning a given n-set into parts whose respective cardinalities are $a_1,a_2,\ldots,a_m$. In the case all mparts have the same cardinality k, we write $\pi(n;k^m)$ to denote the number of partitions of an n-set into m parts, where each part has cardinality k.