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! }[/math], read "[math]\displaystyle{ n }[/math] factorial", is defined as that [math]\displaystyle{ n!=n(n-1)(n-2)\cdots 1 }[/math], with the convention 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]; [math]\displaystyle{ \sum_{k=0}^n {n\choose k}=2^n }[/math].

Proof. 1. We give two proofs for the first equation: (1) (numerical proof) [math]\displaystyle{ {n\choose k}=\frac{n!}{k!(n-k)!}={n\choose n-k} }[/math]. (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]. 2. The second equation can also be proved in different ways, but the combinatorial proof is much easier. 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]

[math]\displaystyle{ {n\choose k} }[/math] is called binomial coefficient for a reason. A binomial is a polynomial with two terms ("poly-" means many, and "bi-" means two, like in "binary", "bipartite", etc). The following celebrated Binomial Theorem states that if a power of a binomial is expanded, the coefficients in the resulting polynomial are the binomial coefficients.

Theorem (Binomial theorem)

[math]\displaystyle{ (1+x)^n=\sum_{k=0}^n{n\choose k}x^k }[/math].

Proof. Write [math]\displaystyle{ (1+x)^n }[/math] as the product of [math]\displaystyle{ n }[/math] factors [math]\displaystyle{ (1+x)(1+x)\cdots (1+x) }[/math]. The term [math]\displaystyle{ x^k }[/math] is obtained by choosing [math]\displaystyle{ x }[/math] from [math]\displaystyle{ k }[/math] factors and 1 from the rest [math]\displaystyle{ (n-k) }[/math] factors. There are [math]\displaystyle{ {n\choose k} }[/math] ways of choosing these [math]\displaystyle{ k }[/math] factors, so the coefficient of [math]\displaystyle{ x^k }[/math] is [math]\displaystyle{ {n\choose k} }[/math]. [math]\displaystyle{ \square }[/math]

The following proposition has an easy proof due to the binomial theorem.

Proposition

For [math]\displaystyle{ n\gt 0 }[/math], the numbers of subsets of an [math]\displaystyle{ n }[/math]-set of even and of odd cardinality are equal.

Proof. Set [math]\displaystyle{ x=-1 }[/math] in the binomial theorem. [math]\displaystyle{ 0=(1-1)^n=\sum_{k=0}^n{n\choose k}(-1)^k=\sum_{\overset{0\le k\le n}{k \text{ even}}}{n\choose k}-\sum_{\overset{0\le k\le n}{k \text{ odd}}}{n\choose k}, }[/math] therefore [math]\displaystyle{ \sum_{\overset{0\le k\le n}{k \text{ even}}}{n\choose k}=\sum_{\overset{0\le k\le n}{k \text{ odd}}}{n\choose k}. }[/math] [math]\displaystyle{ \square }[/math]

For counting problems, what we care about are numbers. In the binomial theorem, a formal variable [math]\displaystyle{ x }[/math] is introduced. It looks having nothing to do with our problem, but turns out to be very useful. This idea of introducing a formal variable is the basic idea of some advanced counting techniques, which will be discussed in future classes.

Compositions of an integer

A composition of [math]\displaystyle{ n }[/math] is an expression of [math]\displaystyle{ n }[/math] as an ordered sum of positive integers. A [math]\displaystyle{ k }[/math]-composition of [math]\displaystyle{ n }[/math] is a composition of [math]\displaystyle{ n }[/math] with exactly [math]\displaystyle{ k }[/math] positive summands.

Formally, a [math]\displaystyle{ k }[/math]-composition of [math]\displaystyle{ n }[/math] is a [math]\displaystyle{ k }[/math]-tuple [math]\displaystyle{ (a_1,a_2,\ldots,a_k)\in\{1,2,\ldots,n\}^k }[/math] such that [math]\displaystyle{ a_1+a_2+\cdots+a_k=n }[/math].

Suppose we have [math]\displaystyle{ n }[/math] identical balls in a line. A [math]\displaystyle{ k }[/math]-composition partitions these [math]\displaystyle{ n }[/math] balls into [math]\displaystyle{ k }[/math] nonempty sets, illustrated as follows.

[math]\displaystyle{ \begin{array}{c|cc|c|c|ccc|cc} \bigcirc \,&\, \bigcirc \,& \bigcirc \,&\, \bigcirc \,&\, \bigcirc \,&\, \bigcirc &\, \bigcirc &\, \bigcirc \,&\, \bigcirc \,& \bigcirc \end{array} }[/math]

So the number of [math]\displaystyle{ k }[/math]-compositions of [math]\displaystyle{ n }[/math] equals the number of ways we put [math]\displaystyle{ k-1 }[/math] bars "[math]\displaystyle{ | }[/math]" into [math]\displaystyle{ n-1 }[/math] slots "[math]\displaystyle{ \sqcup }[/math]", where each slot has at most one bar (because all the summands [math]\displaystyle{ a_i\gt 0 }[/math]):

