With Celia Glass and Robert Schumacher, I recently found a combinatorial interpretation of the poly-Bernoulli numbers of negative order.
Bernoulli numbers
The classical Bernoulli numbers are defined by a recurrence which can be written symbolically as
(B+1)^{n+1} = B^{n+1}.
The interpretation is: expand (B+1)^{n+1} by the Binomial Theorem, then replace superscripts (exponents) by subscripts throughout the equation. The terms B_{n+1} cancel, leaving a relation which expresses B_{n} in terms of earlier Bs. For example,
B_{2}+2B_{1}+1 = B_{2}, so that B_{1} = −1/2;
B_{3}+3B_{2}+3B_{1}+1 = B_{3}, so that B_{2} = 1/6.
They are among the most important and ubiquitous sequences of numbers, appearing in areas from number theory (Faulhaber’s formula for the sum of kth powers of the first n natural numbers; Fermat’s last theorem; Carmichael’s λ-function) through numerical analysis (the Euler–Maclaurin sum formula) to mathematical physics.
There are two slightly different versions of Bernoulli numbers. They differ only in the sign of B_{2}. I will now switch to the other one; this has the effect of adding x to the generating function. (The new form is the one discussed by Conway and Guy in The Book of Numbers.)
It can be shown that the exponential generating function for the (revised) Bernoulli numbers is F(x) = x/(1−e^{−x}). This has two simple consequences:
- F(x)−x/2 = (x/2) coth (x/2), an even function of x, so the odd-numbered Bernoulli numbers after the first are all zero;
- a formula: B_{n} = ∑(-1)^{k}kS(n,k)/(k+1), where the sum is over k running from 1 to n. (Here S(n,k) is the Stirling number of the second kind, the number of partitions of an n-set with k parts.)
Poly-Bernoulli numbers
Poly-Bernoulli numbers were defined by Masanobu Kaneko in 1997.
First we define the order-k polylogarithmic integral by
Li_{k}(z) = ∑_{m≥1} z^{m}/m^{k},
and then let
Li_{k}(1−e^{−x})/(1−e^{−x}) = ∑_{n≥0} B_{n}^{(k)}x^{n}/n!
These are the poly-Bernoulli numbers of order k.
For k = 1, the power series for Li_{1}(z) is just that of −log(1−z), and so the exponential generating function for the poly-Bernoulli numbers of order 1 is simply x/(1−e^{−x}), so as we saw in the last section, they are the classical Bernoulli numbers.
It is clear from the power series that Li_{k+1} is obtained from Li_{k} by multiplying by z and integrating (keeping the constant term zero). We obtain a sequence of transcendental functions in this way.
However, the definitions make sense also for zero and negative orders. We have Li_{0}(z) = 1/(1−z), and successive functions of negative order are obtained by the inverse operation to what we just saw, namely, differentiating and multiplying by z; so they are all rational functions.
Kaneko gives a formula for the Bernoulli numbers of negative order (which turn out to be positive integers), which we will come to soon. But there is a remarkable and unexpected symmetry property:
B_{m}^{(−k)} = B_{k}^{(−m)}.
A combinatorial interpretation
An orientation of the edges of a graph is acyclic if there are no directed cycles.
Theorem The number of acyclic orientations of the complete bipartite graph K_{m,k} is given by
∑ S(m+1,i)S(k+1,i)((i−1)!)^{2}.
The sum runs from i=1 to the maximum of m+1 and k+1.
Here is a sketch of the proof. Such an orientation is obtained by partitioning the two bipartite blocks A and B (of sizes m and k) into parts, arranging them in order (alternating between the two bipartite blocks) and then directing edges from left to right (noting that there are no edges within a part). So the number can be obtained by counting the partitions and the ordering of the parts. However, there are four different cases: the first block in the ordering may be in either A or B, as also may the last block. To reduce the four cases to one, we add a dummy point to A, which must be in the first part, and a dummy point to B, which must be in the last part; then the numbers of parts in the two blocks are equal. (Either the first or last part may be a singleton consisting of the dummy point; these account for the other three cases.) This explains the m+1 and k+1 in the formula. However, when ordering the parts, there are two whose positions are fixed, so there are (i−1)! orderings for the parts in each block.
Now the remarkable thing is:
This formula coincides with a formula of Kaneko for the poly-Bernoulli number B_{m}^{(−k)}.
I don’t really understand why!
Lonesum matrices
Ours is not the first combinatorial interpretation. In 2008, Chad Brewbaker showed that B_{m}^{(−k)} is also the number of lonesum matrices of size m×k: these are zero-one matrices which are uniquely determined by their row and column sums.
A theorem of Ryser shows that a binary matrix is lonesum if and only if it does not contain either the 2×2 identity matrix or its reflection in the vertical axis as a submatrix (in not-necessarily-consecutive rows and columns). If one of these matrices occurs, it can be flipped into the other without changing the row and column sums. The non-trivial asserion is the converse.
The correspondence is simple. Given an orientation of the complete bipartite graph, we can describe it by a binary matrix, with entries 1 for left-to-right arcs and 0 for right-to-left. The two forbidden matrices correspond to directed 4-cycles, so if the orientation is acyclic then the matrix is lonesum. The converse is also true, essentially because the cycle space of the complete bipartite graph is spanned by 4-cycles, so that if there is any directed cycle then there will be a directed 4-cycle.