Combinatorial Proof of an Identity on Genocchi Numbers

Beáta Bényi Faculty of Water Sciences University of Public Service H-1441 Budapest, P.O. Box 60 Hungary

                    benyi.beata@uni-nke.hu

Matthieu Josuat-Vergès CNRS, IRIF (UMR 8243) Université de Paris FRANCE

                matthieu.josuat-verges@u-pem.fr

Abstract In this note we present a combinatorial proof of an identity involving poly-Bernoulli numbers and Genocchi numbers. We introduce combinatorial objects called m-barred Callan sequences and use them to show that the identity holds in a more general manner.

1 Introduction

In this paper we present a combinatorial proof of an identity that establishes an interesting relation between the C-poly-Bernoulli numbers and Genocchi numbers. The Genocchi numbers, G_{n}, can be defined by the generating function [13, Exercise 5.8]

∑_{n=0}^{∞} G_{n} \frac{t^{n}}{n!} = \frac{2t}{e^{t} + 1}.

The first few values are

0, 1, −1, 0, 1, 0, −3, 0, 17, 0, −155, …

(see \underline{A036968} in the OEIS (On-Line Encyclopedia of Integer Sequences) [12]).

The poly-Bernoulli numbers B_{n}^{(k)} are defined for k ∈ ℤ by

\frac{Li_{k}(1 − e^{−t})}{1 − e^{−t}} = ∑_{n=0}^{∞} B_{n}^{(k)} \frac{t^{n}}{n!},  (1)

where Li_{k}(z) is the polylogarithm function given by

Li_{k}(z) = ∑_{m=1}^{∞} \frac{z^{m}}{m^{k}} (|z| < 1).

For negative k indices, the poly-Bernoulli numbers are integers (\underline{A099594} in [12]). Several combinatorial objects are enumerated by these numbers, for instance, lonesum matrices [7], matrices uniquely reconstructible from their row and column sum vectors. For further objects see [3, 4]. Arakawa and Kaneko [2] proved analytically while Bényi and Hajnal [3] combinatorially that

∑_{j=0}^{n}(−1)^{j}B_{n−j}^{(−j)} = 0.  (2)

Arakawa and Kaneko introduced a C-version of poly-Bernoulli numbers in [1] as

\frac{Li_{k}(1 − e^{−t})}{e^{t} − 1} = ∑_{n=0}^{∞} C_{n}^{(k)} \frac{t^{n}}{n!}.  (3)

In particular, {C_{n}^{(1)}}_{n∈ℕ} are the ordinary Bernoulli numbers, B_{n}, defined by

\frac{t}{e^{t} − 1} = ∑_{n=0}^{∞} B_{n} \frac{t^{n}}{n!}.

For negative k, the numbers C_{n}^{(k)} are again positive integers. They are the array \underline{A136126} in [12]. Table 1 below shows the first few values. Bényi and Hajnal [4] introduced this integer array as the number of lonesum matrices without any all-zero columns.

Kaneko, Sakurai, and Tsumura [10] proved the C-version of Identity (2) using analytical methods.

∑_{j=0}^{n}(−1)^{j}C_{n−j}^{(−j−1)} = −G_{n+2} (n ≥ 0).  (4)

In this note we present a combinatorial proof of Identity (4).

Recently, Matsusaka [11] showed that both (2) and (4) are special cases of a more general polynomial identity between symmetrized poly-Bernoulli numbers and Gandhi-polynomials.

2 Definitions

In this section we provide the necessary definitions and notation. We establish a connection between barred Callan sequences and Dumont permutations of the first kind defined in [8] which proves the identity.

Bényi and Nagy [6] defined Callan sequences that are essentially the same as the permutation class that Callan introduced in the entry \underline{A099594} of the OEIS [12]. Based on this notion, Bényi and Matsusaka [5] defined barred Callan sequences. We now recall the definition.

Let k, n ≥ 0 and consider the sets K = {1, …, k} ∪ {∗} (referred to as blue elements), and N = {1, …, n} ∪ {∗} (referred to as red elements).

Definition 1. A Callan sequence of size k × n is a sequence

