"Counting kernel positions in Bernoulli type games"

Gábor Hetyei
University of North Carolina at Charlotte

Monday, March 8, 2010
4:00 pm , 845 POT

Abstract:

We introduce a class of two-player games on a ranked set of positions, in which each move of the winning strategy is unique. This allows to enumerate the kernel positions by rank. Our main example is a simple game in which the number of kernel positions of rank n is a signed factorial multiple of the n-th Bernoulli number of the second kind. A generalization of this game provides a combinatorial model for the degenerate Bernoulli numbers introduced by Carlitz, a probabilistic application allows realizing the integral of any function on a finite interval as the expected gain of a player in an infinite casino-style game.

Almost all of our examples are truncation games on words such that the set of strings that may be truncated in a single move is closed under valid truncations. This property allows an explicit description of all kernel positions. Thus we obtain new formulas for Bernoulli numbers and polynomials of the second kind and a new combinatorial model for the number of connected permutations of given rank, which form the algebra basis of the Malvenuto-Reutenauer Hopf algebra. For connected permutations, the decomposition used to find the winning strategy is shown to be bijectively equivalent to King's decomposition, used to recursively generate a transposition Gray code of the connected permutations.