Code That Counts

From Data.List, we have:

We represent a set \(U\) with a list u of distinct elements. A subset or combination of \(U\) is represented by a list s satisfying isSubsequenceOf s u. In other words:

Subsets of size \(k\) are called k-subsets or k-combinations. To generate them, we closely follow the above cases:

Write \({n \choose k}\) for the number of \(k\)-subsets of a set of size \(n\).

We read this as "n choose k".

The first case of subsets implies for all \(n \ge 0\):

\[{n \choose 0} = 1\]

The second case implies that for any \(k \gt 0\):

\[{0 \choose k} = 0\]

The third case implies:

\[{n \choose k} = {n - 1 \choose k - 1} + {n - 1 \choose k }\]

where \(n, k \gt 0\). The left-hand term of the sum counts all subsets starting with x, while the other side counts all subsets not containing x. In the latter, we know x must be absent because of the uniqueness of each item of the list representing u.

These numbers are called the binomial coefficients, because the coefficient of \(x^k\) in \((1 + x)^n\) is \({n \choose k}\). We can prove via induction that the coefficients satisfy the same recurrence relations.

Pascal’s triangle brings these equations to life:

By induction, we can show:

\[ {n \choose k} = \frac{n^\underline{k}}{k!} \]

where we adopt Knuth’s underline notation for the falling factorial:

\[ n^\underline{k} = n(n-1)..(n-k+1) \]

Stanley writes \( (n)_k \), but we prefer Knuth because it naturally leads to overline notation for the rising factorial:

\[ n^\overline{k} = n(n+1)..(n+k-1) \]

(Thus \( k! = k^\underline{k} = 1^{\overline{k}} \).)

Although there exists a much faster algorithm for computing binomial coefficients, we use falling factorials to compute binomial coefficients for simplicity:

We can view this formula from another perspective. There are \(n\) ways to pick an element from a set of size \(n\):

Iterating this \(k\) times yields \(n(n-1)…​(n-k+1)\) ways of picking a sequence of size \(k\) consisting of distinct elements of the set:

In the case \(n = k\), we have that the number of permutations of \(k\) objects is \(k\) factorial.

Now, there are \({n \choose k}\) distinct \(k\)-subsets, and from each we can produce \(k!\) sequences of size \(k\). By equating two different ways of counting the same thing:

\[ n^\underline{k} = {n\choose k} k! \]

Recall:

\[ (1+x)^n = \sum_k {n\choose k} x^k \]

To translate this to code, we represent polynomials with lists of integers, with \([a_0, a_1, …​]\) representing \(a_0 + a_1 x + …​\). Then addition and multiplication of polynomials are given by:

It turns out our representation works well the other way, that is, we can represent a sequence of numbers as a polynomial; in this scheme, an infinite sequence corresponds to a formal power series. This gives us an algebra for manipulating sequences, known as generating functions.

By redefining \({n\choose k}\) to be the coefficient of \(x^k\) in \((1 + x)^n\) written as a power series, we generalize binomial coefficients beyond positive integers \(n\). When \(n\) is a negative integer, we could derive a formula via calculus and Taylor series expansions, or using the recurrences and induction, but we’ll soon see a simpler approach.

A composition of \(n\) is an ordered list of positive integers that sum to \(n\). A k-composition of \(n\) is a composition of \(n\) into \(k\) parts. For example, a 4-composition of 7 is:

\[ 1 + 3 + 2 + 1 = 7 \]

We obtain related definitions by allowing zero. A weak composition of \(n\) is an ordered list of nonnegative integers that sum to \(n\). A weak k-composition of \(n\) is a weak composition of \(n\) into \(k\) parts. For example, a weak 4-composition of 7 is:

\[ 3 + 0 + 2 + 2 = 7 \]

How can we generate all \(k\)-compositions and weak \(k\)-compositions of \(n\)?

Try answering this before studying the following:

Thus the number of \(k\)-compositions of \(n\) is \({n-1\choose k-1}\), and the number of weak \(k\)-compositions of \(n\) is \({n+k-1\choose k-1}\).

The power set of a set \(S\) is the set of all subsets of \(S\). We can compute it with the standard library subsequences function, or bust out a well-known mind-blowing trick:

The power set of an \(n\)-set has size \(2^n\), as suggested by the length of the list [False, True]. In brief, the list monad is syntax sugar for concatMap. Applying each of \(x\) functions to each of \(y\) items in a list and concatenating everything leads to a list of size \(xy\), so iterating this procedure on \(n\) lists of size 2 leads to a list of size \(2^n\).