(B_{1}, R_{1})(B_{2}, R_{2}) ⋯ (B_{m}, R_{m})(B^{∗}, R^{∗}),

for some m with 0 ≤ m ≤ n, such that

• {B_{1}, …, B_{m}, B^{∗}} form a set partition of K into m + 1 non-empty blocks,

• {R_{1}, …, R_{m}, R^{∗}} form a set partition of N into m + 1 non-empty blocks,

• ∗ ∈ B^{∗}, and ∗ ∈ R^{∗}.

Note that a Callan sequence can be encoded in an obvious way by the following data:

• an integer m with 0 ≤ m ≤ min(k, n);

• an ordered partition (B_{1}, …, B_{m}) of some subset K′ ⊂ {1, …, k}; and

• an ordered partition (R_{1}, …, R_{m}) of some subset N′ ⊂ {1, …, n}.

This is done by letting K′ = K \ B^{∗} and N′ = N \ R^{∗}.

To deal with these objects, it is be convenient to use the following terminology

• B^{∗} and R^{∗} are called extra blocks, while B_{i} and R_{i} are called ordinary blocks,

• each pair (B_{i}, R_{i}) or (B^{∗}, R^{∗}) is a Callan pair; moreover, the former are called ordinary pairs and the latter is called the extra pair.

A Callan sequence is thus a linear arrangement of Callan pairs with the extra pair at the end.

Example 2. The Callan sequences with k = 2 and n = 2 are listed below.

(12∗, 12∗),  (12, 12)(∗, ∗),  (1, 12)(2∗, ∗),  (2, 12)(1∗, ∗),  (12, 1)(∗, 2∗),
(12, 2)(∗, 1∗),  (1, 1)(2∗, 2∗),  (2, 1)(1∗, 2∗),  (1, 2)(2∗, 1∗),  (2, 2)(1∗, 1∗),
(1, 1)(2, 2)(∗, ∗), (1, 2)(2, 1)(∗, ∗), (2, 1)(1, 2)(∗, ∗), (2, 2)(1, 1)(∗, ∗).

Definition 3. A barred Callan sequence of size k × n is a sequence obtained by inserting a bar (denoted |) into a Callan sequence of size k × n with the restriction that the bar cannot be at the end of the sequence. We denote by C_{n}^{k} the set of barred Callan sequences with k blue elements and n red elements.

Example 4. We list here the 7 barred Callan sequences for k = 2 and n = 1.

|(12∗, 1∗); |(12, 1)(∗, ∗); |(2, 1)(1∗, ∗); |(1, 1)(2∗, ∗);
(1, 1)|(2∗, ∗); (2, 1)|(1∗, ∗); (12, 1)|(∗, ∗).

Bényi and Matsusaka [5] showed that the number of barred Callan sequences of size k ×n is the C-poly-Bernoulli number C_{n}^{(−k−1)}. To avoid negative indices in what follows, we use the notation C_{n}^{k} instead of C_{n}^{(−k−1)}. In particular, we have C_{n}^{k} = |C_{n}^{k}|.

Table 1 gives the first few values of the numbers C_{n}^{k}. Note that the symmetry C_{n}^{k} = C_{k}^{n} is clear from the combinatorial interpretation in terms of barred Callan sequences, as one can exchange red and blue blocks to get a n × k Callan sequence from a k × n Callan sequence.

0 1 2  3  4  5
0 1 1 1  1  1  1
1 1 3 7  15  31  63
2 1 7 31 115  391  1267
3 1 15 115 675 3451 16275
4 1 31 391 3451 25231 164731
5 1 63 1267 16275 164731 1441923

Table 1: C-poly-Bernoulli numbers C_{n}^{k}.

Remark 5. We note here that Callan sequences are equivalent to the special class of partial permutations where elements greater than n are excedances and the elements smaller than or equal to n are deficiencies. The number C_{n}^{k} also counts alternative tableaux of rectangular shape k × n and other related tableaux of rectangular shapes that are in bijection with alternative tableaux such as permutation tableaux or tree-like tableaux. See [3, 4] for details.

