Combinatorics (Fall 2010)/Basic enumeration

Sets and Multisets

Subsets

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

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

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

[math]\displaystyle{ v_i=\begin{cases} 1 & \mbox{if }x_i\in T\\ 0 & \mbox{if }x_i\not\in T. \end{cases} }[/math]

The map [math]\displaystyle{ \phi }[/math] is a bijection (a 1-1 correspondence). The proof that [math]\displaystyle{ \phi }[/math] is a bijection is left as an exercise.

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

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

There are two elements of this proof:

• Find a 1-1 correspondence between subsets of an [math]\displaystyle{ n }[/math]-set and [math]\displaystyle{ n }[/math]-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 [math]\displaystyle{ U }[/math] can be represented by an array of [math]\displaystyle{ |U| }[/math] 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 [math]\displaystyle{ |2^S|=2^n }[/math]. Define the function [math]\displaystyle{ f(n)=|2^{S_n}| }[/math], where [math]\displaystyle{ S_n=\{x_1,x_2,\ldots,x_n\} }[/math] is an [math]\displaystyle{ n }[/math]-set. Our goal is to compute [math]\displaystyle{ f(n) }[/math]. We prove the following recursion for [math]\displaystyle{ f(n) }[/math].

Lemma

[math]\displaystyle{ f(n)=2f(n-1)\, }[/math].

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

The elementary case [math]\displaystyle{ f(0)=1 }[/math], because [math]\displaystyle{ \emptyset }[/math] has only one subset [math]\displaystyle{ \emptyset }[/math]. Solving the recursion, we have that [math]\displaystyle{ |2^S|=f(n)=2^n }[/math].

Subsets of fixed size

We then count the number of subsets of fixed size of a set. Again, let [math]\displaystyle{ S=\{x_1,x_2,\ldots,x_n\} }[/math] be an [math]\displaystyle{ n }[/math]-set. We define [math]\displaystyle{ {S\choose k} }[/math] to be the set of all [math]\displaystyle{ k }[/math]-elements subsets (or [math]\displaystyle{ k }[/math]-subsets) of [math]\displaystyle{ S }[/math]. Formally, [math]\displaystyle{ {S\choose k}=\{T\subseteq S\mid |T|=k\} }[/math]. The set [math]\displaystyle{ {S\choose k} }[/math] is sometimes called the [math]\displaystyle{ k }[/math]-uniform of [math]\displaystyle{ S }[/math].

We denote that [math]\displaystyle{ {n\choose k}=\left|{S\choose k}\right| }[/math]. The notation [math]\displaystyle{ {n\choose k} }[/math] is read "[math]\displaystyle{ n }[/math] choose [math]\displaystyle{ k }[/math]".

Theorem

[math]\displaystyle{ {n\choose k}=\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots 1}=\frac{n!}{k!(n-k)!} }[/math].

Proof. The number of ordered [math]\displaystyle{ k }[/math]-subsets of an [math]\displaystyle{ n }[/math]-set is [math]\displaystyle{ n(n-1)\cdots(n-k+1) }[/math]. Every [math]\displaystyle{ k }[/math]-subset has [math]\displaystyle{ k!=k(k-1)\cdots1 }[/math] ways to order it. [math]\displaystyle{ \square }[/math]

Some notations

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

The quantity [math]\displaystyle{ {n\choose k} }[/math] is called a binomial coefficient.

Proposition

[math]\displaystyle{ {n\choose k}={n\choose n-k} }[/math].

Proof 1 (numerical proof). [math]\displaystyle{ {n\choose k}=\frac{n!}{k!(n-k)!}={n\choose n-k} }[/math]. [math]\displaystyle{ \square }[/math]

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

The next proposition is much easier to prove by combinatorial proofs.

Proposition

[math]\displaystyle{ \sum_{k=0}^n {n\choose k}=2^n }[/math].

Proof. For an [math]\displaystyle{ n }[/math]-element set [math]\displaystyle{ S }[/math], it is obvious that we can enumerate all subsets of [math]\displaystyle{ S }[/math] by enumerating [math]\displaystyle{ k }[/math]-subsets for every possible size [math]\displaystyle{ k }[/math], i.e. it holds that [math]\displaystyle{ 2^S=\bigcup_{k=0}^n{S\choose k}. }[/math] For different [math]\displaystyle{ k }[/math], [math]\displaystyle{ {S\choose k} }[/math] are obviously disjoint. By the rule of sum, [math]\displaystyle{ 2^n=|2^S|=\left|\bigcup_{k=0}^n{S\choose k}\right|=\sum_{k=0}^n\left|{S\choose k}\right|=\sum_{k=0}^n {n\choose k} }[/math]. [math]\displaystyle{ \square }[/math]

The twelvfold way

[math]\displaystyle{ f:N\rightarrow M }[/math]

Elements of [math]\displaystyle{ N }[/math]	Elements of [math]\displaystyle{ M }[/math]	Any [math]\displaystyle{ f }[/math]	Injective (1-1) [math]\displaystyle{ f }[/math]	Surjective (on-to) [math]\displaystyle{ f }[/math]
distinguishable	distinguishable	[math]\displaystyle{ m^n\, }[/math]	[math]\displaystyle{ \left(m\right)_n }[/math]	[math]\displaystyle{ m!S(n, m)\, }[/math]
indistinguishable	distinguishable	[math]\displaystyle{ \left({m\choose n}\right) }[/math]	[math]\displaystyle{ {m\choose n} }[/math]	[math]\displaystyle{ \left({m\choose n-m}\right) }[/math]
distinguishable	indistinguishable	[math]\displaystyle{ \sum_{k=1}^m S(n,k) }[/math]	[math]\displaystyle{ \begin{cases}1 & \mbox{if }n\le m\\ 0& \mbox{if }n\gt m\end{cases} }[/math]	[math]\displaystyle{ S(n,m)\, }[/math]
indistinguishable	indistinguishable	[math]\displaystyle{ \sum_{k=1}^m p_k(n) }[/math]	[math]\displaystyle{ \begin{cases}1 & \mbox{if }n\le m\\ 0& \mbox{if }n\gt m\end{cases} }[/math]	[math]\displaystyle{ p_m(n)\, }[/math]