Set Partitions

Section 1.5 Set Partitions

The Stirling Number of the Second Kind counts the number of ways to partition an \(m\)-set into exactly \(n\) parts, where the parts are not ordered, or not distinguished in any way. It is given by the formula

\begin{gather*} S(m,n)=\frac{1}{n!}\sum_{k=0}^{n-1}(-1)^k\binomial{n}{k}(n-k)^m \end{gather*}

Multiplied by \(n!\) this would give the number of partitions where the parts are ordered, and so provides a count of the functions from an \(n\)-set onto an \(m\)-set.

It is straightforward to compute in Sage, the function arguments mirror the usual notation. So to partion a set of ten people into exactly five discussion groups, we would compute:

Sage makes use of many mature open source packages for various areas of mathematics. So sometimes there is more than one way to do something. For this Stirling number there are three ways: Sage's own implementation, GAP (Groups, Algorithms, and Programming) and Maxima (one of the first symbolic mathematics packages). These are chosen with the algorithm= keyword taking values None (default), "gap", or "maxima". So the number of onto functions from a \(10\)-set to a \(5\)-set is computed using GAP by:

Stirling Numbers of the First Kind are a little more complicated. They are often written similarly, but with a lower-case “s”. In Sage you just use the function stirling_number1. The computation is done by GAP.

As used by Sage, \(s(m, n)\) counts the number of permutations of an \(m\)-set which has \(n\) cycles when expressed in cycle notation, and so is always positive. A second interpretation (see next paragraph) involves coefficients of a polynomial which alternate in sign, but which are idential in absolute value. So you may wish to prefix Sage's version with a \((-1)^{m-n}\text{.}\)

Define the falling factorial as \((x)_m = x(x-1)(x-2)\cdots(x-m+1)\text{.}\) Then the signed Stirling numbers of the first kind can be defined by

\begin{gather*} (x)_m = \sum_{k=0}^{m}\,s(m,k)\,x^k \end{gather*}

Here is a Sage example you can edit repeatedly to test this relationship.

The second command makes the letter x represent a symbolic variable, rather than a Python variable, and then computations proceed as you would expect if you were doing basic algebra. (More precisely, x belongs to Sage's SymbolicRing.) Notice how we have to explicitly ask for final polynomial to be expanded so we can easily recognize that it is zero. Try different values of m and maybe for a smaller value temporarily remove the .expand() method.

There are some curious relationships between the two different types of Stirling numbers. We illustrate an inverse relationship by building two lower-triangular matrices that are matrix inverses of each other. Of course, you could infer the general theorem about this relationship from properties of matrix multiplication. Only the size of a page prevents us from using larger matrices.

Notice that lambda is how Python constructs anonymous functions, and Sage employs this in a natural way in the matrix constructor to populate the entries of a matrix.