The other number sequence that is involved in the identity we want to prove is the sequence of Genocchi numbers. Genocchi numbers can be defined in different ways, here we focus on the combinatorial point of view. There are several combinatorial objects that are enumerated by the Genocchi numbers. The first known interpretation was Dumont permutations of the first kind.

Definition 6 ([8]). A Dumont permutation of the first kind is a permutation π ∈ S_{2n} such that each even entry begins a descent and each odd entry begins an ascent or ends the string, i.e., for every i = 1, 2, …, 2n

π(i) even ⟹ i < 2n and π(i) > π(i + 1),
π(i) odd ⟹ i < 2n and π(i) < π(i + 1), or i = 2n.

Let D_{2n} denote the set of Dumont permutations on 2n elements. Example 7. For 2n = 4 we have D_{4} = {2143, 3421, 4213}. For 2n = 6 we have

D_{6} = {642135, 634215, 621435421365, 342165, 214365, 564213, 563421, 562143,

216435, 435621, 215643, 436215, 364215, 421563, 356421, 421635.}

In general, we have Theorem 8. Theorem 8 (Dumont [8]). The cardinality of D_{2n} is (−1)^{n+1}G_{2n+2}.

3 Main result

Identity (4) can be reformulated as in Theorem 9 using our notation. Theorem 9 ([10]). The identity

∑_{j=0}^{n}(−1)^{j}C_{n−j}^{j} = −G_{n+2}  (5)

holds for n ≥ 0.

We introduce some combinatorial objects that play crucial role in our combinatorial proof of a generalization of the identity above. They can be seen as barred Callan sequences with extra structure. We could say that they interpolate in a certain sense between barred Callan sequences and Dumont permutations. Definition 10. Let C_{n}^{k}(m) denote the set of sequences defined by the following conditions. First, the elements in the sequence are

• m blue bars labelled with 1, …, m, and m + 1 red bars labelled with 0, …, m,

• Callan pairs of a k × n Callan sequence shifted up by m, i.e., with base sets K =

{m + 1, …, m + k} ∪ {∗} and N = {m + 1, …, m + n} ∪ {∗}. Second, these elements (labelled bars and Callan pairs) are ordered in a way such that

• a blue bar with label i is followed by a bar with label strictly smaller than i and

• a red bar with label i is followed either by a Callan pair or by a bar with label strictly greater than i.

The elements of C_{n}^{k}(m) are called m-barred Callan sequences and C_{n}^{k}(m) denotes the cardinality of the set C_{n}^{k}(m).

Remark 11. Bényi and Matsusaka [5] defined m-barred Callan sequences otherwise in, we call our special objects m-barred Callan sequence for the sake of convenience. Remark 12. The numbers C_{n}^{k}(1) are the so-called poly-Bernoulli D-relatives. Bényi and Hajnal [4] introduced poly-Bernoulli D-relatives as the number of lonesum matrices that do not contain any all-zero column and any all-zero row. See \underline{A272644} in [12].

Note that a bar is always followed by another element in the sequence, so the last element of the sequence is a Callan pair. More precisely, the last element is necessarily the extra pair of the underlying Callan sequence. For example, an element of C_{4}^{6}(3) is given as

|_{3}|_{2}|_{1}|_{2}(5, 45)|_{3}(79, 7)(4, 6)|_{1}|_{0}(68∗, ∗).

Note 13. Sometimes it is convenient to think that each Callan pair is associated with the (possibly empty) sequence of consecutive bars preceding it. In the previous example, we have the four “groups”

|_{3}|_{2}|_{1}|_{2}(5, 45) |_{3}(79, 7) (4, 6) |_{1}|_{0}(68∗, ∗).

Moreover, the last bar of each group is a red bar.

Let us first record some properties that are simple consequences of the definition.

Proposition 14. We have the following identities

C_{n}^{k}(m) = C_{k}^{n}(m),  (6)
C_{n}^{k}(0) = C_{n}^{k},  (7)
C_{0}^{0}(m) = (−1)^{m+1}G_{2m+2}.  (8)

Proof. The simple bijection that exchanges blue blocks with red blocks in each Callan pair establish a bijection between the sets C_{n}^{k}(m) and C_{k}^{n}(m) and implies the first identity.