Less abstrusely, for each item, we can decide to include it or leave it out, leading to \(2^n\) total different decision paths.

Accordingly, we denote the power set of \(S\) by \(2^S\).

Informally, a multiset is a set where elements may appear more than once. More rigorously, a finite multiset \(M\) on a set \(S\) is a function \(v:S\to\Bbb{N}\) with \(\sum_{s\in S} v(s) < \infty\). We’re back to ordinary subsets when \(v(s) \le 1\).

A k-combination with repetition of a set \(S\) is a multiset on \(S\) of size \(k\). The number of \(k\)-combinations with repetition of an \(n\)-set is denoted by \(\left({n \choose k}\right)\).

We can generate all \(k\)-combinations with repetition of \([1..n]\) as follows:

which implies \(\left({n \choose k}\right) = {n + k - 1 \choose k}\):

We also have:

\[ (1 + x + x^2 + …​)^n = \sum x^{|M|} [M \text{ is a multiset on } [1..n]] = \sum_{k\ge 0} \left({n \choose k}\right) x^k \]

Thus:

\[ (1 + x + x^2 +…​ )^n = (1 - x)^{-n} = \sum_{k\ge 0} {-n \choose k}(-1)^k x^k \]

and therefore:

\[\left({n\choose k}\right) = (-1)^k {-n\choose k} = {n + k - 1\choose k}\]

This is an easy way to compute binomial coefficients for negative \(n\). The first equation is an example of a combinatorial reciprocity theorem.

We generalize binomial cofficients to multinomial coefficients: if \(a_1,…​,a_m\) are nonnegative integers that sum to \(n\), that is, a weak \(m\)-composition of \(n\), then define \({n\choose a_1,…​,a_m}\) to be number of ways to divide \([1..n]\) into \(m\) different categories. We can also view this as the number of permutations of the multiset where there are \(a_i\) copies of the \(i\)th element. Additionally, we have:

\[ (x_1 + ... + x_m)^n = \sum {n\choose a_1,...,a_m} x_1^{a_1}...x_m^{a_m} \]

When \(m = 2\), we have binomial coefficients. Conventionally, we write \({n\choose k}\) instead of \({n\choose k,n-k}\). The latter notation does have advantages: we immediately have \({n\choose k} = {n\choose n-k}\), and we’re mindful that choosing \(k\) elements out of an \(n\)-set is the same as choosing to omit \(n-k\) elements. The recurrence of Pascal’s triangle also becomes symmetric:

\[{n\choose a,b} = {n-1\choose a-1, b} + {n-1\choose a,b-1}\]

Multinomials can be computed by:

\[ {n\choose a_1,…​,a_m} = \frac{n!}{a_1!…​a_m!} \]

and satisfy the recurrence:

\[ {n\choose a_1,…​,a_m} = {n\choose a_1-1,…​,a_m} + …​ + {n\choose a_1,…​,a_m-1} \]

The following is a multiset version of our picks function. We rely on a helper function to keep out degenerate empty lists. We expect identical elements in the input list to be grouped together, for instance, ["b", "aaa", "nn"] instead of "banana".

We’ve already exhibited code to enumerate all permutations of a list xs. Simply evaluate orderedSets xs (length xs).

In Algorithm Design with Haskell, Richard Bird and Jeremy Gibbons describe a more direct approach:

They also describe another function for generating all permutations, one that is inductive as opposed to recursive:

They discuss important features of these algorithms, which we regrettably ignore for now because we’re focusing on combinatorics.

We can use the multiset version of picks to enumerate all permutations of elements of a multiset:

A permutation of a set can be represented as a word. In particular, we can represent the permutation \(\pi\) on \([1..n]\) defined by \(\pi(i) = a_i\) as the word \(a_1 …​ a_n\).

Given a permutation \(\pi\) on a finite set \(S\), for any \(x\in S\) the sequence \(x, \pi(x), \pi(\pi(x)), …​\) must eventually repeat, thus permutations can be written as a product of cycles:

We define a standard representation for writing products of cycles. We sort cycles in increasing order by their maximum elements, and each cycle is written starting with its maximum element. We write \(\hat\pi\) for the standard representation of \(\pi\).

Such a representation is unique, and furthermore, we can remove all bracketing: a new cycle begins precisely when an element exceeds the previous maximum, namely, on all the left-to-right maxima. Thus the standard representation defines a bijection on permutations.

