Day 11: CM, Page xi

Day 11: A second page of notation. I'm going to practice my LaTeX on this page.

The link below is useful for LaTeX notation:
http://en.wikibooks.org/wiki/LaTeX/Mathematics

This is the notation for a Stirling cycle number (the "first kind"). "The notation of using brackets and braces, in analogy to the binomial coefficients, was introduced in 1935 by Jovan Karamata and promoted later by Donald Knuth; it is referred to as Karamata notation" (wikipedia). "Stirling numbers of the first kind (without the qualifying adjective unsigned) are the coefficients in the expansion [to the right] where (x)(n) is the falling factorial." They "count the number of permutations of n elements with k disjoint cycles" (wikipedia). In this context, "cycle" refers to a cyclic permutation. For example, the picture below shows a cyclic permutation on 4 objects with 2 cycles. So, in this case s(4,2) = 11.
How is this related to the formula above? The formula says that the falling factorial is equal to the coefficients on a formula that looks like ax^4 + bx^3 + cx^2 + dx^1 (for n=4). So... what are a, b, c, and d? For n=4, they are:


Notice that "11" appears as the coefficient of x^2. This matches the solution for s(4,2) above. So for s(4,1) and s(4,3), we should find six distinct cycles. And for s(4,4), we should find one. Let's verify assuming we have nodes a, b, c, d.

For s(4,1) we have:
abcd
abdc
acbd
acdb
adbc
adcb

And for s(4,3) we have:
a b cd
a bc d
ab c d
cd b a
d bc a
d c ab

And for s(4,4) we only have:
a b c d

So the cyclic permutations match the coefficients on the expansion of the falling fractorial. Just to confirm that the equation above holds, let's consider it for x=5. Sure enough, it works:

The "first kind" of Sterling numbers let us expand rising and falling factorials and count cyclic permutations. Pretty neat. We'll learn about these more in 260 days or so.