The elements in C_{k}^{n}(0) contain a unique bar, |_{0}. Thus, we have a simple bijection between C_{k}^{n}(0) and C_{k}^{n} by changing |_{0} into |. Hence, we get the second identity.

The elements in C_{0}^{0}(m) contain a unique Callan pair at the last position, (∗, ∗). We also know that |_{m} preceds (∗, ∗) since there is no label strictly greater than m. Regarding this property, it is easy to see that there is a simple bijection between C_{0}^{0}(m) and D_{2m}. Remove |_{m}(∗, ∗) and transform |_{i} into 2i and |_{i} into 2i + 1.

Our main result is that the numbers C_{n}^{k}(m) also have an alternating sum equal to Genocchi numbers, as Theorem 15 states.

Theorem 15. The identity

∑_{j=0}^{n}(−1)^{j}C_{n−j}^{j}(m) = (−1)^{m+1}G_{n+2m+2}  (9)

holds for n, m ≥ 0.

Note that when n is odd both sides of (9) are 0. The sum has an even number of terms and they can be paired using the symmetry C_{n}^{k}(m) = C_{k}^{n}(m). So only the case where n is even is of interest. Note also that the case m = 0 in Theorem 15 is precisely Theorem 9.

The core of our bijective proof of Theorem 15 is the following identity.

Proposition 16. The identity

∑_{j=0}^{n}(−1)^{j}C_{n−j}^{j}(m) = − ∑_{j=0}^{n−2}(−1)^{j}C_{n−2−j}^{j}(m + 1)  (10)

holds for n ≥ 2 and m ≥ 0.

The combinatorial proof of Proposition 16 will be done in the next two sections. We show now that Theorem 15 and Theorem 9 are consequences of Proposition 16.

Proof of Theorem 15. As noted above, we can assume that n is even, n = 2n′ with n′ ∈ ℕ. We can successively iterate the identity in Proposition 16 with (n, m), then (n − 2, m + 1), etc. Each iteration gives a sum with one less term. Finally, we get the identity

∑_{j=0}^{n}(−1)^{j}C_{n−j}^{j}(m) = (−1)^{n′}C_{0}^{0}(m + n′).

The third equation in Proposition 14 implies that this is equal to (−1)^{n′+n′+m+1}G_{2m+2n′+2} which simplifies to (−1)^{m+1}G_{n+2m+2}.

4 The bijection ϕ

We define in this section a one-to-one correspondence between two particular subsets of mbarred Callan sequences. The bijection is a slight modification of the map introduced in [3] in order to prove (2).

Definition 17. Let C_{n}^{k}(m, ∗) denote the subset of C_{n}^{k}(m) containing elements α such that the extra red block is empty (by convention, this means it contains only ∗). Let C_{n}^{k}(m, R∗) = C_{n}^{k}(m)\C_{n}^{k}(m, ∗) denote the complementary subset.

Following the previous convention, let C_{n}^{k}(m, ∗) (respectively, C_{n}^{k}(m, R∗)) denote the cardinality of C_{n}^{k}(m, ∗) (respectively, C_{n}^{k}(m, R∗)).

Suppose that n ≥ 1 and k ≥ 0 are fixed throughout this section. We define the map

ϕ : C_{n}^{k}(m, R∗) → C_{n−1}^{k+1}(m, ∗)

as follows. Let α be an m-barred Callan sequence with a non-empty extra red block, α ∈ C_{n}^{k}(m, R∗). The general idea is to remove the maximal red element m + n and add a new blue element m′ = m + k + 1. We distinguish four cases according to the location of the maximal red element m + n.

A1) m + n is in the extra block as a singleton, i.e., R^{∗} = {m + n, ∗}. A2) m + n is in the extra block with other red elements, i.e., R^{∗} \ {m + n} = R′ ≠ {∗}. B1) m + n is in an ordinary block as a singleton, i.e., there is an ordinary pair (B_{i}, R_{i}) with

R_{i} = {m + n}. B2) m + n is in an ordinary block with other red elements, i.e., there is an ordinary pair

