Acyclic orientations and poly-Bernoulli numbers

P. J. Cameron, C. A. Glass, R. U. Schumacher

Published 2014-12-11Version 1

In 1997, Masanobu Kaneko defined \emph{poly-Bernoulli numbers}, which bear much the same relation to polylogarithms as Berunoulli numbers do to logarithms. In 2008, Chet Brewbaker described a counting problem whose solution can be identified with the poly-Bernoulli numbers with negative index, the \emph{lonesum matrices}. The main aim of this paper is to give formulae for the number of acyclic orientations of a complete bipartite graph, or of a complete bipartite graph with one edge added or removed. Our formula shows that the number of acyclic orientations of $K_{n_1,n_2}$ is equal to the poly-Bernoulli number $B_{n_1}^{(-n_2)}$. We also give a simple bijective identification of acyclic orientations and lonesum matrices. We make some remarks on the context of our result, which are expanded in another paper.