[math]\displaystyle{ \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc \sqcup \bigcirc }[/math]

which is equal to the number of ways of choosing [math]\displaystyle{ k-1 }[/math] slots out of [math]\displaystyle{ n-1 }[/math] slots, which is [math]\displaystyle{ {n-1\choose k-1} }[/math].

This graphic argument can be expressed as a formal proof. We construct a bijection between the set of [math]\displaystyle{ k }[/math]-compositions of [math]\displaystyle{ n }[/math] and [math]\displaystyle{ {\{1,2,\ldots,n-1\}\choose k-1} }[/math] as follows.

Let [math]\displaystyle{ \phi }[/math] be a mapping that given a [math]\displaystyle{ k }[/math]-composition [math]\displaystyle{ (a_1,a_2,\ldots,a_k) }[/math] of [math]\displaystyle{ n }[/math],

[math]\displaystyle{ \begin{align} \phi((a_1,a_2,\ldots,a_k)) &=\{a_1,\,\,a_1+a_2,\,\,a_1+a_2+a_3,\,\,\ldots,\,\,a_1+a_2+\cdots+a_{k-1}\}\\ &=\left\{\sum_{i=1}^ja_i\,\,\bigg|\,\, 1\le j\lt k\right\}. \end{align} }[/math]

[math]\displaystyle{ \phi }[/math] maps every [math]\displaystyle{ k }[/math]-composition to a [math]\displaystyle{ (k-1) }[/math]-subset of [math]\displaystyle{ \{1,2,\ldots,n-1\} }[/math]. It is easy to verify that [math]\displaystyle{ \phi }[/math] is a bijection, thus the number of [math]\displaystyle{ k }[/math]-compositions of [math]\displaystyle{ n }[/math] is [math]\displaystyle{ {n-1\choose k-1} }[/math].

---

The number of [math]\displaystyle{ k }[/math]-compositions of [math]\displaystyle{ n }[/math] is equal to the number of positive integer solutions to [math]\displaystyle{ x_1+x_2+\cdots+x_k=n }[/math]. This suggests us to relax the constraint and count the number of nonnegative integer solutions to [math]\displaystyle{ x_1+x_2+\cdots+x_k=n }[/math]. We call such a solution a weak [math]\displaystyle{ k }[/math]-composition of [math]\displaystyle{ n }[/math].

Formally, a weak [math]\displaystyle{ k }[/math]-composition of [math]\displaystyle{ n }[/math] is a tuple [math]\displaystyle{ (x_1,x_2,\ldots,x_k)\in[n+1]^k }[/math] such that [math]\displaystyle{ x_1+x_2+\cdots+x_k=n }[/math].

Given a weak [math]\displaystyle{ k }[/math]-composition [math]\displaystyle{ (x_1,x_2,\ldots,x_k) }[/math] of [math]\displaystyle{ n }[/math], if we set [math]\displaystyle{ y_i=x_i+1 }[/math] for every [math]\displaystyle{ 1\le i\le k }[/math], then [math]\displaystyle{ y_i\gt 0 }[/math] and

[math]\displaystyle{ \begin{align} y_1+y_2+\cdots +y_k &=(x_1+1)+(x_2+1)+\cdots+(x_k+1)&=n+k, \end{align} }[/math]

i.e., [math]\displaystyle{ (y_1,y_2,\ldots,y_k) }[/math] is a [math]\displaystyle{ k }[/math]-composition of [math]\displaystyle{ n+k }[/math]. It is easy to see that it defines a bijection between weak [math]\displaystyle{ k }[/math]-compositions of [math]\displaystyle{ n }[/math] and [math]\displaystyle{ k }[/math]-compositions of [math]\displaystyle{ n+k }[/math]. Therefore, the number of weak [math]\displaystyle{ k }[/math]-compositions of [math]\displaystyle{ n }[/math] is [math]\displaystyle{ {n+k-1\choose k-1} }[/math].

---

We now count the number of nonnegative integer solutions to [math]\displaystyle{ x_1+x_2+\cdots+x_k\le n }[/math].

Let [math]\displaystyle{ x_{k+1}=n-(x_1+x_2+\cdots+x_k) }[/math]. Then [math]\displaystyle{ x_{k+1}\ge 0 }[/math] and [math]\displaystyle{ x_1+x_2+\ldots+x_k+x_{k+1}=n }[/math]. The problem is transformed to that counting the number of nonnegative integer solutions to the above equation. The answer is [math]\displaystyle{ {n+k\choose k} }[/math].

The twelvfold way

We consider a very fundamental counting framework: counting functions [math]\displaystyle{ f:N\rightarrow M }[/math]. We can define different counting problems according to the types of mapping (1-1, on-to, arbitrary), and the types of the domain and the range (distinguishable, indistinguishable).

• Distinguishability of set:
• Types of mapping:

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]

Reference

• Stanley, Enumerative Combinatorics, Volume 1, Chapter 1.