(B_{i}, R_{i}) with m + n ∈ R_{i} and R_{i} \ {m + n} = R′ ≠ ∅. Accordingly, ϕ(α) is defined as the result of the following procedure. A1) Delete m + n and add the new element m′ to the first Callan pair. A2) Replace the extra red block R^{∗} with {∗}, and place ({m′}, R′) in front of the Callan

sequence as the first element. B1) The successive steps are as follows:

– replace the extra red block R^{∗} with {∗},

– replace R_{i} = {m + n} with R^{∗}\{∗},

– move the new pair (B_{i}, R^{∗}\{∗}) in front of the Callan sequence together with the group of bars to its left (as in Note 13),

– add m′ to the (i + 1)st blue block (this means either B_{i+1} or the extra blue block

B^{∗} if B_{i} was in the last ordinary pair).

B2) The successive steps are as follows:

– replace the extra red block R^{∗} with {∗},

– replace (B_{i}, R_{i}) with two pairs (B_{i}, R^{∗}\{∗}) and ({m′}, R′),

– move the new pair (B_{i}, R^{∗}\{∗}) in front of the sequence together with the group

of consecutive bars preceding it (as in Note 13).

Example 18. Suppose that m, n, k are such that we remove 9 and add 8. The four cases can be illustrated as given in the list below.

A1) (5, 35)|_{1}(47, 247)|_{1}|_{0}(23, 68)(6∗, 9∗) → (58, 35)|_{1}(47, 247)|_{1}|_{0}(23, 68)(6∗, ∗)
A2) (5, 35)|_{1}(47, 2)|_{1}|_{0}(23, 68)(6∗, 479∗) → (8, 47)(5, 3, 5)|_{1}(47, 2)|_{1}|_{0}(23, 68)(6∗, ∗)
B1) (5, 358)|_{1}(47, 24)|_{1}|_{0}(23, 9)(6∗, 67∗) → |_{1}|_{0}(23, 67)(5, 358)|_{1}(47, 24)(68∗, ∗)
B2) (5, 38)|_{1}(47, 4)|_{1}|_{0}(23, 259)(6∗, 67∗) → |_{1}|_{0}(23, 67)(5, 38)|_{1}(47, 4)(8, 25)(6∗, ∗)

Definition 19. For n ≥ 0 and k ≥ 1, let C_{n}^{k}(m, ∗, |m′) denote the subset of C_{n}^{k}(m, ∗) containing elements α such that the maximal blue element m′ = m + k is in an ordinary Callan pair as a singleton and there is at least one bar preceding this pair. Following the previous convention, let C_{n}^{k}(m, ∗, |m′) denote the cardinality of C_{n}^{k}(m, ∗, |m′).

Note that when k = 0 and n > 0, we have C_{n}^{0}(m, ∗) = ∅. Indeed, the only 0 × n Callan sequence is (∗, 123 ⋯ n∗), which has a nonempty extra red block. Accordingly, we also take the convention C_{n}^{0}(m, ∗, |m′) = ∅.

Note also that C_{0}^{k}(m, ∗, |m′) = ∅. Indeed, the only k × 0-Callan pair is (123 ⋯ k∗, ∗), so it is not possible to have m′ as a singleton in an ordinary pair.

Lemma 20. The map ϕ defined as above is a bijection between the sets C_{n}^{k}(m, R∗) and C_{n−1}^{k+1}(m, ∗) \ C_{n−1}^{k+1}(m, ∗, |m′).

Proof. Let us first check that ϕ(α) ∈ C_{n−1}^{k+1}(m, ∗). Note that each group of consecutive bars is unchanged (though these groups are possibly permuted in case B1 and B2), so we only need to check that the pairs form a valid Callan sequence. This is straightforward.

Then, let us check that ϕ(α) ∉ C_{n−1}^{k+1}(m, ∗, |m′). In cases A1 and B1, the blue element m′ is added to a blue block (which is nonempty by definition) so m′ is not a single element in its block. In cases A2 and B2, m′ is in a singleton block, so we need to check that there is no bar preceding the pair containing m′. In case A2, this is because this pair is at the beginning of the sequence. In case B2, the new pair ({m′}, R′) is created with another pair to its left, and since the pair to its left is moved together with the associated group of bars, there is again another pair to the left of ({m′}, R′) in ϕ(α).

