DIAGONAL CHECKER-JUMPING AND

EULERIAN NUMBERS FOR COLOR-SIGNED PERMUTATIONS

Niklas Eriksen ^{∗}  Henrik Eriksson ^{†}  Kimmo Eriksson ^{‡}

     niklas@math.kth.se    henrik@nada.kth.se    Kimmo.Eriksson@mdh.se

∗ Department of Mathematics, KTH, SE-100 44 Stockholm, Sweden
† NADA, KTH, SE-100 44 Stockholm, Sweden
‡ IMa, Mälardalens högskola, Box 883, SE-721 23 Västerås, Sweden

Submitted: September 2, 1999; Accepted: January 26, 2000.

Abstract. We introduce 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 checkerjumping problem, when the rules are relaxed to allow also diagonal jumps.

1. Introduction

This paper has two themes. First, we will present a notion of 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 [2], 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 [1]). H. Eriksson and Lindström generalized checker-jumping to higher dimensions [5]. In his M.Sc. thesis, Eriksen [4] 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.

1991 Mathematics Subject Classification. Primary: 05A30; Secondary: 05A99.

Key words and phrases. Eulerian numbers, color-signed permutations, checker-jumping, pagoda function.

N.E.: Partially supported by the Swedish Natural Science Research Council.

K.E.: Partially supported by the Swedish Natural Science Research Council and the Swedish Foundation for Strategic Research.

The connection between the two themes is the following identity: Let n be a positive integer and let σ denote the golden ratio (\sqrt{5} − 1)/2. Then

∑_{m=1}^{∞} m (2m + 1)^{n−1} σ^{m+2} = σ^{−2n} ∑_{k=1}^{n} b_{nk}σ^{k}, (1)

where the numbers b_{nk} are defined by b_{1,1} = 1, b_{nk} = 0 for k ≤ 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:

k = 1 2 3 4
n = 1  1
2  3 1
3  9 14 1
4  27 115 49 1

The identity (1) is needed for computation of the upper bound in the checkerjumping problem. Zeilberger (personal communication) told us how (1) could be proved using induction. Our own search for a combinatorial proof led us to the idea of color-signed permutations.

2. Preliminaries on Eulerian and q-Eulerian numbers