Given a permutation \(\pi\), let \(c_i(\pi)\) be the number of cycles of length \(i\). Then the type of a permutation \(\pi\) is the sequence \( (c_1(\pi),…​,c_n(\pi)) \), and the total number of cycles of \(\pi\) is the sum of this sequence and denoted \(c(\pi)\).

Exercise: Show the number of permutations of type \((c_1,…​,c_n)\) is:

\[ \frac{n!}{1^{c_1}c_1!...n^{c_n}c_n!} \]

Solution: Suppose we write \([1..n]\) in every possible order, and for each such ordering, from left to right we divide the elements into \(c_1\) cycles of length 1, then \(c_2\) cycles of length 2, and so on up to \(c_n\) cycles of length \(n\). We have produced all permutations of the desired type, but we have counted each permutation multiple times because we can write a cycle of length \(k\) in \(k\) different ways and for each \(i\) we can permute \(c_i\) cycles amongst themselves without changing the product.

Following Knuth (who credits Jovan Karamata), we write:

\[{n \brack k}\]

for the number of permutations of \([1..n]\) with exactly \(k\) cycles. (Stanley writes \(c(n, k)\).) Thanks to standard representations, this is also the number of permutations of \([1..n]\) with \(k\) left-to-right maxima. These are known as the signless Stirling numbers of the first kind.

The following enumerates them all:

The code implies the recursion:

\[ {n \brack k} = (n-1) {n-1 \brack k} + {n-1 \brack k-1} \]

We can prove:

by showing the coefficients satisfy the same recursive relations.

Another proof: the coefficient of \(x^k\) on the right-hand side is:

\[ \sum_{1\le a_1,…​,a_{n-k}\le n-1} a_1 …​ a_{n-k} \]

which can viewed as the count of tuples \((S, f)\) where \(S\) is a \((n-k)\)-subset of \([1..n-1]\) and \(f : S → [1..n - 1]\) is a function satisfying \(f(i) \le i\).

We show each such tuple corresponds to a \(k\)-cycle permutation, which can be written as a permutation of \([1..n]\) with \(k\) left-to-right maxima.