In the previous paragraph, we observed the following properties in ϕ(α):

• m′ is in the first pair iff the sequence was obtained from the cases A1 or A2.

• m′ is alone in its block iff the sequence was obtained from the cases A2 or B2.

So, the four cases can be distinguished based on which of the above properties they satisfy. In each case, based on the position of m′ it is straightforward to describe the inverse procedure, so ϕ is injective.

The bijection ϕ can be used to obtain pairwise cancellations in the alternating sums.

Lemma 21. The identity

∑_{j=0}^{n}(−1)^{j}C_{n−j}^{j}(m) = ∑_{j=0}^{n}(−1)^{j}C_{n−j}^{j}(m, ∗, |m′).

holds for n, m ≥ 0.

Proof. The set C_{n−j}^{j}(m) can be partitioned as

C_{n−j}^{j}(m) = C_{n−j}^{j}(m, R∗) ⨄ (C_{n−j}^{j}(m, ∗) \ C_{n−j}^{j}(m, ∗, |m′)) ⨄ C_{n−j}^{j}(m, ∗, |m′),  (11)

so that

∑_{j=0}^{n}(−1)^{j}C_{n−j}^{j}(m) = ∑_{j=0}^{n}(−1)^{j}|C_{n−j}^{j}(m, R∗)| + ∑_{j=0}^{n}(−1)^{j}|(C_{n−j}^{j}(m, ∗) \ C_{n−j}^{j}(m, ∗, |m′))|

+ ∑_{j=0}^{n}(−1)^{j}C_{n−j}^{j}(m, ∗, |m′).

The bijection ϕ readily shows that the first and second sum cancel each other out, upon checking the boundary terms.

The first boundary term is j = n in the first sum. The set C_{0}^{n}(m, R∗) is empty (as there are no red element besides ∗, the extra red block cannot be nonempty), so the corresponding term is 0. The second boundary term is j = 0 in the second sum. As noted after Definition 19, C_{n}^{0}(m, ∗) is empty, C_{n}^{0}(m, ∗) \ C_{n}^{0}(m, ∗, |m′) is empty as well, and the corresponding term is 0.

Lemma 21 implies Proposition 16 when we can show the following identity.

∑_{j=0}^{n}(−1)^{j}C_{n−j}^{j}(m, ∗, |m′) = − ∑_{j=0}^{n−2}(−1)^{j}C_{n−2−j}^{j}(m + 1).  (12)

We prove Identity (12) in the next section.

5 The bijection ψ

It is convenient to use a slight modified set instead of C_{n}^{k}(m, ∗, |m′) in the combinatorial proof of Identity (12).

Definition 22. We define C_{n}^{k}(m, ∗, |m + 1) like C_{n}^{k}(m, ∗, |m′) in Definition 19, but with m+1 instead of m′ = m + k. As before, denote C_{n}^{k}(m, ∗, |m + 1) = |C_{n}^{k}(m, ∗, |m + 1)|.

Explicitely, C_{n}^{k}(m, ∗, |m′) is the subset of C_{n}^{k}(m, ∗) containing elements α such that the minimal blue element, m + 1, is in an ordinary Callan pair as a singleton, and there is at least one bar preceding this pair.

There is a bijection from C_{n}^{k}(m, ∗, |m′) to C_{n}^{k}(m, ∗, |m + 1) via a relabelling of blue elements that exchanges m + k and m + 1. Using this, (12) is clearly equivalent to:

∑_{j=0}^{n}(−1)^{j}C_{n−j}^{j}(m, ∗, |m + 1) = − ∑_{j=0}^{n−2}(−1)^{j}C_{n−2−j}^{j}(m + 1).  (13)

In order to show (13), we give a bijection ψ between the sets C_{n}^{k}(m, ∗, |m + 1) and C_{n−1}^{k−1}(m + 1) for n, k ≥ 1. Note that C_{0}^{k}(m, ∗, |m + 1) = C_{n}^{0}(m, ∗, |m + 1) = ∅, following the remarks after Definition 19.