Let [n] denote the integer set {1, …, 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 π by its sequence π_{1} … π_{n} of values.

Two statistics on permutations will be important: the number of descents and the number of minus signs. A descent is a position i where the permutation value decreases: π_{i−1} > π_{i}. When counting descents we always have the convention that π_{0} = 0. Let d(π) denote the number of descents of a signed permutation π. The number of minus signs (resp. plus signs) in a signed permutation π ∈ B_{n} is denoted by N(π) (resp. P (π)). In other words,

N(π) =^{def} #{i ∈ [n] : π_{i} < 0}  and  P (π) =^{def} n − N(π).

The well-known Eulerian numbers A_{nk} count permutations in S_{n} with k descents. Similarly, Eulerian numbers of type B are the numbers B_{nk} of signed permutations in B_{n} with k descents. These numbers define the Eulerian polynomials:

A_{n}(x) =^{def} ∑_{k=0}^{n} A_{nk}x^{k}  and  B_{n}(x) =^{def} ∑_{k=0}^{n} B_{nk}x^{k}.

Refining also by the statistic N(π), Brenti [2] defined a q-analog to these polynomials, called the q-Eulerian polynomial:

B_{n}(x; q) =^{def} ∑_{k=0}^{n} B_{nk}(q)x^{k} =^{def} ∑_{π∈B_{n}} q^{N(π)}x^{d(π)},

where the polynomials B_{nk}(q) are called 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.

3. 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 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, 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

∑_{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.

Lemma 3.1. The pq-Eulerian numbers are related to the q-Eulerian numbers by

B_{nk}(p, q) = p^{n}B_{nk}(\frac{q}{p}).

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.

This simple relationship gives direct pq-analogues of all Brenti’s theorems for q-Eulerian numbers in Section 3 of [2], 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.

Theorem 3.2. The pq-Eulerian numbers B_{nk}(p, q) satisfy

B_{nk}(p, q) = ∑_{j=0}^{k} \binom{n + 1}{j}(−1)^{j}((p + q)(k − j) + p)^{n}

= ∑_{j=k+1}^{n+1} \binom{n + 1}{j}(−1)^{j+1}((p + q)(k − j) + p)^{n}.

Proof. The proof follows the proof in Comtet [3], p. 243, for ordinary Eulerian numbers.

We shall now present new, combinatorial, proofs of two of the pq-analogues of Brenti’s theorems, and then proceed with a further generalization.

Theorem 3.3. The pq-Eulerian numbers satisfy the recurrence relation

B_{nk}(p, q) = (p(k +1) + qk)B_{n−1,k}(p, q)
+ (p(n−k) + q(n−k +1))B_{n−1,k−1}(p, q)

and the boundary conditions B_{00} = 1 and B_{nk} = 0 for k < 0 and k > n.

Proof. The boundary conditions are obvious. The first term of the recurrence counts ways to insert ±n into a signed [n − 1]-permutation with k descents, such that the number of descents is unchanged. Either the ±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.

Theorem 3.4. As a polynomial in m,

(p(m + 1) + qm)^{n} = ∑_{k=0}^{n} B_{nk}(p, q) \binom{m + n − k}{n},

for positive integers n.

In order to make the idea as clear as possible, we shall present the combinatorial proof of Theorem 3.4 in a series of three cases of increasing generality.

3.1. Splitting the hypercube, unsigned case. For p = 1 and q = 0, Theorem 3.4 specializes to the following well-known identity for Eulerian numbers (cf. Comtet [3], p. 243):

(m + 1)^{n} = ∑_{k=0}^{n} A_{nk} \binom{m + n − k}{n}. (2)

For nonnegative integers m, the left-hand side can be interpreted as the number of grid points in the n-dimensional hypercube {(x_{1}, …, x_{n}) ∈ [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 π ∈ S_{n} corresponds a simplex defined by the inequalities

0 ⋖ x_{π_{1}} ⋖ x_{π_{2}} ⋖ … ⋖ x_{π_{n}} ≤ m. (3)

The symbol ⋖ is defined in the following way:

x_{π_{k}} ⋖ x_{π_{k+1}} = \begin{cases}x_{π_{k}} < x_{π_{k+1}}, & if π_{k} > π_{k+1}, i.e. a descent; \\ x_{π_{k}} ≤ x_{π_{k+1}}, & if π_{k} < π_{k+1}. \end{cases}

It is easy to see that these simplices are all disjoint and cover the hypercube.

Example 3.5. Let n = m = 2.

[figure: x_{2}; x_{1}]

The picture shows a larger simplex 0 ≤ x_{1} ≤ x_{2} ≤ 2, corresponding to π = 12, and a smaller simplex 0 ≤ x_{2} < x_{1} ≤ 2, corresponding to π = 21.

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 (2).

3.2. Splitting the hypercube, signed case. For p = q = 1, Theorem 3.4 specializes to the Eulerian identity of type B:

(2m + 1)^{n} = ∑_{k=0}^{n} B_{nk} \binom{m + n − k}{n}. (4)

We now interpret the left-hand side as the number of grid points in the n-dimensional hypercube {(x_{1}, …, x_{n}) ∈ [−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 π ∈ B_{n}, define the meaning of x_{π_{i}} to be sgn(π_{i})x_{|π_{i}|}. This gives a well-defined meaning for signed permutations to the simplexdefining inequalities (3), (now corresponding to the so called B-arrangement) and so explains the identity in a similar way as before.

Example 3.6. Let n = m = 2.

[figure: x_{2}; x_{1}]

For instance, the smallest simplex is defined by 0 < −x_{1} < −x_{2} ≤ 2, corresponding to π = −1 − 2.

Observe that a consequence of the inequalities (3) is that in the simplex corresponding to a signed permutation π, the sign of the coordinate x_{|π_{i}|} is always the sign of π_{i}.

3.3. Splitting the hypercube, color-signed case. The general identity, with p colors of plus signs and q colors of minus signs, is

(p(m + 1) + qm)^{n} = ∑_{k=0}^{n} B_{nk}(p, q) \binom{m + n − k}{n}. (5)

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 π is defined by (3) together with the definition of the color of x_{|π_{i}|} to be the color of the sign of π_{i}.

Example 3.7. Let n = m = 2, and let p = 1 and q = 2.

[figure: color 1; color 2; color 2; color 1]

For a color-signed permutation π, the color of the sign of x_{|π_{i}|} is the color of the sign of π_{i}.

3.4. 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:

Theorem 3.8.

(p′(m + 1) + q′m)^{n′} (p(m + 1) + qm)^{n−n′} = ∑_{k=0}^{n} b_{nk} \binom{m + n − k}{n}.

The numbers b_{nk} are determined by the recurrence in Theorem 3.3, using p′, q′ up to n′, and thereafter continuing with p, q.

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:

A(m) = ∑_{k=0}^{n} b_{nk} \binom{m + n − k}{n} ⇔ ∑_{m=0}^{∞} A(m) x^{m} = \frac{∑_{k=0}^{n} b_{nk} x^{k}}{(1 − x)^{n+1}} (6)

3.5. Deriving identity (1). With p = 0 and q = 1 for n′ = 1, while p = 1 and q = 1 for higher n, Theorem 3.8 gives the following identity:

m(2m + 1)^{n−1} = ∑_{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 (6) yields

∑_{m=0}^{∞} m(2m + 1)^{n−1} x^{m} = \frac{∑_{k=0}^{n} b_{nk} x^{k}}{(1 − x)^{n+1}} .

If we now take x = σ = (\sqrt{5} − 1)/2 and use the fact that 1 − σ = σ^{2}, we obtain identity (1) as promised in the introduction.

4. Playing diagonal Pegs in ℤ^{n}

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 [1] and in Eriksen [4]). 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:

[figure]

One can of course play Pegs on other boards than the traditional one. In [1], the following situation is studied: Use ℤ^{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 ℤ^{n}, n ≥ 2, by H. Eriksson and Lindström [5]:

Theorem 4.1 (Eriksson and Lindström [5]). When playing Pegs on ℤ^{n}, starting with pegs in all holes with coordinates (x_{1}, x_{2}, …, x_{n}) such that x_{n} ≤ 0, it is impossible to play a peg into any hole with x_{n} ≥ 3n − 1.

Eriksson and Lindström 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.

[figure]

In the present paper, we will study how far pegs can reach when diagonal moves are allowed, such as

[figure]

4.1. The pagoda function. We will use the standard tool for this kind of problems: the pagoda function introduced in [1]. A pagoda function is a function P (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 ℤ^{n} and the initial peg distribution is a filled halfspace. The pagoda function is now used as follows. Let

f(n, k) =^{def} ∑_{x:x_{n}≤−k} P (x).

Then if we find a value of k such that f(n, k) ≤ P (¯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 [1, 5], the pagoda function was taken to be P_{classic}(x) = σ^{|x_{1}|+···+|x_{n}|}, where σ = (\sqrt{5} − 1)/2. It is easy to verify that this is a proper pagoda function, using the equation σ^{2} + σ = 1.

When diagonal moves are allowed too, the above function is no longer a proper pagoda function. We will instead define

P (x) =^{def} σ^{max |x_{i}|}, (7)

for which the pagoda property is easily verified.

We have P (¯0) = 1, so if f(n, k) ≤ 1 for some n and k, then we cannot reach the kth level in ℤ^{n}. Calculating f(n, k) will thus provide us with an upper limit on the range of the pegs.

4.2. 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.

Lemma 4.2. The numbers f(n, k) satisfy the recurrence

f(n, k) = 4 ∑_{l=k+1}^{∞} f(n − 1, l) + (2k + 1)f(n − 1, k),

with the initial values

f(1, k) = σ^{k−2}.

Proof. Let us first verify the initial values. We first observe that in ℤ^{1}, we get a single line of σ, σ^{2}, σ^{3}, . . .. Simple calculations give

f(1, k) = ∑_{ℓ=k}^{∞} σ^{ℓ} = \frac{σ^{k}}{1 − σ} = σ^{k−2}.

For the recurrence, we start with the case n = 2. Figure 1 shows the σ-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) = 3f(1, 1) + 4f(1, 2) + 4f(1, 3) + . . ..

4 3 2 1 0 1 2 3 4 4 3 2 1 1 1 2 3 4 4 3 2 2 2 2 2 3 4 4 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4

Figure 1. The σ-logarithm of the Pagoda function

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 5f(1, 2) + 4f(1, 3) + 4f(1, 4) + . . .. 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) = 3f(2, 1) + 4f(2, 2) + 4f(2, 3) + …, and the argument obviously applies to all f(n, k).

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) ≤ 1, for any given n, provided the value of f(j, 1) is known for all j ≤ n.

Lemma 4.3. The function f(n, k) is given by the formula

f(n, k) = f(n, 1) − 2(k − 1) ∑_{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) ≤ 1 is clearly

k^{∗}(n) = 1 + ⌈\frac{f(n, 1) − 1}{2 ∑_{j=1}^{n−1} f(j, 1)}⌉ .

Proof. First we simplify the recursion a bit. Using k − 1 instead of k, we obtain

f(n, k − 1) = 4 ∑_{l=k}^{∞} 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).

In order to be able to use the above formula, our next step is to calculate f(n, 1).

Lemma 4.4. The value of all holes with x_{n} ≤ −1 in ℤ^{n}, is given by

f(n, 1) = σ^{2} ∑_{m=1}^{∞} m (2m + 1)^{n−1}σ^{m}.

Proof. We wish to compute the total value of the holes with x_{n} ≤ −1. This value is equal to the value of the holes with x_{n} ≥ 1. Hence, if we let g(n) be the value of all holes in ℤ^{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

f(n, 1) = \frac{g(n) − g(n − 1)}{2} (8)

The holes in ℤ^{n} with value σ^{m}, for a fixed m ≥ 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 (8), we now obtain

f(n, 1) = ∑_{m=1}^{∞} \frac{((2m + 1)^{n} − (2m − 1)^{n}) − ((2m + 1)^{n−1} − (2m − 1)^{n−1})}{2} σ^{m}

= ∑_{m=1}^{∞} \frac{(2m + 1 − 1)(2m + 1)^{n−1} − (2m − 1 − 1)(2m − 1)^{n−1}}{2} σ^{m}

= ∑_{m=1}^{∞} (m(2m + 1)^{n−1} − (m − 1)(2m − 1)^{n−1})σ^{m}

= ∑_{m=1}^{∞} m(2m + 1)^{n−1}σ^{m} − ∑_{m=0}^{∞} m(2m + 1)^{n−1}σ^{m+1}

= ∑_{m=1}^{∞} m (2m + 1)^{n−1} σ^{m+2}

Finally, we observe that this infinite sum is computable via identity (1), which was proved in Section 3.5. 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.

Theorem 4.5. Suppose that the half-space x_{n} ≤ 0 is filled with pegs and the rest of ℤ^{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 1.

Table 1. Unreachable levels of Diapegs in ℤ^{n}

n unreachable level k^{∗} f(n, k^{∗}) f(n, k^{∗} − 1)
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

4.3. Lower bounds. When Eriksson and Lindström [5] 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 ℤ^{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.

References

[1] E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning ways, Academic Press, London, 1982, vol. 2, 697-734.

[2] F. Brenti, q-Eulerian Polynomials Arising from Coxeter Groups, Europ. J. Combinatorics 15 (1994), 417–441.

[3] L. Comtet, Advanced Combinatorics, D. Reidel Publishing Company. Dordrecht, 1974.

[4] N. Eriksen, Pegs, Pebbles, Pennies and Piles — a study of some combinatorial games, Master thesis, KTH, 1999.

[5] H. Eriksson and B. Lindström, Twin jumping checkers in ℤ^{d}, Europ. J. Combinatorics 16, 1995, 153–157.

[6] R. Stanley, Enumerative Combinatorics, vol. 1, Cambridge University Press, Cambridge, 1997.

[7] D. Zeilberger, personal communication, 1999.