% A LaTeX file for an 11 page document.
\documentclass[12pt]{amsart}
%\usepackage[T1]{fontenc}
%\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}
\newcommand{\DEF}{\buildrel {\rm def} \over =}
\newcommand{\sgn}{{\rm sgn}}
\newcommand{\Diapegs}{{\sc Diapegs}}
\newcommand{\Pegs}{{\sc Pegs}}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\textwidth 6in
\textheight 8.5in
\oddsidemargin 0.1in
\evensidemargin 0.1in
\begin{document}
\thispagestyle{empty}
\title{Diagonal checker-jumping and \\ Eulerian numbers for color-signed permutations}
\keywords{Eulerian numbers, color-signed permutations,
checker-jumping, pagoda function}
\subjclass{Primary: 05A30; Secondary: 05A99}
\date{}
\thanks{N.E.: Partially supported by the Swedish Natural Science
Research Council.}
\thanks{K.E.: Partially supported by the Swedish Natural Science
Research Council and the Swedish Foundation for Strategic Research.}
\maketitle
\begin{center}
\begin{tabular}[t]{c@{\extracolsep{2em}}c@{\extracolsep{2em}}c}
\bf Niklas Eriksen \footnotemark[1] &
\bf Henrik Eriksson \footnotemark[2] &
\bf Kimmo Eriksson \footnotemark[3] \\
\small\tt niklas@math.kth.se&
\small\tt henrik@nada.kth.se&
\small\tt Kimmo.Eriksson@mdh.se\\
\end{tabular}
\smallskip
\begin{small}
\begin{tabular}{rl}
\footnotemark[1]& \parbox[t]{13cm}{
Department of Mathematics, KTH, SE-100 44 Stockholm,
Sweden} \\
\footnotemark[2]& \parbox[t]{13cm}{
NADA, KTH, SE-100 44 Stockholm,
Sweden} \\
\footnotemark[3]& \parbox[t]{13cm}{
IMa, M{\"a}lardalens h{\"o}gskola, Box 883,
SE-721 23 V{\"a}ster{\aa}s, Sweden}
\end{tabular}
\end{small}
\end{center}
\pagestyle{myheadings} \markboth{\hfill{\sc the electronic journal of
combinatorics {\bf 7} (2000), \#R3}}
{{\sc the electronic journal of combinatorics {\bf 7} (2000), \#R3}\hfill}
\vspace{0.5cm}\begin{center}
Submitted: September 2, 1999; Accepted: January 26, 2000.
\end{center}
\begin{abstract}
We introduce {\em color-signed} permutations to obtain a
very explicit combinatorial interpretation of the $q$-Eulerian
identities of Brenti and some generalizations. In particular,
we prove an identity involving the golden ratio, which allows
us to compute upper bounds on how high a checker can reach
in a classical checker-jumping problem, when the rules are
relaxed to allow also diagonal jumps.
\end{abstract}
\section{Introduction}
This paper has two themes. First,
we will present a notion of {\em color-signed} permutations, that is,
signed permutations where the plus sign comes in $p$ different
colors and the minus sign comes in $q$ different colors.
These permutations give a very explicit combinatorial interpretation
of the $q$-Eulerian identities of Brenti \cite{FB}, and also provide
some generalizations of them.
Second, we will treat a variant of an old checker-jumping problem:
When playing checkers on the square grid, given that the lower
half-plane is full of checkers and the upper half-plane is empty, how
high up in the upper half-plane can we place a checker by playing the
game? This problem was solved long ago (see Berlekamp, Conway and
Guy's entertaining book on combinatorial games \cite{EB}). H.\,Eriksson
and Lindstr{\"o}m generalized checker-jumping to higher dimensions
\cite{HE&BL}. In his M.Sc.~thesis, Eriksen \cite{NE} changed the
rules to allow also diagonal checker-jumping moves, thereby obtaining
a harder problem for which we will here present an upper bound on how
high the checker can be placed.
The connection between the two themes is the following identity:
Let $n$ be a positive integer and let $\sigma$ denote the golden
ratio $(\sqrt{5}-1)/2$. Then
\begin{equation}\label{niklas-id}
\sum_{m = 1}^{\infty}\ m\ (2m + 1)^{n - 1}\ \sigma^{m+2} =
\sigma^{-2n} \sum_{k = 1}^{n} b_{nk} \sigma^k,
\end{equation}
where the numbers $b_{nk}$ are defined by $b_{1,1}=1$, $b_{nk}=0$
for $k\le 0$ and for $k> n$, and the recurrence relation
$$b_{nk} = (2 (n - k) + 1)\ b_{n-1, k-1} + (2k + 1)\ b_{n-1, k}.$$
The first few values of $b_{nk}$ are:
\begin{center}
\begin{tabular} {r | r r r r}
\\
& $k=1$ & 2 & 3 & 4 \\ \hline
$n= 1$ & 1 \\
2 & 3 & 1 \\
3 & 9 & 14 & 1 \\
4 & 27 & 115 & 49 & 1 \\
\end{tabular}
\end{center}
The identity (\ref{niklas-id}) is needed for computation of the upper
bound in the checker-jumping problem. Zeilberger (personal
communication) told us how (\ref{niklas-id}) could be proved using induction.
Our own search for a combinatorial proof led us to the idea of color-signed
permutations.
\section{Preliminaries on Eulerian and $q$-Eulerian numbers}
Let $[n]$ denote the integer set $\{1,\dots,n\}$. Signed
permutations on $[n]$ define a group denoted by $B_n$. The subgroup
consisting of signed permutations with every value plus-signed
is isomorphic to the symmetric group $S_n$.
We will describe a signed permutation $\pi$ by its
sequence $\pi_1\dots\pi_n$ of values.
Two statistics on permutations will be important: the number of
descents and the number of minus signs.
A {\em descent} is a position $i$ where the permutation value decreases:
$ \pi_{i - 1} > \pi_i$. When counting descents we always have the
convention that $\pi_0=0$. Let $d(\pi)$ denote the {\em number of descents}
of a signed permutation $\pi$.
The {\em number of minus signs} (resp.~{\em plus signs}) in a signed
permutation $\pi\in B_n$ is denoted by $N(\pi)$ (resp.~$P(\pi)$).
In other words,
$$N(\pi) \DEF \# \{i \in [n]: \pi_i < 0\} \qquad\mbox{ and }\qquad
P(\pi) \DEF n - N(\pi).
$$
%A sequence ${a_0, a_1, \ldots, a_n}$ is said to be {\em log-concave}
%if $a_i^2 \geq a_{i - 1}a_{i + 1}$ for all $i$. It is {\em unimodal}
%if there exists an index $0 \leq j \leq n$ such that $a_i \leq a_{i +
%1}$ for $i < j$ and $a_i \leq a_{i + 1}$ for $i \geq j$.
%The following proposition will prove very useful to us later. A proof
%can be found in \cite{RS}, p 209.
%\begin{proposition} \label{pr: binomial}
%Let $A(m)$ be a real polynomial in $m$ of degree $n$. Then
%\[
%A(m) = \sum_{k = 0}^n \ b_k \ \binom{m + n - k}{n} \quad\Leftrightarrow\quad
%\sum_{m = 0}^\infty \ A(m)\ x^m \ = \frac{\sum_{k = 0}^n \ b_k \
% x^k}{(1 - x)^{n + 1}}
%\]
%as formal power series in ${\mathbb R}[[x]]$.
%\end{proposition}
The well-known {\em Eulerian numbers} $A_{nk}$ count permutations
in $S_n$ with $k$ descents. Similarly, {\em Eulerian numbers of type $B$}
are the numbers $B_{nk}$ of signed permutations in $B_n$ with $k$
descents. These numbers define the {\em Eulerian polynomials}:
\[
A_n(x)\DEF \sum_{k=0}^n A_{nk}x^k \qquad\mbox{ and }\qquad
B_n(x)\DEF \sum_{k=0}^n B_{nk}x^k.
\]
Refining also by the statistic $N(\pi)$,
Brenti \cite{FB} defined a $q$-analog to these polynomials, called
the {\em $q$-Eulerian polynomial}:
\[
B_n(x;q)\DEF \sum_{k=0}^n B_{nk}(q)x^k \DEF
\sum_{\pi\in B_n}q^{N(\pi)}x^{d(\pi)},
\]
where the polynomials $B_{nk}(q)$ are called
{\em $q$-Eulerian numbers}. For $q=1$ they reduce to the Eulerian
numbers of type $B$, and for $q=0$ they reduce to the ordinary
Eulerian numbers.
\section{Color-signed permutations}
{}From the definition of the $q$-Eulerian numbers, it is clear that
if the value of $q$ is a nonnegative integer, then so is $B_{nk}(q)$.
There is a simple combinatorial interpretation of $q$,
not mentioned by Brenti: If we {\em color
each minus sign by one of $q$ colors}, then $B_{nk}(q)$ is the
number of such $q$-color signed permutations in $B_n$ with $k$
descents. (Coloring does not affect what is meant by a descent.)
This interpretation allows an obvious generalization, namely,
{\em coloring the plus signs by one of $p$ colors}. Define the
$pq$-Eulerian number $B_{nk}(p,q)$ as the number of $pq$-color
signed permutations in $B_n$ with $k$ descents. A first observation
is that
$$\sum_{k=0}^n B_{nk}(p,q)=(p+q)^n n!,$$
since there is a choice among $p$ plus signs and $q$ minus signs
for every value of an unsigned permutation.
The $pq$-Eulerian numbers are easily expressed in terms of Brenti's
$q$-Eulerian numbers.
\begin{lemma}\label{lm:rel}
The $pq$-Eulerian numbers are related to the $q$-Eulerian numbers by
$$B_{nk}(p,q)=p^nB_{nk}(\frac{q}{p}).$$
\end{lemma}
\begin{proof}
Since this is a polynomial identity, it suffices to verify it
for all integers $p$ and $q$ such that $q$ is divisible by $p$.
Given one color for plus signs and $\frac{q}{p}$ colors for minus
signs, split every color into $p$ different subcolors. This gives
$p^n$ possible subcolorings for every original coloring.
\end{proof}
This simple relationship gives direct $pq$-analogues of
all Brenti's theorems for $q$-Eulerian numbers in Section 3
of \cite{FB}, dealing with recurrences, generating functions,
polynomial identities, log-concavity and unimodality.
Using the generating function, we obtain the following explicit
formula for the $pq$-Eulerian numbers.
\begin{theorem} \label{th: direct}
The $pq$-Eulerian numbers $B_{nk}(p, q)$ satisfy
\begin{align}
B_{nk}(p, q) &= \sum_{j = 0}^k \ \binom{n + 1}{j} (-1)^j ((p + q)(k -
j) + p)^n \notag \\
&= \sum_{j = k + 1}^{n + 1} \ \binom{n + 1}{j} (-1)^{j + 1} ((p + q)(k -
j) + p)^n. \notag
\end{align}
\end{theorem}
\begin{proof}
The proof follows the proof in Comtet \cite{LC}, p. 243, for ordinary
Eulerian numbers.
\end{proof}
We shall now present new, combinatorial, proofs of two of the
$pq$-analogues of Brenti's theorems, and then proceed with a further
generalization.
\begin{theorem} \label{th: recurrence}
The $pq$-Eulerian numbers satisfy the recurrence relation
\begin{align}
B_{nk}(p,q) &= (p(k+\!1) + qk)B_{n\!-\!1,k}(p,q) \notag \\
&\qquad + (p(n\!-\! k) + q(n\!-\! k+\! 1))B_{n\!-\!1,k\!-\!1}(p,q) \notag
%B_{nk}(p,q) = ((p + q)(n - k) + q)\ B_{n-1, k-1}(p,q) \ + ((p + q)k + p)\
%B_{n-1, k}(p,q),
\end{align}
and the boundary conditions $B_{00} = 1$ and
$B_{nk}= 0$ for $k<0$ and $k>n$.
\end{theorem}
\begin{proof}
The boundary conditions are obvious.
The first term of the recurrence counts ways to insert $\pm n$
into a signed $[n-1]$-permutation with $k$ descents, such that the
number of descents is unchanged. Either the $\pm n$ must go into an
old descent or a $+n$ goes last; in all, this gives
$p(k\!+\!1) + qk$ possibilities.
The second term has a similar interpretation.
\end{proof}
\begin{theorem}\label{th: id}
As a polynomial in $m$,
$$ (p(m+1)+qm)^n\
= \sum_{k = 0}^n\ B_{nk}(p, q)\ \binom{m + n - k}{n},
$$
for positive integers $n$.
\end{theorem}
In order to make the idea as clear as possible,
we shall present the combinatorial proof of Theorem \ref{th: id}
in a series of three cases of increasing generality.
\subsection{Splitting the hypercube, unsigned case}
For $p=1$ and $q=0$, Theorem \ref{th: id} specializes to the
following well-known identity for Eulerian numbers
(cf. Comtet \cite{LC}, p. 243):
\begin{equation} \label{eq: Euler-simplex}
(m+1)^n = \sum_{k = 0}^n \ A_{nk}\ \binom{m + n - k}{n}.
\end{equation}
For nonnegative integers $m$, the left-hand side can be interpreted as
the number of grid points in the $n$-dimensional hypercube
$\{(x_1,\dots,x_n)\in [0,m]^n \}$.
We would then like to
find a similar interpretation of the right-hand side. Let us divide
the hypercube into $n!$ simplices as follows:
To every permutation $\pi \in S_n$ corresponds a simplex
defined by the inequalities
\begin{equation} \label{eq: permutation}
0 \lessdot \ x_{\pi_1}\ \lessdot \ x_{\pi_2} \lessdot \ldots \lessdot
\ x_{\pi_n} \leq \ m.
\end{equation}
The symbol $\lessdot$ is defined in the following way:
\[
x_{\pi_k} \lessdot x_{\pi_{k+1}} =
\begin{cases}
x_{\pi_k} < x_{\pi_{k+1}}, &\text{if $\pi_k > \pi_{k+1}$, i.e. a descent;} \\
x_{\pi_k} \le x_{\pi_{k+1}}, &\text{if $\pi_k < \pi_{k+1}$}.
\end{cases}
\]
It is easy to see that these simplices are all disjoint and cover the hypercube.
\begin{example}
Let $n=m=2$.
\begin{center}
\begin{picture}(70, 80)(-20, -20)
\setlength{\unitlength}{0.6mm}
\put (-10,30){$x_2$}
\put (30,-5){$x_1$}
\put (10,-2){\line(0,1){4}}
\put (20,-2){\line(0,1){4}}
\put (-2,10){\line(1,0){4}}
\put (-2,20){\line(1,0){4}}
\put (10,10){\circle*{2}}
\put (10,20){\circle*{2}}
\put (20,10){\circle*{2}}
\put (20,20){\circle*{2}}
\put (-10,0){\vector(1, 0){40}}
\put (0,-10){\vector(0, 1){40}}
\put (0,0){\line(0, 1){20}}
\put (0,0){\line(1, 1){20}}
\put (0,20){\line(1, 0){20}}
\put (10,0){\line(1, 0){10}}
\put (10,0){\line(1, 1){10}}
\put (20,0){\line(0, 1){10}}
\end{picture}
\end{center}
The picture shows a larger simplex $0\le x_1\le x_2\le 2$, corresponding
to $\pi=12$, and a smaller simplex $0\le x_2< x_1\le 2$,
corresponding to $\pi=21$.
\end{example}
We remark that, apart from the rules about which region boundary points
belong to, the division of the hypercube is done by the well-known
hyperplane arrangement of type $A$.
The size of a simplex is the number of integral solutions to the
inequalities. If $k$ of the inequalities are strict, then by a
standard argument there are $\binom{m + n - k}{n}$ integral
solutions. Since there
are $A_{nk}$ permutations of [$n$] with $k$ descents, we have an
interpretation of the right hand side of (\ref{eq: Euler-simplex}).
\subsection{Splitting the hypercube, signed case}
For $p=q=1$, Theorem \ref{th: id} specializes to the
Eulerian identity of type $B$:
\begin{equation}
\label{eq: Bn-simplex}
(2m + 1)^n = \sum_{k = 0}^n \ B_{nk}\ \binom{m + n - k}{n}.
\end{equation}
We now interpret the left-hand side as the number of grid points in
the $n$-dimensional hypercube $\{(x_1,\dots,x_n)\in [-m,m]^n\}$.
The binomial part of the right-hand side still signifies the size of a
simplex, but the number of simplices of each size has now
changed. For a signed permutation $\pi\in B_n$, define
the meaning of $x_{\pi_i}$ to be $\sgn(\pi_i)x_{|\pi_i|}$.
This gives a well-defined meaning for signed permutations
to the simplex-defining inequalities (\ref{eq: permutation}),
(now corresponding to the so called $B$-arrangement)
and so explains the identity in a similar way as before.
\begin{example}
Let $n=m=2$.
\begin{center}
\begin{picture}(90, 100)(-40, -40)
\setlength{\unitlength}{0.6mm}
\put (-10,30){$x_2$}
\put (30,-5){$x_1$}
\put (10,-2){\line(0,1){4}}
\put (20,-2){\line(0,1){4}}
\put (-2,10){\line(1,0){4}}
\put (-2,20){\line(1,0){4}}
\put (-10,-2){\line(0,1){4}}
\put (-20,-2){\line(0,1){4}}
\put (-2,-10){\line(1,0){4}}
\put (-2,-20){\line(1,0){4}}
\put (10,10){\circle*{2}}
\put (10,20){\circle*{2}}
\put (20,10){\circle*{2}}
\put (20,20){\circle*{2}}
\put (-10,10){\circle*{2}}
\put (-10,20){\circle*{2}}
\put (-20,10){\circle*{2}}
\put (-20,20){\circle*{2}}
\put (10,-10){\circle*{2}}
\put (10,-20){\circle*{2}}
\put (20,-10){\circle*{2}}
\put (20,-20){\circle*{2}}
\put (-10,-10){\circle*{2}}
\put (-10,-20){\circle*{2}}
\put (-20,-10){\circle*{2}}
\put (-20,-20){\circle*{2}}
\put (0,0){\circle*{2}}
\put (0,10){\circle*{2}}
\put (0,20){\circle*{2}}
\put (0,-10){\circle*{2}}
\put (0,-20){\circle*{2}}
\put (10,0){\circle*{2}}
\put (20,0){\circle*{2}}
\put (-10,0){\circle*{2}}
\put (-20,0){\circle*{2}}
\put (-25,0){\vector(1, 0){55}}
\put (0,-25){\vector(0, 1){55}}
\put (-10,-10){\line(-1, 0){10}}
\put (-10,-10){\line(-1, -1){10}}
\put (-20,-10){\line(0, -1){10}}
\put (10,-10){\line(1, 0){10}}
\put (10,-10){\line(1, -1){10}}
\put (20,-10){\line(0, -1){10}}
\put (-10,10){\line(0,1){10}}
\put (-10,10){\line(-1, 1){10}}
\put (-10,20){\line(-1, 0){10}}
\put (-10,0){\line(-1, 0){10}}
\put (-10,0){\line(-1, 1){10}}
\put (-20,0){\line(0, 1){10}}
\put (0,-10){\line(0,-1){10}}
\put (0,-10){\line(1,-1){10}}
\put (0,-20){\line(1,0){10}}
\put (10,0){\line(1, 0){10}}
\put (10,0){\line(1, 1){10}}
\put (20,0){\line(0, 1){10}}
\put (20,20){\line(-1, 0){20}}
\put (20,20){\line(-1, -1){20}}
\put (0,20){\line(0, -1){20}}
\end{picture}
\end{center}
For instance, the smallest simplex is defined by
$0 < -x_1 < -x_2\le 2$, corresponding to $\pi=-1\ -2$.
\end{example}
Observe that a consequence of the inequalities (\ref{eq: permutation})
is that in the simplex corresponding to a signed permutation $\pi$,
the sign of the coordinate $x_{|\pi_i|}$ is always the sign of $\pi_i$.
\subsection{Splitting the hypercube, color-signed case}
The general identity, with $p$ colors of plus signs and $q$ colors of
minus signs, is
\begin{equation}
\label{eq: pq-simplex}
(p(m+1)\ + qm)^n\
= \sum_{k = 0}^n\ B_{nk}(p, q)\ \binom{m + n - k}{n}.
\end{equation}
The left-hand side is the size of a hypercube with side
length $p(m+1)+qm$. We obtain this by letting the range
of every coordinate be $[-m,m]$ with $p$ choices of color
for each nonnegative value and $q$ choices of color for each
negative value.
The simplex corresponding to a color-signed permutation $\pi$
is defined by (\ref{eq: permutation}) together with the definition
of the color of $x_{|\pi_i|}$ to be the color of the sign of $\pi_i$.
\begin{example}
Let $n=m=2$, and let $p=1$ and $q=2$.
\begin{center}
\begin{picture}(120, 130)(-75, -75)
\setlength{\unitlength}{0.6mm}
%\put (-10,50){$x_1$}
%\put (50,-5){$x_2$}
\put (-10,-2){\line(0,1){4}}
\put (-20,-2){\line(0,1){4}}
\put (-2,-10){\line(1,0){4}}
\put (-2,-20){\line(1,0){4}}
\put (10,-2){\line(0,1){4}}
\put (20,-2){\line(0,1){4}}
\put (-2,10){\line(1,0){4}}
\put (-2,20){\line(1,0){4}}
\put (-30,-2){\line(0,1){4}}
\put (-40,-2){\line(0,1){4}}
\put (-2,-30){\line(1,0){4}}
\put (-2,-40){\line(1,0){4}}
\put (-10,-30){\circle*{2}}
\put (-10,-40){\circle*{2}}
\put (-20,-30){\circle*{2}}
\put (-20,-40){\circle*{2}}
\put (0,-30){\circle*{2}}
\put (0,-40){\circle*{2}}
\put (10,-30){\circle*{2}}
\put (10,-40){\circle*{2}}
\put (20,-30){\circle*{2}}
\put (20,-40){\circle*{2}}
\put (-30,-30){\circle*{2}}
\put (-30,-40){\circle*{2}}
\put (-40,-30){\circle*{2}}
\put (-40,-40){\circle*{2}}
\put (-30,-10){\circle*{2}}
\put (-30,-20){\circle*{2}}
\put (-40,-10){\circle*{2}}
\put (-40,-20){\circle*{2}}
\put (-30,10){\circle*{2}}
\put (-40,0){\circle*{2}}
\put (-30,0){\circle*{2}}
\put (-30,20){\circle*{2}}
\put (-40,10){\circle*{2}}
\put (-40,20){\circle*{2}}
\put (10,10){\circle*{2}}
\put (10,20){\circle*{2}}
\put (20,10){\circle*{2}}
\put (20,20){\circle*{2}}
\put (-10,10){\circle*{2}}
\put (-10,20){\circle*{2}}
\put (-20,10){\circle*{2}}
\put (-20,20){\circle*{2}}
\put (10,-10){\circle*{2}}
\put (10,-20){\circle*{2}}
\put (20,-10){\circle*{2}}
\put (20,-20){\circle*{2}}
\put (-10,-10){\circle*{2}}
\put (-10,-20){\circle*{2}}
\put (-20,-10){\circle*{2}}
\put (-20,-20){\circle*{2}}
\put (0,0){\circle*{2}}
\put (0,10){\circle*{2}}
\put (0,20){\circle*{2}}
\put (0,-10){\circle*{2}}
\put (0,-20){\circle*{2}}
\put (10,0){\circle*{2}}
\put (20,0){\circle*{2}}
\put (-10,0){\circle*{2}}
\put (-20,0){\circle*{2}}
\put (25,0){\line(-1, 0){70}}
\put (0,25){\line(0, -1){70}}
\put (25,-25){\line(-1, 0){70}}
\put (-25,25){\line(0, -1){70}}
\put (-46,25){color 1}
\put (-22,25){color 2}
\put (25,-16){color 2}
\put (25,-40){color 1}
\put (-30,-10){\line(-1, 0){10}}
\put (-30,-10){\line(-1, -1){10}}
\put (-40,-10){\line(0, -1){10}}
\put (-10,-30){\line(-1, 0){10}}
\put (-10,-30){\line(-1, -1){10}}
\put (-20,-30){\line(0, -1){10}}
\put (-30,-30){\line(-1, 0){10}}
\put (-30,-30){\line(-1, -1){10}}
\put (-40,-30){\line(0, -1){10}}
\put (10,-30){\line(1, 0){10}}
\put (10,-30){\line(1, -1){10}}
\put (20,-30){\line(0, -1){10}}
\put (-30,10){\line(0,1){10}}
\put (-30,10){\line(-1, 1){10}}
\put (-30,20){\line(-1, 0){10}}
\put (-30,0){\line(-1, 0){10}}
\put (-30,0){\line(-1, 1){10}}
\put (-40,0){\line(0, 1){10}}
\put (0,-30){\line(0,-1){10}}
\put (0,-30){\line(1,-1){10}}
\put (0,-40){\line(1,0){10}}
\put (-10,-10){\line(-1, 0){10}}
\put (-10,-10){\line(-1, -1){10}}
\put (-20,-10){\line(0, -1){10}}
\put (10,-10){\line(1, 0){10}}
\put (10,-10){\line(1, -1){10}}
\put (20,-10){\line(0, -1){10}}
\put (-10,10){\line(0,1){10}}
\put (-10,10){\line(-1, 1){10}}
\put (-10,20){\line(-1, 0){10}}
\put (-10,0){\line(-1, 0){10}}
\put (-10,0){\line(-1, 1){10}}
\put (-20,0){\line(0, 1){10}}
\put (0,-10){\line(0,-1){10}}
\put (0,-10){\line(1,-1){10}}
\put (0,-20){\line(1,0){10}}
\put (10,0){\line(1, 0){10}}
\put (10,0){\line(1, 1){10}}
\put (20,0){\line(0, 1){10}}
\put (20,20){\line(-1, 0){20}}
\put (20,20){\line(-1, -1){20}}
\put (0,20){\line(0, -1){20}}
\end{picture}
\end{center}
\end{example}
For a color-signed permutation $\pi$, the color of the sign of
$x_{|\pi_i|}$ is the color of the sign of $\pi_i$.
\subsection{Different colors for different positions}
We can obtain other triangles of numbers by allowing a different number of
signs to some of the permutation values.
Say that we have $p'$ colors of plus signs and $q'$ colors of minus signs
for the $n'$ first values, and $p$ resp. $q$ colors for the remaining values.
We would then get a relation like this:
\begin{theorem}\label{re: triangles}
\[
(p'(m+1) + q'm)^{n'}\ (p(m+1) + qm)^{n - n'}\
= \sum_{k = 0}^n\ b_{nk}\ \binom{m + n - k}{n}.
\]
The numbers $b_{nk}$ are determined by the recurrence in
Theorem \ref{th: recurrence}, using $p', q'$ up to $n'$, and thereafter
continuing with $p, q$.
\end{theorem}
Finally, we make a note that all the above polynomial identities can be
translated into power series identities by the following
well-known formula for generating functions:
\begin{equation}\label{eq:poly-power}
A(m) = \sum_{k = 0}^n \ b_{nk} \ \binom{m + n - k}{n} \quad\Leftrightarrow\quad
\sum_{m = 0}^\infty \ A(m)\ x^m \ =
\frac{\sum_{k = 0}^n \ b_{nk} \ x^k}{(1 - x)^{n + 1}}
\end{equation}
\subsection{Deriving identity (\ref{niklas-id})}\label{sc:id}
With $p´=0$ and $q´=1$ for $n'=1$, while $p=1$ and $q=1$ for higher $n$,
Theorem \ref{re: triangles} gives the following identity:
$$ m(2m+1)^{n-1} = \sum_{k= 0}^n\ b_{nk}\ \binom{m + n - k}{n},$$
with the numbers $b_{nk}$ defined by $b_{10}=1$, $b_{11}=0$ and,
for $n>1$, by the standard recurrence for $p=q=1$.
Identity (\ref{eq:poly-power}) yields
$$\sum_{m=0}^\infty \ m(2m+1)^{n-1}\ x^m \ =
\frac{\sum_{k = 0}^n \ b_{nk} \ x^k}{(1 - x)^{n + 1}}.$$
If we now take $x=\sigma=(\sqrt5 -1)/2$ and use the fact that
$1-\sigma=\sigma^2$, we obtain identity (\ref{niklas-id}) as promised
in the introduction.
\section{Playing diagonal \Pegs\ in ${\mathbb Z}^n$}
\label{sc:pegs}
Peg solitaire, or \Pegs, is one of the most famous board games for one person.
It is played on a board with 33 holes, 32 of which are occupied by a peg,
and the objective is to get rid of all pegs but one. (Detailed
descriptions, and some interesting generalizations can be found in
Berlekamp, Conway and Guy \cite{EB} and in Eriksen \cite{NE}). A move can be
made whenever there are two adjacent pegs next to an empty hole, all in the
same row or column. Then the outer peg may jump over the middle peg
into the empty hole, thereby removing the middle peg. With white pegs and
black holes, it looks like this:
\begin{center}
\begin{picture}(100,12)
\put (10,3){\circle{8}}
\put (20,3){\circle{8}}
\put (30,3){\circle*{3}}
\put (40,3){\vector(1,0){20}}
\put (70,3){\circle*{3}}
\put (80,3){\circle*{3}}
\put (90,3){\circle{8}}
\end{picture}
\end{center}
One can of course play \Pegs\ on other boards than the traditional one.
In \cite{EB}, the following situation is studied: Use ${\mathbb Z}^2$ as our board,
with the entire lower half plane (including $y = 0$) filled with pegs and
the upper half plane empty. How far up into the upper half plane
can you put a peg, using \Pegs\ moves? The answer is that although there is
an infinite number of pegs to use, one can only reach the fourth row!
The reachability problem was generalized to ${\mathbb Z}^n$, $n\geq 2$,
by H.~Eriksson and Lindstr\"om \cite{HE&BL}:
\begin{theorem} [Eriksson and Lindstr\"om \cite{HE&BL}] \label{Theo: HE1}
When playing \Pegs\ on ${\mathbb Z}^n$, starting with pegs in all holes
with coordinates $(x_1, x_2, \ldots, x_n)$
such that $x_n \leq 0$, it is impossible to play a peg into any hole with
$x_n \geq 3n - 1$.
\end{theorem}
Eriksson and Lindstr\"om also prove that the bound is sharp: a good
player can always reach level $x_n = 3n - 2$. They remark
that allowing L-moves of the following kind will not increase the range.
\begin{center}
\begin{picture}(71,12)(5,2)
\put (10,3){\circle{6}}
\put (20,3){\circle{6}}
\put (20,13){\circle*{3}}
\put (30,5){\vector(1,0){20}}
\put (60,3){\circle*{3}}
\put (70,3){\circle*{3}}
\put (70,13){\circle{6}}
\end{picture}
\end{center}
In the present paper, we will study how far pegs can reach
when {\em diagonal moves} are allowed, such as
\begin{center}
\begin{picture}(71,22)(5,2)
\put (10,3){\circle{6}}
\put (20,13){\circle{6}}
\put (30,23){\circle*{3}}
\put (40,10){\vector(1,0){20}}
\put (70,3){\circle*{3}}
\put (80,13){\circle*{3}}
\put (90,23){\circle{6}}
\end{picture}
\end{center}
\subsection{The pagoda function}
We will use the standard tool for this kind of problems: the
{\em pagoda function} introduced in \cite{EB}. A pagoda function is a function $P({\bf x})$ that
assigns a real value to each position on the board, with the property that
the sum of the values of all peg positions can
never increase by a legal move.
In our case, the board is ${\mathbb Z}^n$ and the initial peg distribution is
a filled halfspace. The pagoda function is now used as follows. Let
$$f(n,k)\DEF \sum_{{\bf x}:x_n\le -k} P({\bf x}).$$
Then if we find a value of $k$ such that $f(n,k)\le P(\bar 0)$, this implies
that it is impossible to reach $k$ levels above the peg-filled halfspace,
since the pagoda function cannot increase.
Thus our first task is to find a good pagoda function. In the analysis of the classical
case where no diagonal moves are allowed \cite{EB,HE&BL}, the pagoda function was taken to be
$P_{\rm classic}({\bf x})= \sigma^{|x_1|+\dots+|x_n|}$, where $\sigma=(\sqrt 5 - 1)/2$.
It is easy to verify that this is a proper pagoda function, using the equation $\sigma^2+\sigma=1$.
When diagonal moves are allowed too, the above function is no longer a proper pagoda function.
We will instead define
\begin{equation}
P({\bf x})\DEF\sigma^{\max |x_i|},
\end{equation}
for which the pagoda property
is easily verified.
We have $P(\bar{0}) = 1$, so if $f(n, k)\leq 1$
for some $n$ and $k$, then we cannot reach the $k$th level in
${\mathbb Z}^n$. Calculating $f(n, k)$ will thus provide us with an
upper limit on the range of the pegs.
\subsection{Computation of $f(n,k)$}
Computation of the function $f(n,k)$ is not trivial, and we will
approach the problem in several steps. To begin with, we can find
a recurrence involving an infinite sum.
\begin{lemma} \label{le: recur1}
The numbers $f(n,k)$ satisfy the recurrence
\[
f(n,k) = 4 \sum_{l = k + 1}^{\infty} f(n - 1, l) + (2k + 1) f(n - 1,
k),
\]
with the initial values
\[
f(1, k) = \sigma^{k - 2}.
\]
\end{lemma}
\begin{proof}
Let us first verify the initial values. We first observe that in
${\mathbb Z}^1$, we get a single line of $\sigma, \sigma^2, \sigma^3,
\ldots$. Simple calculations give
\[
f(1, k) = \sum_{\ell = k}^{\infty} \sigma^\ell = \frac{\sigma^k}{1 - \sigma}
= \sigma^{k - 2}.
\]
For the recurrence, we start with the case $n=2$. Figure \ref{diapegs pagoda} shows
the $\sigma$-logarithm of the Pagoda function. (The zero is, of course, at the origin.)
First we calculate $f(2, 1)$: On the right side of the middle column, we have, diagonally, a sum equivalent to $f(1,1)$ running from (1, -1), two $f(1,2)$s running from (1, -2) and (2, -1), two $f(1,3)$s, etc. The same goes for the left side, and the middle column will produce a $f(1,1)$, giving a total of $f(2,1)=3 f(1,1) + 4 f(1,2) + 4 f(1,3) + \ldots$.
\begin{figure}[htb]
\begin{center}
\begin{picture}(180, 80)(0, 20)
\setlength{\unitlength}{0.6mm}
\put (10,50){4}
\put (20,50){3}
\put (30,50){2}
\put (40,50){1}
\put (50,50){0}
\put (60,50){1}
\put (70,50){2}
\put (80,50){3}
\put (90,50){4}
\put (10,40){4}
\put (20,40){3}
\put (30,40){2}
\put (40,40){1}
\put (50,40){1}
\put (60,40){1}
\put (70,40){2}
\put (80,40){3}
\put (90,40){4}
\put (10,30){4}
\put (20,30){3}
\put (30,30){2}
\put (40,30){2}
\put (50,30){2}
\put (60,30){2}
\put (70,30){2}
\put (80,30){3}
\put (90,30){4}
\put (10,20){4}
\put (20,20){3}
\put (30,20){3}
\put (40,20){3}
\put (50,20){3}
\put (60,20){3}
\put (70,20){3}
\put (80,20){3}
\put (90,20){4}
\put (10,10){4}
\put (20,10){4}
\put (30,10){4}
\put (40,10){4}
\put (50,10){4}
\put (60,10){4}
\put (70,10){4}
\put (80,10){4}
\put (90,10){4}
\put (-10, 47) {\line(1, 0){125}}
\end{picture}
\end{center}
\caption{The $\sigma$-logarithm of the Pagoda function} \label{diapegs pagoda}
\end{figure}
Calculating $f(2,2)$ is done in an analogous way: We get nice diagonals on the right
and the sides if we first remove the three middle columns. The total weight will
then be $5 f(1,2) + 4 f(1,3) + 4 f(1,4) + \ldots$. An inductive argument then shows
that the recursion is valid for every $f(2, k)$, proving the formula correct for $n = 2$.
Higher dimensions can be dealt with in the same manner. For example, in order to
compute $f(3, 1)$, use the vertical plane in the middle ($x_2 = 0$) as a divider and
consider the right and left sides. On each, we have one $f(2, 1)$, two $f(2,2)$s,
two $f(2,3)$s etc. Together with the dividing plane, which equals $f(2, 1)$, we get
$f(3,1)=3 f(2,1) + 4 f(2,2) + 4 f(2,3) + \ldots$, and the argument obviously applies
to all $f(n,k)$.
\end{proof}
{}From this recursion, we can write $f$ as a linear function of $k$,
making it easy to find the smallest value of $k$ such that
$f(n,k) \leq 1$, for any given $n$, provided the value
of $f(j,1)$ is known for all $j\le n$.
\begin{lemma}
The function $f(n,k)$ is given by the formula
\[
f(n,k)=f(n,1)-2(k-1)\sum_{j=1}^{n-1}f(j,1).
\]
Hence in particular, $f$ is a linear function of $k$. The smallest value of
$k$ for which $f(n,k) \leq 1$ is clearly
\[
k^*(n)=1+\left\lceil{\frac{f(n,1)-1}{2\sum_{j=1}^{n-1}f(j,1)}}\right\rceil .
\]
\end{lemma}
\begin{proof}
First we simplify the recursion a bit. Using $k-1$ instead of $k$, we obtain
\[
f(n,k-1) = 4 \sum_{l = k}^{\infty} f(n - 1, l) + (2k - 1) f(n - 1, k-1),
\]
and subtracting the second recursion from the first gives
\[
f(n,k) - f(n,k-1) = (2k - 3)f(n-1,k) - (2k-1)f(n-1,k-1).
\]
Let us now assume that $f(n,k)$ can be written in the form
\[f(n,k)=f(n,1)-(k-1)h(n),\]
where $h$ does not depend on $k$ and is to be determined. We then
substitute this into the expression above and extract $h(n)$.
\end{proof}
In order to be able to use the above formula, our next step is to calculate $f(n, 1)$.
\begin{lemma}
The value of all holes with $x_n \leq -1$ in ${\mathbb Z}^n$, is given
by
\[
f(n, 1) = \sigma^2 \sum_{m = 1}^{\infty}\ m\ (2m + 1)^{n - 1}\sigma^m.
\]
\end{lemma}
\begin{proof}
We wish to compute the total value of the holes with $x_n \leq -1$. This
value is equal to the value of the holes with $x_n \geq 1$.
Hence, if we let $g(n)$ be the value of all holes in ${\mathbb Z}^n$, then
we can subtract the total value of the hyperplane $x_n = 0$ and
divide the difference by two to obtain $f(n,1)$.
But the value of the hyperplane is $g(n-1)$. Thus, we have proved that
\begin{equation} \label{eq: g}
f(n,1) = \frac{g(n) - g(n-1)}{2}
\end{equation}
The holes in ${\mathbb Z}^n$
with value $\sigma^m$, for a fixed $m \geq 1$, constitute
the outer shell of an $n$-dimensional hypercube centered around the origin,
with side length $2m+1$ The
number of such holes is therefore $(2m + 1)^n - (2m - 1)^n$. Using
\eqref{eq: g}, we now obtain
\begin{align}
f(n, 1) &= \sum_{m = 1}^\infty \ \frac{((2m + 1)^n - (2m - 1)^n) -
((2m + 1)^{n - 1} - (2m - 1)^{n - 1})}{2}\ \sigma^m \notag \\
&= \sum_{m = 1}^\infty \ \frac{(2m + 1 - 1)(2m + 1)^{n - 1} -
(2m - 1 - 1)(2m - 1)^{n - 1}}{2}\ \sigma^m \notag \\
&= \sum_{m = 1}^{\infty} \ (m(2m + 1)^{n - 1} -
(m - 1)(2m -1)^{n - 1}) \sigma^m \notag \\
&=\ \sum_{m = 1}^{\infty} m(2m + 1)^{n - 1} \sigma^m -
\sum_{m = 0}^{\infty} m(2m + 1)^{n - 1} \sigma^{m + 1} \notag \\
&=\ \sum_{m = 1}^{\infty}\ m\ (2m + 1)^{n - 1}\ \sigma^{m+2}
\notag
\end{align}
\end{proof}
Finally, we observe that this infinite sum is computable via
identity (\ref{niklas-id}), which was proved in Section \ref{sc:id}.
Hence, we have a way of computing $k^*(n)$. The results
are collected in the below theorem.
We are now ready to state the theorem, which follows directly from the
lemmas.
\begin{theorem}
Suppose that the half-space $x_n \leq 0$ is filled with pegs and the
rest of ${\mathbb Z}^n$ is empty.
Then the range of the pegs is bounded, even if we allow diagonal
moves. Upper bounds for small values of $n$ can be found in Table
\ref{table: diapegs}.
\end{theorem}
\begin{table} [htb]
\caption{Unreachable levels of \Diapegs\ in ${\mathbb Z}^n$} \label{table: diapegs}
\begin{center}
\begin{tabular} {r r r @{.} l r @{.} l}
$n$ & unreachable level $k^*$ & \multicolumn{2}{c}{$f(n, k^*)$} & \multicolumn{2}{c}{$f(n, k^* - 1)$} \\
\hline
1 & 2 & 1 & 000 & 1 & 618 \\
2 & 9 & 0 & 877 & 1 & 308 \\
3 & 18 & 0 & 872 & 1 & 286 \\
4 & 28 & 0 & 967 & 1 & 424 \\
5 & 40 & 0 & 689 & 1 & 017 \\
6 & 51 & 0 & 932 & 1 & 376 \\
7 & 64 & 0 & 703 & 1 & 041 \\
\end{tabular}
\end{center}
\end{table}
\subsection{Lower bounds}
When Eriksson and Lindstr\"om \cite{HE&BL} proved that the upper bounds
could be attained in the case where diagonal moves are not allowed, they
showed how a successful construction in two dimensions could be used
iteratively to solve the problem in higher dimensions. Such a scheme does
not seem likely to succeed when diagonal moves are allowed, since every time
the dimension is increased a new type of diagonal move is introduced.
We have no nontrivial general lower bounds.
However, using ad hoc methods we have constructed a game in ${\mathbb Z}^2$
that reaches level 8, so here the upper bound is sharp! It is possible that
the bounds are sharp for all $n$, but completely new construction ideas
would be needed to prove such a result.
%Judging from the table values, it seems hard to reach the 39:th level
%in ${\mathbb Z}^5$.
\begin{thebibliography}{ABC}
\bibitem{EB} E. R. Berlekamp, J. H. Conway, R. K. Guy, {\em Winning ways}, Academic Press, London, 1982, vol. 2, 697-734.
\bibitem{FB} F. Brenti, $q$-Eulerian Polynomials Arising from Coxeter
Groups, {\em Europ. J. Combinatorics} {\bf 15} (1994), 417--441.
\bibitem{LC} L. Comtet, {\em Advanced Combinatorics}, D. Reidel Publishing Company. Dordrecht, 1974.
\bibitem{NE} N. Eriksen, {\sc Pegs}, {\sc Pebbles}, {\sc Pennies} and
{\sc Piles} --- a study of some combinatorial games, Master thesis,
KTH, 1999.
\bibitem{HE&BL} H. Eriksson and B. Lindstr\"om, Twin jumping checkers
in ${\mathbb Z}^d$, {\em Europ. J. Combinatorics} \textbf{16}, 1995, 153--157.
\bibitem{RS} R. Stanley, {\em Enumerative Combinatorics}, vol. 1,
Cambridge University Press, Cambridge, 1997.
\bibitem{DZ} D. Zeilberger, personal communication, 1999.
\end{thebibliography}
\end{document}