We do this in two steps, i.e., as the composition of two operations: ψ = ψ_{r} ∘ ψ_{b}. The first map ψ_{b} takes the blue element m + 1 out of a Callan pair and changes it into a labeled blue bar |_{m+1}. The second map ψ_{r} does the same with m + 1 and |_{m+1}.

Definition 23. For α ∈ C_{n}^{k}(m, ∗, |m + 1), note that α contains an ordinary pair (m + 1, R). Let w_{1} (respectively, w_{2}) denote the maximal subsequence of consecutive bars that are directly to the left (respectively, to the right) of (m + 1, R). Note that w_{1} is nonempty by definition, but w_{2} is possibly empty. We define ψ_{b}(α) as follows.

1. Replace w_{1} (m + 1, R) w_{2} with w_{2} |_{m+1} w_{1} in the sequence.

2. Replace the extra red block {∗} with R ∪ {∗}.

Example 24.

(4, 9)(58, 25)|_{1}(2, 347)|_{1}|_{0}(37, 68)(6∗, ∗) →_{ψ_{b}} (4, 9)(58, 35)|_{1}|_{0}|_{2}|_{1}(37, 68)(6∗, 347∗).

Note that an element in the image of ψ_{b} has a nonempty extra red block.

Definition 25. Let α ∈ im(ψ_{b}). We define ψ_{r}(α) by the following procedure distinguishing two cases.

• If m + 1 ∈ R^{∗}, replace the extra pair (B^{∗}, R^{∗}) with two consecutive elements |_{m+1} and (B^{∗}, R^{∗} \ {m + 1}).

• Otherwise, m + 1 is in an ordinary pair (B_{i}, R_{i}). Replace the pair (B_{i}, R_{i}) with two consecutive elements |_{m+1} and (B_{i}, R^{∗} \ {∗}), then replace the extra pair (B^{∗}, R^{∗}) with (B^{∗}, R′ ∪ {∗}) where R′ = R_{i} \ {m + 1}.

Example 26.

(583, 46)(29, 35)|_{1}|_{0}(47, 2)(3∗, 17∗) →_{ψ_{r}} (583, 46)(29, 35)|_{1}|_{0}(47, 2)|_{1}(3∗, 7∗),
(583, 1)(29, 35)|_{1}|_{0}(47, 46)(3∗, 27∗) →_{ψ_{r}} |_{1}(583, 27)(29, 35)|_{1}|_{0}(47, 46)(3∗, ∗).

Lemma 27. For n, k ≥ 1 and m ≥ 0, the map ψ = ψ_{r} ∘ ψ_{b} is a bijection between the sets C_{n}^{k}(m, ∗, |m + 1) and C_{n−1}^{k−1}(m + 1).

Proof. First, we can check that ψ(α) with labelled bars removed is a (k − 1) × (n − 1) Callan sequence where labels are shifted up by m + 1. As noted above, ψ_{b}(α) has a nonempty extra red block. In the second case of the definition of ψ_{r}, we thus see that R^{∗} \ {∗} ≠ ∅, so that (B_{i}, R^{∗} \ {∗}) is a valid Callan pair.

Secondly, we check that the labelled bars in ψ(α) sastisfy the conditions so that ψ(α) ∈ C_{n−1}^{k−1}(m + 1). We begin with labelled bars in ψ_{b}(α). We have to check two locations.

• The element after |_{m+1} should be a labelled bar with label strictly smaller than m + 1. This element is the first one of w_{1}, as w_{1} is nonempty. By definition, it satisfies the required properties.

• If w_{2} is empty, either |_{m+1} begins the sequence or it is preceded by a Callan pair. Otherwise, the last element of w_{2} is a bar |_{i} with i ≤ m, as it is followed by a Callan pair in α. In both cases, this is a valid configuration.

Then, ψ(α) is obtained by adding |_{m+1} to the left of a Callan pair. Thus, either it is a new group of bars in itself, or it is added at the end of an existing group of bars. In the second case, as the last element of this group is a red bar with label i at most m, the configuration |_{i}|_{m+1} is valid.

