4.1. Enumeration

I use the following convention throughout this chapter: for $n$, a natural number, $n=\{0,1,\dots ,n-1\}$ when $n>0$, and $0=\varnothing$.

Previously in this course, it was established that there are exactly $n^k$ functions from any set of size $k$ to any set of size $n$. Let me show you an example. Consider the following set of distinct objects.

$$X=\{A,B,C,D\}$$

In how many ways can you choose two objects from $X$? I have to be more specific. For example, are you allowed to grab the same element twice, e.g. $AA$? Am I distinguishing $AB$ from $BA$?

In general, without further specification, there are $|X^2|=|X{|}^2=4^2=16$ ways to make a selection. But maybe not all of them are relevant for your purposes.

AA	AB	AC	AD
BA	BB	BC	BD
CA	CB	CC	CD
DA	DB	DC	DD
The diagonal $AA,BB,CC,DD$ contains the repeated elements. The highlighted selections consist of those where order is not distinguished and repetitions are not counted. In this example, there are $\frac{12}{2}=6$ such selections.

Definition.

Denote by $P{R}_k^n$ the number of choices of $k$ elements from a set of size $n$ with repetitions and with order.

Denote by $P_k^n$ the number of choices of $k$ elements from a set of size $n$ with no repetitions and with order.

Based in my previous discussion, $P{R}_k^n=n^k$.

Theorem.

For $k\le n$,

$$P_k^n=\frac{n!}{(n-k)!}$$

Informal proof:

Proceed by induction on $n$. The base case $n=0$ is clear since $0!=1$.

The inductive step follows from the observation that $P_k^n=n\cdot P_{k-1}^{n-1}$. Indeed, for every choice counted by the left hand size, I can fix the first element which has $n$ possible values. The remaining elements are chosen from a set of size $n-1$ (since there is no repetition) and there are $k-1$ of them. Thus the product of $n$ and this other amount gives me the total number of possible choices.

Note:

Formalize the above proof using a bijection between the permutations of $n$ and a set of size $P_k^n(n-k)!$. An example of such a proof is seen below and you are expected to know how to write these types of formal proofs.

Corollary.

There are $P_n^n=n!$ bijections from any set of size $n$ to itself. These are called permutations.

Combinations

Let $X$ be a set and $\lambda$ a cardinal (usually a natural number). I will denote by $[X{]}^{\lambda }$ the collection of subsets of $X$ of size exactly $\lambda$. That is, $[X{]}^{\lambda }:=\{A\subseteq X:|A|=\lambda \}$.

Definition.

The number of subsets of a given size is read as ”$n$ choose $k$” and denoted as follows.

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right):=\left|[n{]}^k\right|$$

Examples.

1. $\left(\genfrac{}{}{0ex}{}{n}{n}\right)=|\{n\}|=1$
2. $\left(\genfrac{}{}{0ex}{}{n}{0}\right)=|\{\varnothing \}|=1$
3. when $k>n$, $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=0$
4. $\left(\genfrac{}{}{0ex}{}{n}{1}\right)=|\{\{k\}:k<n\}|=n$
5. $\left(\genfrac{}{}{0ex}{}{n}{n-1}\right)=|\{n\setminus \{k\}:k<n\}|=n$

You are expected to know how to prove the following exercises from the definition, not from the formula, which prove afterwards.

Exercise.

Prove that for $k\le n$, $\left(\genfrac{}{}{0ex}{}{n}{n-k}\right)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)$.

Exercise.

$$\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n$$

Combinations formula.

Assume $k\le n$.

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!(n-k)!}$$

Proof:

For every $A\in [n{]}^k$, let ${\Phi }_A$ be the set of all permutations on $A$. For simplicity, let me write $A=\{a_1,\dots ,a_k\}$. By definition, the set

$$\beth :=\{(\phi (a_1),\dots ,\phi (a_k)):\phi \in {\Phi }_A,A\in [n{]}^k\}$$

has size $P_k^n$. It is straightforward to show that, for any fixed $A$ (since they all have the same size), $|\beth |=|[n{]}^k|\cdot |{\Phi }_A|=(\genfrac{}{}{0ex}{}{n}{k})k!$. The result follows.

Reflect.

It isn’t even immediately obvious that the right-most expression above is an integer to begin with. This is proved in Tutorial 3.