Combinatorics (Fall 2010)/Basic enumeration

Sets and Multisets

Subsets

We want to count the number of subsets of a set.

Let$S=\{x_1,x_2,\dots ,x_n\}$ be an $n$-element set, or $n$-set for short. Let $2^S=\{T\mid T\subset S\}$ denote the set of all subset of $S$. $2^S$ is called the power set of $S$.

We give a combinatorial proof that $|2^S|=2^n$. We observe that every subset $T\in 2^S$ corresponds to a unique bit-vector $v\in \{0,1{\}}^S$, such that each bit $v_i$ indicates whether $x_i\in S$. Formally, define a map $\varphi :2^S\to \{0,1{\}}^n$ by $\varphi (T)=(v_1,v_2,\dots ,v_n)$, where

$v_i=\{\begin{array}{ll}1& \text{if }{x}_i\in T\\ 0& \text{if }{x}_i\notin T.\end{array}$

The map $\varphi$ is a bijection (a 1-1 correspondence). The proof that $\varphi$ is a bijection is left as an exercise.

We know that $|\{0,1{\}}^n|=2^n$. Why is that? We apply "the rule of product": for any finite sets $P$ and $Q$, the cardinality of the Cartesian product $|P\times Q|=|P|\cdot |Q|$. We can write $\{0,1{\}}^n=\{0,1\}\times \{0,1{\}}^{n-1}$, thus $|\{0,1{\}}^n|=2|\{0,1{\}}^{n-1}|$, and by induction, $|\{0,1{\}}^n|=2^n$.

Since there is a bijection between $2^S$ and $\{0,1{\}}^n$, it holds that $|2^S|=|\{0,1{\}}^n|=2^n$. Here we use "the rule of bijection": if there exists a bijection between finite sets $P$ and $Q$, then $|P|=|Q|$.

There are two elements of this proof:

• Find a 1-1 correspondence between subsets of an $n$-set and $n$-bit vectors.

An application of this in Computer Science is that we can use bit-array as a data structure for sets: any set defined over a universe $U$ can be represented by an array of $|U|$ bits.

• The rule of bijection: if there is a 1-1 correspondence between two sets, then their cardinalities are the same.

Many counting problems are solved by establishing a bijection between the set to be counted and some easy-to-count set. This kind of proofs are usually called (non-rigorously) combinatorial proofs.

---

We give an alternative proof that $|2^S|=2^n$. Define the function $f(n)=|2^{S_n}|$, where $S_n=\{x_1,x_2,\dots ,x_n\}$ is an $n$-set. Our goal is to compute $f(n)$. We prove the following recursion for $f(n)$.

Lemma

$f(n)=2f(n-1)$.

Proof. Fix an element $x_n$, let $U$ be the set of subsets of $S_n$ that contain $x_n$ and let $V$ be the set of subsets of $S_n$ that do not contain $x_n$. It is obvious that $U$ and $V$ are disjoint (i.e. $U\cap V=\mathrm{\varnothing }$) and $2^{S_n}=U\cup V$, because any subset of $S_n$ either contains $x_n$ or does not contain $x_n$ but not both. We apply "the rule of sum": for any disjoint finite sets $P$ and $Q$, the cardinality of the union $|P\cup Q|=|P|+|Q|$. Therefore, $f(n)=|U\cup V|=|U|+|V|$. The next observation is that $|U|=|V|=f(n-1)$, because $V$ is exactly the $2^{S_{n-1}}$, and $U$ is the set resulting from add $x_n$ to every member of $2^{S_{n-1}}$. Therefore, $f(n)=|U|+|V|=f(n-1)+f(n-1)=2f(n-1)$. $◻$

The elementary case $f(0)=1$, because $\mathrm{\varnothing }$ has only one subset $\mathrm{\varnothing }$. Solving the recursion, we have that $|2^S|=f(n)=2^n$.

Subsets of fixed size

We then count the number of subsets of fixed size of a set. Again, let $S=\{x_1,x_2,\dots ,x_n\}$ be an $n$-set. We define $(\genfrac{}{}{0ex}{}{S}{k})$ to be the set of all $k$-elements subsets (or $k$-subsets) of $S$. Formally, $(\genfrac{}{}{0ex}{}{S}{k})=\{T\subseteq S\mid |T|=k\}$. The set $(\genfrac{}{}{0ex}{}{S}{k})$ is sometimes called the $k$-uniform of $S$.

We denote that $(\genfrac{}{}{0ex}{}{n}{k})=\left|(\genfrac{}{}{0ex}{}{S}{k})\right|$. The notation $(\genfrac{}{}{0ex}{}{n}{k})$ is read "$n$ choose $k$".

Theorem

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n(n-1)\cdots (n-k+1)}{k(k-1)\cdots 1}=\frac{n!}{k!(n-k)!}$.

Proof. The number of ordered $k$-subsets of an $n$-set is $n(n-1)\cdots (n-k+1)$. Every $k$-subset has $k!=k(k-1)\cdots 1$ ways to order it. $◻$

Some notations

• $n!=n(n-1)(n-2)\cdots 1$, read "$n$ factorial". A convention is that $0!=1$.
• $n(n-1)\cdots (n-k+1)=\frac{n!}{(n-k)!}$ is usually denoted as $(n{)}_k$, read "$n$ lower factorial $k$".

Proposition

$(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n}{n-k})$.

Proof 1 (numerical proof). $(\genfrac{}{}{0ex}{}{n}{k})=\frac{n!}{k!(n-k)!}=(\genfrac{}{}{0ex}{}{n}{n-k})$. $◻$

Proof 2 (combinatorial proof). Choosing $k$ elements from an $n$-set is equivalent to choosing the $n-k$ elements to leave out. Formally, every $k$-subset $T\in (\genfrac{}{}{0ex}{}{S}{k})$ is uniquely specified by its complement $S\setminus T\in (\genfrac{}{}{0ex}{}{S}{n-k})$, and the same holds for $(n-k)$-subsets, thus we have a bijection between $(\genfrac{}{}{0ex}{}{S}{k})$ and $(\genfrac{}{}{0ex}{}{S}{n-k})$. $◻$

The twelvfold way

$f:N\to M$

Elements of $N$	Elements of $M$	Any $f$	Injective (1-1) $f$	Surjective (on-to) $f$
distinguishable	distinguishable	$m^n$	${\left(m\right)}_n$	$m!S(n,m)$
indistinguishable	distinguishable	$\left((\genfrac{}{}{0ex}{}{m}{n})\right)$	$(\genfrac{}{}{0ex}{}{m}{n})$	$\left((\genfrac{}{}{0ex}{}{m}{n-m})\right)$
distinguishable	indistinguishable	$\sum _{k=1}^{m}S(n,k)$	$\{\begin{array}{ll}1& \text{if }n\le m\\ 0& \text{if }n>m\end{array}$	$S(n,m)$
indistinguishable	indistinguishable	$\sum _{k=1}^m{p}_k(n)$	$\{\begin{array}{ll}1& \text{if }n\le m\\ 0& \text{if }n>m\end{array}$	$p_m(n)$