Subtract each element of \(S\) from \(n\) to get \(b_1 > …​ > b_{n-k}\). The \(k\) remaining elements of \([1..n\) are our left-to-right maxima, so we start by writing them in ascending order. Then we insert the \(b_i\) values so that exactly \(f(b_i)\) numbers larger than \(b_i\) appear to the left of \(b_i\).

Yet another proof: we show the polynomials in question agree for all positive integers \(x\). For such an \(x\), the left-hand side is the number of \(k\)-cycle permutations multiplied by the number of functions from \(k\) objects to \([1..x]\), while the right-hand side is the number of integer sequences \((a_1,…​,a_n)\) satisfying \(0 \le a_i \le x - 1 + n - i\). (The \(a_i\) are "backwards" and zero-indexed for historical reasons; our code will undo this.)

We can produce a permutation and function from such a sequence as follows:

Setting \(x = 1\) shows for all positive integers \(n, k\), the number of sequences \((a_1, …​, a_n)\) with \(0 \le a_i \le n - i\) containing exactly \(k\) zeroes is \({n\brack k}\). Or in code:

We can build a permutation \(\pi\) in word form more directly from such a sequence:

In the sequence, \(a_i\) is the number of entries \(j\) in \(\pi\) to the left of \(i\) such that \(j > i\). As hinted by our function name, if \(\pi = b_1 …​ b_n\) then \((b_i, b_j)\) is an inversion if \(i < j\) and \(b_i > b_j\), and the sequence \(a_i\) is called the inversion table of the permutation \(\pi\), and written \(I(\pi)\). An inversion table is another way to represent a permutation.

If \(i(\pi)\) denotes the number of inversions in the permutation \(\pi\), we see:

\[ \sum_{\pi\in S_n} q^{i(\pi)} = (1 + q)(1 + q + q^2)…​(1 + q + …​ + q^{n-1}) \]

The descent set \(D(\pi)\) of a permutation \(\pi = a_1 …​ a_n\) is defined by:

For a subset \(S\) of \([1..n-1]\), define \(\alpha(S)\) and \(\beta(S)\) as follows:

Thus an alternative definition of \(\alpha(S)\) is:

If we write \(S\) as an increasing sequence \(s_1, …​, s_k\), then \[ \alpha(S) = {n \choose {s_1, s_2 - s_1, …​, n - s_k}} \]

For a permutation \(\pi\), write \(des(\pi)\) for the number of descents \(|D(\pi)|\). Then

\[ A_n(x) = \sum_{\pi\in S_n} x^{1+des(\pi)} \]

is an Eulerian polynomial. We write \(A(n, k)\) for the coefficient of \(x^k\) in \(A_n(x)\), and we call it an Eulerian number. Hence:

The definition of the standard representation of a permutation implies:

\[ n - des(\hat\pi) = \#\{i \in [1..n] | \pi(i) \ge i\} \]

A number \(i\) is called a weak excedance of \(\pi\) if \(\pi(i)\ge i\), and an excedance if \(\pi(i) > i\):

From:

it follows that the Eulerian number \(A(n, k+1)\) is equal to the number of permutations of \(S_n\) with \(k\) excedances and also the number of permutations of \(S_n\) with \(k+1\) weak excedances.

The sum of the descent set of a permutation \(\pi\) is called the greater index and is denoted \(\iota(\pi)\). It is also called the major index and denoted \(maj(\pi)\). It turns out:

A binary tree of numbers has the heap property if each child node exceeds its parent node. We represent a permutation as a heap as follows:

Define an element \(w_i\) of a word \(w_1…​w_n\) to be

where we set the sentinels \(w_0 = w_{n+1} = 0\). These four classes of terrain determine whether a node has no children, a left child, a right child, or both.

From this bijection, we see:

We can also represent a permutation \(\pi\) as an unoriented heap. We prepend the sentinel value of 0 to our permutation, and start with root node of 0. Then the children of the node \(n\) are all nodes \(a\) that appear to the right of \(n\) in \(\pi\) satisfying \(n < a\) and \(b > a\) for all numbers \(b\) that appear between \(n\) and \(a\) in \(\pi\).

Thus:

A partition of a natural number \(n\) is a non-increasing sequence of integers that sums to \(n\). We ignore terminating 0s when deciding equality of partitions. A partition is like a composition, except the order of the summands is unimportant.

Write \(p(n)\) for the number of partitions of \(n\), \(p_k(n)\) for the number of partitions of \(n\) into \(k\) parts, and \(p(j, k, n)\) for the number of partitions of \(n\) into \(k\) parts with largest part at most \(j\).

We can generate all partitions with:

which gives the recurrence:

\[ p_k(n) = p_{k-1}(n - 1) + p_k(n - k) \]

The following code produces the Ferrers diagram or Ferrers graph of a partition:

If we had drawn squares instead, then we would have a Young diagram.

A partition of a finite set \(N\) is a set of disjoint subsets \(\{B_1,…​,B_k\}\) of \(N\) whose union is \(N\). A subset \(B_i\) is called a block.

Roughly speaking, partitions of a set are like partitions of an integer, except the elements of a set are distinguishable. We can generate them with:

Define \({n \brace k}\) to be the number of ways to partition \(N\) into \(k\) blocks. These are called the Stirling numbers of the second kind. (Again, we adopt Knuth’s recommendation instead of Stanley’s \(S(n, k)\).)

Our partitions function implies:

By induction:

The total number of partitions of an \(n\)-set is called a Bell number and is denoted \(B(n)\).

To recap:

\[ {0 \choose 0} = {0 \brack 0} = {0 \brace 0} = 1 \]

For \(k > 0\): \[ {0 \choose k} = {0 \brack k} = {0 \brace k} = 0 \]

For \(n > 0\): \[ {n \choose 0} = 1 \]

\[ {n \brack 0} = {n \brace 0} = 0 \]

For \(n, k > 0\):

Summations: \[ \begin{align} \sum_k {n \choose k} &= 2^n \\ \sum_k {n \brack k} &= n! \\ \sum_k {n \brace k} &= B(n) \end{align} \]

Two functions \(f, g : N \to X\) are equivalent with \(N\) indistinguishable if there exists a bijection \(\pi : N \to N\) such that \(f \circ \pi = g\).

They are equivalent with \(X\) indistinguishable if there exists a bijection \(\sigma : X \to X\) such that \(\sigma \circ f = g\).

They are equivalent with \(N\) and \(X\) indistinguishable if there exists bijections \(\pi : N \to N\) and \(\sigma : X \to X\) such that \(\sigma \circ f \circ \pi = g\).

Given \(n, x\) and two booleans representing the distinguishability of an \(n\)-set \(N\) and and \(x\)-set \(X\), the following function returns a list containing the number of functions, injections, and surjections from \(N\) to \(X\).