We thus have ψ(α) ∈ C_{n−1}^{k−1}(m + 1). It remains to describe the inverse bijection ψ^{−1} and to check that it is indeed the left and right inverse of ψ. In the definition of ψ_{r}, the cases can be distinguished: the first one (respectively, second one) results in |_{m+1} being to the left of the extra pair (respectively, of an ordinary pair). Using that, the inverse bijection is straightforward to describe explicitly.

Remark 28. Our bijections provided a combinatorial proof for the fact that the alternating diagonal sum of C-poly-Bernoulli numbers is given by the Genocchi number (Theorem 9). We used a special technique. Instead of defining a direct involution on the set that is enumerated by the C-poly-Bernoulli numbers, we introduced interpolating sets, the m-barred Callan sequences. Starting with the set of Callan sequences, enumerated by the C-poly-Bernoulli number, we applied the involution ϕ that reduced the number of elements to obtain a new set, on which we again applied the involution, until we reached the set that is known to be counted by the Genocchi number. This tricky solution shows the difficulty of the problem somewhat. It would be also interesting to find a direct bijection on any of the corresponding combinatorial objects that proves Theorem 9 without any iteration steps needed. Moreover, it is still an open problem to find a combinatorial proof for the more general identity related with symmetrized poly-Bernoulli numbers and Gandhi polynomials (see [11]).

6 Acknowledgments

The authors would like to thank the anonymous referees for helpful comments and suggestions.

References

[1] T. Arakawa and M. Kaneko, Multiple Zeta values, poly-Bernoulli numbers, and related zeta functions, Nagoya Math. J. 153 (1999), 189–209.

[2] T. Arakawa and M. Kaneko, On poly-Bernoulli numbers, Comment. Math. Univ. St. Paul. 48 (1999), 159–167.

[3] B. Bényi and P. Hajnal, Combinatorics of poly-Bernoulli numbers, Studia Sci. Math. Hungarica 52 (2015), 537–558.

[4] B. Bényi and P. Hajnal, Combinatorial properties of poly-Bernoulli relatives, Integers 17 (2017), Paper A31.

[5] B. Bényi and T. Matsusaka, On the combinatorics of symmetrized poly-Bernoulli numbers, Electron. J. Combin. 28 (2021), P1.47.

[6] B. Bényi and G. Nagy, Bijective enumeration of Γ-free 0-1 matrices, Adv. in Appl. Math. 96 (2018), 195–215.

[7] C. R. Brewbaker, Lonesum (0, 1) matrices and the poly-Bernoulli numbers of negative index, Master’s thesis, Iowa State Univ., 2005. Available at https://lib.dr.iastate.

edu/rtd/18914/.

[8] D. Dumont, Interprétations combinatoires des nombres de Genocchi, Duke Math. J. 41 (1974), 305–318.

[9] M. Kaneko, Poly-Bernoulli numbers, J. Théor. Nombres Bordeaux 9 (1997), 221–228.

[10] M. Kaneko, F. Sakurai, and H. Tsumura, On a duality formula for certain sums of values of poly-Bernoulli polynomials and its application, J. Théorie Nombres Bordeaux 30 (2018), 203–218.

[11] T. Matsusaka, Symmetrized poly-Bernoulli numbers and combinatorics, J. Integer Sequences 23 (2020), Article 20.9.2.

[12] N. J. A. Sloane et al., The on-line encyclopedia of integer sequences, 2021. Available at

https://oeis.org.

[13] R. P. Stanley, Enumerative Combinatorics, Volume 2, Cambridge University Press, 1999.

2010 Mathematics Subject Classification: Primary 05A19; Secondary: 11B68. Keywords: Genocchi number, poly-Bernoulli number, combinatorial identity, bijection, Callan sequence.

(Concerned with sequences \underline{A036968}, \underline{A099594}, \underline{A136126}, and \underline{A272644}.)

Received January 5 2021; revised versions received May 26 2021; July 17 2021. Published in Journal of Integer Sequences, July 18 2021.

Return to Journal of Integer Sequences home page.