Discrete CATS Seminar
####
**
**#####
U N I V E R S I T Y
O F
K E N T U C K Y

DISCRETE
CATS
SEMINAR

WHERE CATS =
COMBINATORICS,
ALGEBRA,
TOPOLOGY
&
STATISTICS!

845 PATTERSON OFFICE TOWER

SPRING 2010

##
"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.