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.

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 apply "the rule of bijection".

• 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].

How do we know that [math]\displaystyle{ |\{0,1\}^n|=2^n\, }[/math]? We use "the rule of product".

• 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].

To count the size of [math]\displaystyle{ \{0,1\}^n\, }[/math], we 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]. Solving the recursion, we have that [math]\displaystyle{ |\{0,1\}^n|=2^n\, }[/math].

There are two elements of the 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]. The proof needs another basic counting rule: "the rule of sum".

• 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].

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. Applying the rule of sum, [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 adding [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 solutions to [math]\displaystyle{ x_1+x_2+\cdots+x_k=n }[/math] in positive integers. This suggests us to relax the constraint and count the number of solutions to [math]\displaystyle{ x_1+x_2+\cdots+x_k=n }[/math] in nonnegative integers. 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 solutions to [math]\displaystyle{ x_1+x_2+\cdots+x_k\le n }[/math] in nonnegative integers.

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 solutions to the above equation in nonnegative integers. The answer is [math]\displaystyle{ {n+k\choose k} }[/math].

Multisets

A [math]\displaystyle{ k }[/math]-subset of an [math]\displaystyle{ n }[/math]-set [math]\displaystyle{ S }[/math] is sometimes called a [math]\displaystyle{ k }[/math]-combination of [math]\displaystyle{ S }[/math] without repetitions. This suggests the problem of counting the number of [math]\displaystyle{ k }[/math]-combinations of [math]\displaystyle{ S }[/math] with repetitions; that is, we choose [math]\displaystyle{ k }[/math] elements of [math]\displaystyle{ S }[/math], disregarding order and allowing repeated elements.

Example

[math]\displaystyle{ S=\{1,2,3,4\} }[/math]. All [math]\displaystyle{ 3 }[/math]-combination without repetitions are

[math]\displaystyle{ \{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\}\, }[/math].

Allowing repetitions, we also include the following 3-combinations:

[math]\displaystyle{ \begin{align} &\{1,1,1\},\{1,1,2\},\{1,1,3\},\{1,1,4\},\{1,2,2\},\{1,3,3\},\{1,4,4\},\\ &\{2,2,2\},\{2,2,3\},\{2,2,4\},\{2,3,3\},\{2,4,4\},\\ &\{3,3,3\},\{3,3,4\},\{3,4,4\}\\ &\{4,4,4\} \end{align} }[/math]

Combinations with repetitions can be formally defined as multisets. A multiset is a set with repeated elements. Formally, a multiset [math]\displaystyle{ M }[/math] on a set [math]\displaystyle{ S }[/math] is a function [math]\displaystyle{ m:S\rightarrow \mathbb{N} }[/math]. For any element [math]\displaystyle{ x\in S }[/math], the integer [math]\displaystyle{ m(x)\ge 0 }[/math] is the number of repetitions of [math]\displaystyle{ x }[/math] in [math]\displaystyle{ M }[/math], called the multiplicity of [math]\displaystyle{ x }[/math]. The sum of multiplicities [math]\displaystyle{ \sum_{x\in S}m(x) }[/math] is called the cardinality of [math]\displaystyle{ M }[/math] and is denoted as [math]\displaystyle{ |M| }[/math].

A [math]\displaystyle{ k }[/math]-multiset on a set [math]\displaystyle{ S }[/math] is a multiset [math]\displaystyle{ M }[/math] on [math]\displaystyle{ S }[/math] with [math]\displaystyle{ |M|=k }[/math]. It is obvious that a [math]\displaystyle{ k }[/math]-combination of [math]\displaystyle{ S }[/math] with repetition is simply a [math]\displaystyle{ k }[/math]-multiset on [math]\displaystyle{ S }[/math].

The set of all [math]\displaystyle{ k }[/math]-multisets on [math]\displaystyle{ S }[/math] is denoted [math]\displaystyle{ \left({S\choose k}\right) }[/math]. Assuming that [math]\displaystyle{ n=|S| }[/math], denote [math]\displaystyle{ \left({n\choose k}\right)=\left|\left({S\choose k}\right)\right| }[/math], which is the number of [math]\displaystyle{ k }[/math]-combinations of an [math]\displaystyle{ n }[/math]-set with repetitions.

Believe it or not: we have already evaluated the number [math]\displaystyle{ \left({n\choose k}\right) }[/math]. If [math]\displaystyle{ S=\{x_1,x_2,\ldots,x_n\} }[/math], let [math]\displaystyle{ z_i=m(x_i) }[/math], then [math]\displaystyle{ \left({n\choose k}\right) }[/math] is the number of solutions to [math]\displaystyle{ z_1+z_2+\cdots+z_n=k }[/math] in nonnegative integers, which is the number of weak [math]\displaystyle{ n }[/math]-compositions of [math]\displaystyle{ k }[/math], which we have seen is [math]\displaystyle{ {n+k-1\choose n-1}={n+k-1\choose k} }[/math].

---

There is a direct combinatorial proof that [math]\displaystyle{ \left({n\choose k}\right)={n+k-1\choose k} }[/math].

Given a [math]\displaystyle{ k }[/math]-multiset [math]\displaystyle{ 0\le a_0\le a_1\le\cdots\le a_{k-1}\le n-1 }[/math] on [math]\displaystyle{ [n] }[/math], then defining [math]\displaystyle{ b_i=a_i+i }[/math], we see that [math]\displaystyle{ \{b_0,b_1,\ldots,b_{k-1}\} }[/math] is a [math]\displaystyle{ k }[/math]-subset of [math]\displaystyle{ [n+k-1] }[/math]. Conversely, given a [math]\displaystyle{ k }[/math]-subset [math]\displaystyle{ 0\le b_0\le b_1\le\cdots\le b_{k-1}\le n+k-2 }[/math] of [math]\displaystyle{ [n+k-1] }[/math], then defining [math]\displaystyle{ a_i=b_i-i }[/math], we have that [math]\displaystyle{ \{b_0,b_1,\ldots,b_{k-1}\} }[/math] is a [math]\displaystyle{ k }[/math]-multiset on [math]\displaystyle{ [n] }[/math]. Therefore, we have a bijection between [math]\displaystyle{ \left({[n]\choose k}\right) }[/math] and [math]\displaystyle{ {[n+k-1]\choose k} }[/math].

Multinomial coefficients

The binomial coefficient [math]\displaystyle{ {n\choose k} }[/math] may be interpreted as follows. Each element of an [math]\displaystyle{ n }[/math]-set is placed into two groups, with [math]\displaystyle{ k }[/math] elements in Group 1 and [math]\displaystyle{ n-k }[/math] elements in Group 2. The binomial coefficient [math]\displaystyle{ {n\choose k} }[/math] counts the number of such placements.

This suggests a generalization allowing more than two groups. Let [math]\displaystyle{ (a_1,a_2,\ldots,a_m) }[/math] be a tuple of nonnegative integers summing to [math]\displaystyle{ n }[/math]. Let [math]\displaystyle{ {n\choose a_1,a_2,\ldots,a_m} }[/math] denote the number of ways of assigning each element of an [math]\displaystyle{ n }[/math]-set to one of [math]\displaystyle{ m }[/math] groups [math]\displaystyle{ G_1,G_2,\ldots,G_m }[/math] so that exactly [math]\displaystyle{ a_i }[/math] elements are assigned to [math]\displaystyle{ G_i }[/math].

The binomial coefficient is just the case when there are two groups, and [math]\displaystyle{ {n\choose k}={n\choose k,n-k} }[/math]. The number [math]\displaystyle{ {n\choose a_1,a_2,\ldots,a_m} }[/math] is called a multinomial coefficient. We can think of it as that [math]\displaystyle{ n }[/math] labeled balls are assigned to [math]\displaystyle{ m }[/math] labeled bins, and [math]\displaystyle{ {n\choose a_1,a_2,\ldots,a_m} }[/math] is the number of assignments such that the [math]\displaystyle{ i }[/math]-th bin has [math]\displaystyle{ a_i }[/math] balls in it.

The multinomial coefficient can also be interpreted as the number of permutations of multisets. A permutation [math]\displaystyle{ \pi }[/math] of an [math]\displaystyle{ n }[/math]-set [math]\displaystyle{ S }[/math] can be defined in two equivalent ways:

• a bijection [math]\displaystyle{ \pi:S\rightarrow S }[/math];
• a tuple [math]\displaystyle{ \pi=(x_1,x_2,\ldots,x_n)\in S^n }[/math] such that all [math]\displaystyle{ x_i }[/math] are distinct.

There are [math]\displaystyle{ n! }[/math] permutations of an [math]\displaystyle{ n }[/math]-set [math]\displaystyle{ S }[/math].

A permutation of a multiset [math]\displaystyle{ M }[/math] is a tuple [math]\displaystyle{ \pi=(x_1,x_2,\ldots,x_n) }[/math] such that every [math]\displaystyle{ x_i\in M }[/math] appears in [math]\displaystyle{ \pi }[/math] for exactly [math]\displaystyle{ m(x_i) }[/math] times, where [math]\displaystyle{ m(x_i) }[/math] is the multiplicity of [math]\displaystyle{ x_i }[/math] in [math]\displaystyle{ M }[/math].

Example

We want to enumerate all the ways of reordering the word "multinomial". Note that in this word, the letter "m", "l" and "i" each appears twice. So the problem is to enumerate the permutations of the multiset [math]\displaystyle{ \{\text{a, i, i, l, l, m, m, n, o, t, u}\} }[/math].

Let [math]\displaystyle{ M }[/math] be a multiset of [math]\displaystyle{ m }[/math] distinct elements [math]\displaystyle{ x_1,x_2,\ldots,x_m }[/math] such that [math]\displaystyle{ x_i }[/math] has multiplicity [math]\displaystyle{ a_i }[/math] in [math]\displaystyle{ M }[/math]. A permutation [math]\displaystyle{ \pi }[/math] of multiset [math]\displaystyle{ M }[/math] assigns [math]\displaystyle{ n }[/math] indices [math]\displaystyle{ 1,2,\ldots,n }[/math] to [math]\displaystyle{ m }[/math] groups, where each group corresponds to a distinct element [math]\displaystyle{ x_i }[/math], such that [math]\displaystyle{ i }[/math] is assigned to group [math]\displaystyle{ j }[/math] if [math]\displaystyle{ \pi_i=x_j }[/math].

Therefore, [math]\displaystyle{ {n\choose a_1,a_2,\ldots,a_m} }[/math] is also the number of permutations of a multiset [math]\displaystyle{ M }[/math] with [math]\displaystyle{ |M|=n }[/math] such that [math]\displaystyle{ M }[/math] has [math]\displaystyle{ m }[/math] distinct elements whose multiplicities are given by [math]\displaystyle{ a_1,a_2,\ldots,a_m }[/math].

Theorem

[math]\displaystyle{ {n\choose a_1,a_2,\ldots,a_m}=\frac{n!}{a_1!a_2!\cdots a_m!}. }[/math]

Proof. There are [math]\displaystyle{ n! }[/math] permutations of [math]\displaystyle{ n }[/math] objects. Assume that these [math]\displaystyle{ n }[/math] objects are the elements of an multiset [math]\displaystyle{ M }[/math] of [math]\displaystyle{ m }[/math] distinct elements with [math]\displaystyle{ |M|=n }[/math] and multiplicities [math]\displaystyle{ a_1,a_2,\ldots,a_m }[/math]. Since [math]\displaystyle{ a_i! }[/math] permutations of object [math]\displaystyle{ i }[/math] do not change the permutation of the multiset [math]\displaystyle{ M }[/math], every [math]\displaystyle{ a_1!a_2!\cdots a_m! }[/math] permutations of these [math]\displaystyle{ n }[/math] objects correspond to the same permutation of the multiset [math]\displaystyle{ M }[/math]. Thus, the number of permutations of [math]\displaystyle{ M }[/math] is [math]\displaystyle{ \frac{n!}{a_1!a_2!\cdots a_m!} }[/math]. [math]\displaystyle{ \square }[/math]

We also have the Multinomial Theorem.

Theorem

[math]\displaystyle{ {n\choose a_1,a_2,\ldots,a_m} }[/math] is the coefficient of [math]\displaystyle{ x_1^{a_1}x_2^{a_2}\cdots x_m^{a_m} }[/math] in [math]\displaystyle{ (x_1+x_2+\cdots +x_m)^n }[/math].

Proof. Write [math]\displaystyle{ (x_1+x_2+\cdots +x_m)^n=(x_1+x_2+\cdots +x_m)\cdots (x_1+x_2+\cdots +x_m) }[/math]. Each of the [math]\displaystyle{ n }[/math] factors corresponds to a distinct ball, and [math]\displaystyle{ x_1,x_2,\ldots,x_m }[/math] correspond to [math]\displaystyle{ m }[/math] groups. The coefficient of [math]\displaystyle{ x_1^{a_1}x_2^{a_2}\cdots x_m^{a_m} }[/math] equals the number of ways to put [math]\displaystyle{ n }[/math]distinct balls to [math]\displaystyle{ m }[/math] distinct groups so that group [math]\displaystyle{ i }[/math] receives [math]\displaystyle{ a_i }[/math] balls, which is exactly our first definition of [math]\displaystyle{ {n\choose a_1,a_2,\ldots,a_m} }[/math]. [math]\displaystyle{ \square }[/math]

Partitions of a set

A partition of finite set [math]\displaystyle{ S }[/math] is a collection [math]\displaystyle{ P=\{B_1,B_2,\ldots,B_k\} }[/math] of subsets of [math]\displaystyle{ S }[/math] such that:

• [math]\displaystyle{ B_i\neq\emptyset }[/math] for every [math]\displaystyle{ i }[/math];
• [math]\displaystyle{ B_i\cap B_j=\emptyset }[/math] if [math]\displaystyle{ i\neq j }[/math] (also called that blocks are pairwise disjoint);
• [math]\displaystyle{ B_1\cup B_2\cup\cdots\cup B_k=S }[/math].

Each [math]\displaystyle{ B_i }[/math] is called a block of partition [math]\displaystyle{ P }[/math]. We call [math]\displaystyle{ P }[/math] a [math]\displaystyle{ k }[/math]-partition of [math]\displaystyle{ S }[/math] if [math]\displaystyle{ |P|=k }[/math].

Define [math]\displaystyle{ S(n,k) }[/math] to be the number of [math]\displaystyle{ k }[/math]-partitions of an [math]\displaystyle{ n }[/math]-set. Note that since a partition [math]\displaystyle{ P }[/math] is a set, the order of blocks [math]\displaystyle{ B_1,B_2,\ldots,B_k }[/math] is disregarded when counting [math]\displaystyle{ k }[/math]-partitions.

The number [math]\displaystyle{ S(n,k) }[/math] is called a Stirling number of the second kind.

Stirling number Stirling numbers are named after James Stirling.There are two kinds of Stirling numbers. Stirling number of the first kind is related to the number of permutations with fixed number of disjoint cycles. And Stirling number of the second kind counts the number of ways of partitioning a set into fixed number of disjoint blocks. Both numbers arise from important combinatorial problems and have various applications in combinatorics and other branches of Mathematics.

Unlike previous identities, it is very difficult to give a determinant for [math]\displaystyle{ S(n,k) }[/math]. But we have the following recurrence:

Theorem

[math]\displaystyle{ S(n,k)=kS(n-1,k)+S(n-1,k-1)\, }[/math].

Proof. To partition [math]\displaystyle{ \{1,2,\ldots,n\} }[/math] into [math]\displaystyle{ k }[/math] blocks, we can partition [math]\displaystyle{ \{1,2,\ldots,{n-1}\} }[/math] into [math]\displaystyle{ k }[/math] blocks and place [math]\displaystyle{ n }[/math] into one of the [math]\displaystyle{ k }[/math] blocks, which gives us [math]\displaystyle{ kS(n-1,k) }[/math] ways to do so; or we can partition [math]\displaystyle{ \{1,2,\ldots,{n-1}\} }[/math] into [math]\displaystyle{ k-1 }[/math] blocks and let [math]\displaystyle{ \{n\} }[/math] be a block by itself, which gives us [math]\displaystyle{ S(n-1,k-1) }[/math] ways to do so. The permutation constructed by these two methods are different, since by the first method, [math]\displaystyle{ x_n }[/math] is always in a block of cardinality [math]\displaystyle{ \gt 1 }[/math], and by the second method, [math]\displaystyle{ \{x_n\} }[/math] is always a block. So the cases are disjoint. And any [math]\displaystyle{ k }[/math]-partition of [math]\displaystyle{ [n] }[/math] must be constructible by one of the two methods, thus by the rule of sum, [math]\displaystyle{ S(n,k)=kS(n-1,k)+S(n-1,k-1) }[/math]. [math]\displaystyle{ \square }[/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]

balls per bin	unrestricted	≤ 1	≥ 1
[math]\displaystyle{ n }[/math] labeled balls, [math]\displaystyle{ m }[/math] labeled bins	[math]\displaystyle{ n }[/math]-tuples of [math]\displaystyle{ m }[/math] things	[math]\displaystyle{ n }[/math]-permutations of [math]\displaystyle{ m }[/math] things	partition of [math]\displaystyle{ [n] }[/math] into [math]\displaystyle{ m }[/math] ordered parts
[math]\displaystyle{ n }[/math] unlabeled balls, [math]\displaystyle{ m }[/math] labeled bins	[math]\displaystyle{ n }[/math]-combinations of [math]\displaystyle{ [m] }[/math] with repetitions	[math]\displaystyle{ n }[/math]-combinations of [math]\displaystyle{ [m] }[/math] without repetitions	[math]\displaystyle{ m }[/math]-compositions of [math]\displaystyle{ n }[/math]
[math]\displaystyle{ n }[/math] labeled balls, [math]\displaystyle{ m }[/math] unlabeled bins	partitions of [math]\displaystyle{ [n] }[/math] into [math]\displaystyle{ \le m }[/math] parts	[math]\displaystyle{ n }[/math] pigeons into [math]\displaystyle{ m }[/math] holes	partitions of [math]\displaystyle{ [n] }[/math] into [math]\displaystyle{ \le m }[/math] parts
[math]\displaystyle{ n }[/math] unlabeled balls, [math]\displaystyle{ m }[/math] unlabeled bins	partitions of [math]\displaystyle{ n }[/math] into [math]\displaystyle{ \le m }[/math] parts	[math]\displaystyle{ n }[/math] pigeons into [math]\displaystyle{ m }[/math] holes	partitions of [math]\displaystyle{ n }[/math] into [math]\displaystyle{ m }[/math] parts

Reference

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