A Generalized Hockey Stick Theorem

Molly Lynch

Department of Mathematics, Statistics, and Computer Science Hollins University 7916 Williamson Rd Roanoke, VA 24020

USA

lynchme2@hollins.edu

Michael Weselcouch

School of Health, Science, and Sustainability 221 College Ln Roanoke College Salem, VA 24153

USA

weselcouch@roanoke.edu

Abstract

We present a combinatorial proof, based on a sign-reversing involution, of a new identity that extends the classical “hockey stick” identity for binomial coefficients.

1 Introduction

In this article we give a combinatorial proof using a sign-reversing involution of the following identity:

∑_{i=0}^{k} \binom{(r + 1)i + n}{i} = ∑_{α∈C(k,r)} sgn(α)(∏_{j=1}^{ℓ(α)} \binom{r}{α_{j} − 1})\binom{(r + 1)k + n + 1 − |α| + ℓ(α)}{k − |α|}. (1)

Before introducing the notation used in the right hand side of the identity, we should note that when r = 0, Eq. (1) gives the hockey stick identity (also known as Chu’s theorem)

[5] and when r = 1, Eq. (1) gives the big hockey stick and pucks identity [2, 4]. For fixed values of r and n, Eq. (1) gives many sequences from the On-Line Encyclopedia of Integer Sequences (OEIS) [6] as detailed in Table 1.

r n OEIS sequence
0 0  \underline{A000027}
0 1  \underline{A000217}
0 2  \underline{A000292}
0 3  \underline{A000332}
0 4  \underline{A000389}
0 5  \underline{A000579}
1 0  \underline{A006134}
1 1  \underline{A079309}
1 2  \underline{A057552}
1 3  \underline{A371965}
1 4  \underline{A371964}
1 5  \underline{A371963}
2 0  \underline{A188675}
2 1  \underline{A263134}
2 2  \underline{A087413}
3 0  \underline{A225612}
4 0  \underline{A225615}

Table 1: OEIS sequences for fixed values of r and n.

The hockey stick identity is a well-known result in enumerative combinatorics. It states that for nonnegative integers n and k,

∑_{i=0}^{k} \binom{i + n}{i} = \binom{k + 1 + n}{k}.  (2)

The reason behind naming this identity the “hockey stick identity” is because the terms in the identity appear to form a hockey stick when viewed as being a part of Pascal’s triangle \underline{A007318}. Figure 1 shows the terms in the hockey stick identity when n = 2 and k = 3. The terms that appear on the left-hand side of Eq. (2) are circled and the term on the right-hand side is enclosed in a square. In this case, we see that \binom{2}{0} + \binom{3}{1} + \binom{4}{2} + \binom{5}{3} = 20 = \binom{6}{3}.

\begin{matrix}( & {0 \atop 0} & ) \\ ( & {1 \atop 0} & ) \\ ( & {1 \atop 1} & ) \\ ( & {2 \atop 0} & ) \\ ( & {2 \atop 1} & ) \\ ( & {2 \atop 2} & ) \\ ( & {3 \atop 0} & ) \\ ( & {3 \atop 1} & ) \\ ( & {3 \atop 2} & ) \\ ( & {3 \atop 3} & ) \\ ( & {4 \atop 0} & ) \\ ( & {4 \atop 1} & ) \\ ( & {4 \atop 2} & ) \\ ( & {4 \atop 3} & ) \\ ( & {4 \atop 4} & ) \\ ( & {5 \atop 0} & ) \\ ( & {5 \atop 1} & ) \\ ( & {5 \atop 2} & ) \\ ( & {5 \atop 3} & ) \\ ( & {5 \atop 4} & ) \\ ( & {5 \atop 5} & ) \\ ( & {6 \atop 0} & ) \\ ( & {6 \atop 1} & ) \\ ( & {6 \atop 2} & ) \\ ( & {6 \atop 3} & ) \\ ( & {6 \atop 4} & ) \\ ( & {6 \atop 5} & ) \\ ( & {6 \atop 6} & ) \end{matrix}

Figure 1: The hockey stick identity with n = 2 and k = 3.

Similarly, the big hockey stick and pucks identity states that for nonnegative integers n and k,

∑_{i=0}^{k} \binom{2i + n}{i} = ∑_{i=0}^{⌊ \frac{k}{2} ⌋}(−1)^{i}\binom{2k + 1 + n − i}{k − 2i}.  (3)

Figure 2 shows the terms in the big hockey stick and pucks identity when n = 1 and k = 4. As with Figure 1, in Figure 2, the terms that appear on the left-hand side of Eq. (3) are circled and the terms that appear on the right-hand side are enclosed in a square. In this case, we see that \binom{1}{0} + \binom{3}{1} + \binom{5}{2} + \binom{7}{3} + \binom{9}{4} = 175 = \binom{10}{4} − \binom{9}{2} + \binom{8}{0}.

\begin{matrix}( & {0 \atop 0} & ) \\ ( & {1 \atop 0} & ) \\ ( & {1 \atop 1} & ) \\ ( & {2 \atop 0} & ) \\ ( & {2 \atop 1} & ) \\ ( & {2 \atop 2} & ) \\ ( & {3 \atop 0} & ) \\ ( & {3 \atop 1} & ) \\ ( & {3 \atop 2} & ) \\ ( & {3 \atop 3} & ) \\ ( & {4 \atop 0} & ) \\ ( & {4 \atop 1} & ) \\ ( & {4 \atop 2} & ) \\ ( & {4 \atop 3} & ) \\ ( & {4 \atop 4} & ) \\ ( & {5 \atop 0} & ) \\ ( & {5 \atop 1} & ) \\ ( & {5 \atop 2} & ) \\ ( & {5 \atop 3} & ) \\ ( & {5 \atop 4} & ) \\ ( & {5 \atop 5} & ) \\ ( & {6 \atop 0} & ) \\ ( & {6 \atop 1} & ) \\ ( & {6 \atop 2} & ) \\ ( & {6 \atop 3} & ) \\ ( & {6 \atop 4} & ) \\ ( & {6 \atop 5} & ) \\ ( & {6 \atop 6} & ) \\ ( & {7 \atop 0} & ) \\ ( & {7 \atop 1} & ) \\ ( & {7 \atop 2} & ) \\ ( & {7 \atop 3} & ) \\ ( & {7 \atop 4} & ) \\ ( & {7 \atop 5} & ) \\ ( & {7 \atop 6} & ) \\ ( & {7 \atop 7} & ) \\ ( & {8 \atop 0} & ) \\ ( & {8 \atop 1} & ) \\ ( & {8 \atop 2} & ) \\ ( & {8 \atop 3} & ) \\ ( & {8 \atop 4} & ) \\ ( & {8 \atop 5} & ) \\ ( & {8 \atop 6} & ) \\ ( & {8 \atop 7} & ) \\ ( & {8 \atop 8} & ) \\ ( & {9 \atop 0} & ) \\ ( & {9 \atop 1} & ) \\ ( & {9 \atop 2} & ) \\ ( & {9 \atop 3} & ) \\ ( & {9 \atop 4} & ) \\ ( & {9 \atop 5} & ) \\ ( & {9 \atop 6} & ) \\ ( & {9 \atop 7} & ) \\ ( & {9 \atop 8} & ) \\ ( & {9 \atop 9} & ) \\ ( & {10 \atop 0} & ) \\ ( & {10 \atop 1} & ) \\ ( & {10 \atop 2} & ) \\ ( & {10 \atop 3} & ) \\ ( & {10 \atop 4} & ) \\ ( & {10 \atop 5} & ) \\ ( & {10 \atop 6} & ) \\ ( & {10 \atop 7} & ) \\ ( & {10 \atop 8} & ) \\ ( & {10 \atop 9} & ) \\ ( & {10 \atop 10} & ) \end{matrix}

Figure 2: The big hockey stick and pucks identity with n = 1 and k = 4.

We note that Jones [3] previously did work generalizing the hockey stick identity, and Bondarenko [1] did work more generally regarding Pascal’s triangle.

2 Preliminaries

We begin with some preliminaries about sign-reversing involutions, compositions, Young diagrams, and lattice paths. For more information, see Stanley [7].

2.1 Sign-reversing involutions

Our main tool in this paper is that of a sign-reversing involution. Let X be a set of objects and to each object x ∈ X, assign a weight, wt(x) = ±1. The usual objective is to calculate the total weight of the objects in X, namely ∑_{x∈X} wt(x). A sign-reversing involution on X is an involution τ : X → X such that if x ≠ τ(x), then wt(τ(x)) = − wt(x). In other words, τ pairs up elements of X with opposite signs. We denote the set of fixed points of τ, i.e., x ∈ X such that τ(x) = x as Fix(τ). Therefore,

∑_{x∈X} wt(x) = ∑_{x∈Fix(τ)} wt(x).

Often it is the case that wt(x) = 1 for all x ∈ Fix(τ), so in that case, summing the weights of all elements in X gives the total number of fixed points.

2.2 Compositions

A composition α = (α_{1}, α_{2}, …, α_{j}) of an integer k is a finite sequence of positive integers summing to k. We write α ⊨ k if α is a composition of k. Additionally, we write |α| for the sum of the parts of α and ℓ(α) for the number of parts of α. There is a unique composition of 0 denoted by ∅ called the empty composition. The empty composition satisfies ℓ(∅) = |∅| = 0. We define the sign of α to be sgn(α) = (−1)^{|α|−ℓ(α)}.

Given a composition α = (α_{1}, α_{2}, …, α_{j}), we define the compositions α^{→}, α^{↑}, and α^{↙} by:

• α^{→} = (α_{1} + 1, α_{2}, …, α_{j}),

• α^{↑} = (2, α_{1}, α_{2}, …, α_{j}),

• α^{↙} = \begin{cases}(α_{1} − 1, α_{2}, …, α_{j}) & if α_{1} > 2, \\ (α_{2}, …, α_{j}) & if α_{1} ≤ 2. \end{cases}

We note that if α_{1} ≥ 2, these operations on α each result in a composition with sign opposite of the sign of α.

Proposition 1. If α_{1} ≥ 2, then sgn(α^{→}) = sgn(α^{↑}) = sgn(α^{↙}) = − sgn(α).

Proof. We prove each claim one at a time.

• sgn(α^{→}) = − sgn(α): In this case, we have ℓ(α^{→}) = ℓ(α) but |α^{→}| = |α| + 1. As a result, |α^{→}| − ℓ(α^{→}) = |α| − ℓ(α) + 1. It follows that sgn(α^{→}) = − sgn(α).

• sgn(α^{↑}) = − sgn(α): Here we have ℓ(α^{↑}) = ℓ(α) + 1 and |α^{↑}| = |α| + 2. As a result, |α^{↑}| − ℓ(α^{↑}) = |α| − ℓ(α) + 1. This again implies that sgn(α^{↑}) = − sgn(α).

• sgn(α^{↙}) = − sgn(α) : If α_{1} > 2, then ℓ(α^{↙}) = ℓ(α) and |α^{↙}| = |α| − 1. From this, we have |α^{↙}| − ℓ(α) = |α| − ℓ(α) − 1 resulting in sgn(α^{↙}) = − sgn(α). Finally, if α_{1} = 2, then ℓ(α^{↙}) = ℓ(α) − 1 and |α^{↙}| = |α| − 2. As a result, sgn(α^{↙}) = − sgn(α).

Let c(k, r) denote the set of compositions α ⊨ k such that 2 ≤ α_{i} ≤ r + 1 for all

1 ≤ i ≤ ℓ(α) and let C(k, r) = ⋃_{j=0}^{k} c(j, r).

Example 2. If k = 5 and r = 3, then

C(5, 3) = {∅, (2), (3), (4), (2, 2), (2, 3), (3, 2)}.

2.3 Young diagrams

For a composition α, the Young diagram of shape α is a collection of boxes arranged in leftjustified rows such that row i has α_{i} boxes. In the case where α = ∅, the Young diagram of α has no boxes. The compositions α^{→}, α^{↑}, and α^{↙} defined in Section 2.2 can be described in terms of Young diagrams. The Young diagram for α^{→} can be obtained from the Young diagram for α by adding an additional box in the first row. The Young diagram for α^{↑} can be obtained from the Young diagram for α by creating a new first row with two boxes. Finally, α^{↙} is the Young diagram obtained from α by removing the first row in the case where α_{i} ≤ 2, and otherwise removing a box from the first row.

We define a labeled tableau of shape α to be a labeling of the boxes of the Young diagram of shape α such that the first entry in each row is empty and the remaining entries are nonnegative integers that are strictly increasing from left to right. We denote by Λ(α, r) the set of all labeled tableau of shape α whose labels are all less than r. If α = ∅, then Λ(α, r) contains only a single element, the empty labeling of the Young diagram of shape ∅. For i, j ≥ 1 and λ ∈ Λ(α, r), we let λ_{i} denote the set of entries of the ith row of λ, |λ_{i}| denote the number of boxes in the ith row, and we let λ_{i,j} denote the entry in the ith row and (j + 1)st column of λ. Finally, if λ ∈ Λ(α, r), then we define the shape of λ as sh(λ) = α and the sign of λ as sgn(λ) = sgn(α).

Example 3. The following is an element of Λ((4, 5, 3), 4):

0 2 3 0 1 2 3 1 3

In this case, λ_{1,1} = 0 since 0 is in the first row and second column of λ. We also have that sgn(λ) = −1.

Proposition 4. Let r be a nonnegative integer and α be a composition. Then if α = ∅, the size of the set Λ(α, r) is 1. If |α| ≥ 1, then

|Λ(α, r)| = ∏_{j=1}^{ℓ(α)} \binom{r}{α_{j} − 1}.

Proof. If α = ∅, then the only element of Λ(α, r) is the empty labeling of the Young diagram of shape ∅.

Now assume |α| ≥ 1. If α_{i} = 1 for all 1 ≤ i ≤ ℓ(α), then the result holds as the only element of Λ(α, r) is the empty labeling of the Young diagram of shape α and ∏_{j=1}^{ℓ(α)} \binom{r}{0} = 1.

If α_{i} > 1 for some i, then the constraints on the labels of the labeled tableaux in Λ(α, r) are that the first entry of each row must be empty, the remaining entries must be nonnegative integers listed in strictly increasing order from left to right, and the labels must be less than r. That means that for all 1 ≤ j ≤ ℓ(α), the labels used in row j must be an (α_{j} −1)-element subset of \{0, …, r − 1\}. There are \binom{r}{α_{j}−1} such subsets. Since the labels in each row are independent from the labels in the other rows, taking the product over the number of rows gives the desired result.

Given λ ∈ Λ(α, r) and a ∈ {0, …, r − 1}, we define λ ⊕ a to be the labeled tableau of shape α^{↑} satisfying (λ ⊕ a)_{1,1} = a and for i ≥ 1, (λ ⊕ a)_{i+1} = λ_{i}. If a ∉ λ_{1}, then we let λ + a to be the labeled tableau of shape α^{→} that satisfies (λ + a)_{1} = λ_{1} ∪ {a} and for i > 1, (λ + a)_{i} = λ_{i}. Finally we let λ^{↙} be the labeled tableau of shape α^{↙} where if |λ_{1}| > 2, then (λ^{↙})_{1} = λ_{1} − λ_{1,1} and for i > 1, (λ^{↙})_{i} = λ_{i}, but if |λ_{1}| ≤ 2, then for i ≥ 1, (λ^{↙})_{i} = λ_{i+1}. That is to say, λ^{↙} is created from λ by removing the smallest entry in the first row of λ, if α_{1} > 2 or it is created by removing the entire first row of λ otherwise.

Example 5. If λ is the labeled tableau shown in Example 3, then λ ⊕ 1, λ + 1, and λ^{↙} are the following labeled tableaux:

λ ⊕ 1 =  1 0 2 3 0 1 2 3 1 3  λ + 1 =  0 1 2 3 0 1 2 3 1 3  λ^{↙} =  2 3 0 1 2 3 1 3

2.4 Lattice sequences and lattice paths

Let m be a nonnegative integer. A lattice sequence L = (L_{0}, L_{1}, L_{2}, …, L_{m}, L_{m+1}) is a sequence of nonnegative integers satisfying 0 = L_{0} ≤ L_{1} ≤ ⋯ ≤ L_{m+1}. We say that m is the width of L and that L_{m+1} is the height of L. Note that if the width of L is m, then L has (m + 2) entries.

For 0 ≤ i ≤ j ≤ m + 1, let L_{[i,j]} denote the subsequence (L_{i}, L_{i+1}, …, L_{j}) and let L_{[i,...]} be the subsequence (L_{i}, L_{i+1}, …, L_{m+1}). If L and L′ are both sequences, let L; L′ denote the concatenation of the two sequences. Finally, for any sequence L = (L_{0}, L_{1}, …), let L + a denote the sequence (L_{0} + a, L_{1} + a, …).

A lattice sequence can be interpreted as a lattice path consisting of steps of the form (1, 0) or (0, 1) from (0, 0) to (m, L_{m+1}). For 1 ≤ i ≤ m, the value of L_{i} gives the height of the ith horizontal step of the lattice path.

Since lattice sequences can be interpreted as a lattice paths, the number of lattice sequences with width m and height n is \binom{m+n}{m}. We let L(m, n) denote the set of such lattice sequences.

Definition 6. Let L ∈ L(m, n). The ascent set of L, denoted asc(L), is given by

asc(L) = {i ∈ {0, …, m} | L_{i} < L_{i+1}}.

When viewing L as a lattice path, the ascent set of L gives the horizontal coordinates in which vertical steps appear.

Example 7. The following is the lattice path corresponding to the lattice sequence L = (0, 0, 0, 2, 3, 5) ∈ L(4, 5). The ascent set of L is asc(L) = {2, 3, 4}. The entries in the sequence (excluding the first and last) correspond to the heights of the horizontal steps.

We now introduce some notation that will be heavily used in the proof of Theorem 12. Let L ∈ L(m, n) and let η ≤ m be a nonnegative integer. Let ω_{η}(L), γ_{η}(L), and μ_{η}(L) be the following values:

• ω_{η}(L) = L_{η+1} − L_{η}.

• γ_{η}(L) = \begin{cases}max(asc(L_{[0,η]})), & if asc(L_{[0,η]}) ≠ ∅; \\ −1, & otherwise. \end{cases}

• μ_{η}(L) = η − 1 − γ_{η}(L).

When viewing L as a lattice path from (0, 0) to (m, n), ω_{η}(L) gives the number of vertical steps on the line x = η and if γ_{η}(L) ≥ 0, then γ_{η}(L) gives the horizontal location of the east-most vertical step west of the line x = η. If γ_{η}(L) = −1, then L_{[0,η]} = (0, …, 0). That is to say there are no vertical steps west of x = η. The value of μ_{η}(L) gives the horizontal distance between the vertical step used to determine γ_{η}(L) and line x = η − 1.

Example 8. Consider the lattice sequence L = (0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 4, 4, 4, 4) where η = 9. It follows that ω_{9}(L) = L_{10} − L_{9} = 4 − 2 = 2, γ_{9}(L) = 4 and μ_{9}(L) = 9 − 1 − 4 = 4. The dashed lines are the lines x = η and the location of the east-most vertical step west of x = η.

The following lemma is used in the proof Theorem 12.

Lemma 9. Let r, k, n, and i be fixed nonnegative integers, and let η = rk + n + 1. If A = {L ∈ L(η, k) | μ_{η}(L) ≥ r · ω_{η}(L) and ω_{η}(L) = k − i}, then

|A| = \binom{(r + 1)i + n}{i}.

Proof. We prove this results by showing that there is a bijection between the sets A and L(ri + n, i) as the size of L(ri + n, i) is \binom{(r+1)i+n}{i}.

Let B = (B_{1}, …, B_{r(k−i)+1}) be the sequence defined by B_{j} = i if j ≤ r(k − i) and B_{r(k−i)+1} = k. Let ψ be a function with domain L(ri + n, i) defined by ψ(L) = L; B. We now show that ψ(L) ∈ A.

Let L ∈ L(ri + n, i). Since L_{ri+n+1} = i for all L ∈ L(ri + n, i), it follows that L; B is weakly-increasing and hence is a lattice sequence with height k. The number of elements in the lattice sequence L; B is (ri + n + 2) + (r(k − i) + 1) = rk + n + 3. Since the width of a lattice sequence is the number of entries minus 2, the width of L; B is rk + n + 1 = η. Note that (L; B)_{η+1} − (L; B)_{η} = k − i and max(asc(L; B)) = max(asc(L)) ≤ ri + n. This means that μ_{η}(L; B) ≥ η − 1 − (ri + n) = r(k − i) = rω_{η}(L; B). Therefore we have that ψ(L) is an element of A.

Now let ϕ be the function with domain A defined by ϕ(L) = L_{[0,ri+n+1]}. We now show that ϕ(L) ∈ L(ri + n, i).

Let L ∈ A. This means that ω_{η}(L) = k − i and μ_{η}(L) ≥ r · (k − i). Since ω_{η}(L) = k − i, it follows that L_{η} = k − (k − i) = i and because μ_{η}(L) ≥ r · (k − i), it follows that L_{j} = i for all j ∈ {η−1−r·(k−i)+1, …, η}. In particular, L_{ri+n+1} = i. Therefore L_{[0,ri+n+1]} ∈ L(ri+n, i) as desired.

Since ψ and ϕ are inverses of each other (the sequence of terms removed by ϕ is the sequence B) we have that these sets are in bijection.

2.5 Labeled lattice sequences

We now turn our attention to the main combinatorial object of this article, the labeled lattice sequence.

Definition 10. A labeled lattice sequence of type (k, n, r) is a pair, (λ, L), where λ ∈ Λ(α, r) for some α ∈ C(k, r) and L ∈ L(rk + n + 1 + ℓ(α), k − |α|).

Notice that if (λ, L) is a labeled lattice sequence, then the labels of λ are independent of the constraints that L satisfies.

Proposition 11. Let k, n, and r be nonnegative integers. Then the number of labeled lattice sequences, (λ, L), of type (k, n, r) such that sh(λ) = α for a fixed α ∈ C(k, r) is

(∏_{j=1}^{ℓ(α)} \binom{r}{α_{j} − 1})\binom{(r + 1)k + n + 1 − |α| + ℓ(α)}{k − |α|}.

Proof. If r = 0, then the empty composition is the only element of C(k, 0). There are \binom{k+n+1}{k} elements of L(n + 1, k).

Now assume r ≥ 1. By Proposition 4, the number of labeled tableaux of shape α whose labels are all less than r is (∏_{j=1}^{ℓ(α)} \binom{r}{α_{j}−1}). The number of (rk + n + 1 + ℓ(α))-width lattice

sequences with height (k − |α|) is \binom{(r+1)k+n+1+−|α|+ℓ(α)}{k−|α|}. Therefore the number of pairs is the product of these two numbers, as desired.

3 Generalized hockey stick theorem

We now have the necessary results and notation to state the main result of this article.

Theorem 12. Let k, n, and r be nonnegative integers and let X be the set of labeled lattice sequences of type (k, n, r). For each (λ, L) ∈ X assign the weight wt((λ, L)) = sgn(λ). Then,

∑_{(λ,L)∈X} wt((λ, L)) = ∑_{i=0}^{k} \binom{(r + 1)i + n}{i}.  (4)

Proof. We now define a sign-reversing involution τ: X → X where the fixed points are enumerated by the right-hand side of Eq. (4). Let (λ, L) ∈ X and let η = rk + n + 1, ω = ω_{η}(L), γ = γ_{η}(L), μ = μ_{η}(L), and if sh(λ) ≠ ∅, let ν(λ, L) = η − 1 − r · ω − λ_{1,1}. We denote ν(λ, L) by ν.

Define τ: X → X by τ(λ, L) = (λ′, L′) where

λ′ = \begin{cases}λ ⊕ (μ mod r), & if μ < r · ω; \\ λ, & if μ ≥ r · ω and sh(λ) = ∅; \\ λ^{↙}, & if μ ≥ r · ω, |λ_{1}| ≥ 2, and γ ≤ ν; \\ λ + (μ mod r), & if μ ≥ r · ω, |λ_{1}| ≥ 2, and γ > ν. \end{cases}

and

L′ = \begin{cases}L_{[0,γ]}; (L_{[γ+1,η]} − 1); (L_{η} − 1 + ⌊\frac{μ}{r}⌋); (L_{[η+1,...]} − 2), & if μ < r · ω; \\ L, & if μ ≥ r · ω and sh(λ) = ∅; \\ L_{[0,ν]}; (L_{[ν+1,η]} + 1); (L_{[η+2,...]} + 2), & if μ ≥ r · ω, |λ_{1}| = 2, and γ ≤ ν; \\ L_{[0,ν]}; (L_{[ν+1,...]} + 1), & if μ ≥ r · ω, |λ_{1}| > 2, and γ ≤ ν; \\ L_{[0,γ]}; (L_{[γ+1,...]} − 1), & if μ ≥ r · ω, |λ_{1}| ≥ 2, and γ > ν. \end{cases}

To show that τ is an involution, we need to establish that (λ′′, L′′) = τ(λ′, L′) = (λ, L), but to evaluate τ(λ′, L′), it may be necessary to find the values of ω_{η}(L′), γ_{η}(L′), μ_{η}(L′), and ν(L′, λ′). We denote these values as ω′, γ′, μ′, and ν′ respectively. We note that τ is a sign reversing involution since by Proposition 1, sgn(λ) = − sgn(λ′) for all λ where λ ≠ λ′. Additionally, we note that sgn(λ) = 1 for all λ such that λ = λ′.

Case 1: μ < r · ω.

Since μ < r · ω, we have that L′ = L_{[0,γ]}; (L_{[γ+1,η]} − 1); (L_{η} − 1 + ⌊\frac{μ}{r}⌋); (L_{[η+1,...]} − 2) and λ′ = λ ⊕ (μ mod r). This means that |λ′_{1}| = 2 and λ′_{1,1} = (μ mod r).

By definition of ω′, we have that

ω′ = L′_{η+1} − L′_{η} = (L_{η} − 1 + ⌊\frac{μ}{r}⌋) − (L_{η} − 1) = ⌊\frac{μ}{r}⌋.

It follows from the construction of L′ that the ascent set of L′_{[0,η]} is a subset of the ascent set of L_{[0,η]}. Therefore it follows that γ′ ≤ γ and similarly we conclude that μ′ ≥ μ. This is because

μ′ = η − 1 − γ′ ≥ η − 1 − γ = μ.

Finally, the value of ν′ = γ because

ν′ = η − 1 − r · ω′ − λ′_{1,1} = η − 1 − (r · ⌊\frac{μ}{r}⌋ + (μ mod r)) = η − 1 − μ = γ.

Combining the equations and inequalities above, we have that μ′ ≥ μ ≥ r · ⌊\frac{μ}{r}⌋ = r · ω′, |λ′_{1}| = 2, and γ′ ≤ ν′.

Therefore we have λ′′ = λ^{′↙} = λ and

L′′ = L′_{[0,ν′]}; (L′_{[ν′+1,η]} + 1); (L′_{[η+2,...]} + 2)
= L_{[0,γ]}; (L_{[γ+1,η]} − 1 + 1); (L_{[η+1,...]} − 2 + 2)
= L.

Case 2: μ ≥ r · ω and sh(λ) = ∅.

In this case, τ(λ, L) = (λ, L) so τ(τ(λ, L)) = (λ, L).

Case 3: μ ≥ r · ω, |λ_{1}| = 2, and γ ≤ ν.

In this case, we have that L′ = L_{[0,ν]}; (L_{[ν+1,η]} + 1); (L_{[η+2,...]} + 2) and λ′ = λ^{↙}.

Therefore we have

ω′ = L′_{η+1} − L′_{η} = L_{η+2} + 2 − (L_{η} + 1) = L_{η+2} − L_{η} + 1.

Since L is weakly increasing, we have that L_{η+2} − L_{η} + 1 ≥ L_{η+1} − L_{η} + 1 = ω + 1 > ω. That is to say, ω′ ≥ ω + 1, i.e., ω′ > ω.

It follows from the construction of L′ that ν ∈ asc(L′) and that ν is the greatest element of the ascent set of L′_{[0,η]}. This is because γ ≤ ν and γ is the greatest element of the ascent set of L_{[0,η]}. Therefore we have that γ′ = ν. Since μ′ = η −1−γ′, we have that μ′ = η −1−ν. But since ν = η − 1 − r · ω − λ_{1,1}, we have that μ′ = r · ω + λ_{1,1}. Note that λ_{1,1} < r so we have that r · ω + λ_{1,1} < r · (ω + 1). But since ω′ > ω, we have μ′ < r · ω′.

Since μ′ < r · ω′, we have that λ′′ = λ′ ⊕ (μ′ mod r) = λ′ ⊕ λ_{1,1} = λ and

L′′ = L′_{[0,γ′]}; (L′_{[γ′+1,η]} − 1); (L′_{η} − 1 + ⌊\frac{μ′}{r} ⌋); (L′_{[η+1,...]} − 2)
= L_{[0,ν]}; (L_{[ν+1,η]} + 1 − 1); (L_{η} + 1 − 1 + ω); (L_{[η+2,...]} + 2 − 2)
= L.

Case 4: μ ≥ r · ω, |λ_{1}| > 2, and γ ≤ ν.

In this case, we have that L′ = L_{[0,ν]}; (L_{[ν+1,...]} + 1) and λ′ = λ^{↙}.

As |λ_{1}| > 2, the smallest entry of the first row of λ, λ_{1,1}, is removed to create λ′. Therefore, λ_{1,1} < λ′_{1,1} which implies ν > ν′.

By construction of L′, ω′ = ω and asc(L′) = asc(L) ∪ {ν}. As a result, γ′ = ν. But as ν > ν′, we have that γ′ > ν′. We also have that that μ′ ≥ r · ω′ and (μ′ mod r) = λ_{1,1} as μ′ = η − 1 − γ′ = η − 1 − ν = r · ω + λ_{1,1}.

Since μ′ ≥ r · ω′, |λ_{1}| ≥ 2, and γ′ > ν′, we have

L′′ = L′_{[0,γ′]}; (L′_{[γ′+1,...]} − 1)
= L_{[0,ν]}; (L_{[ν+1,...]} + 1 − 1)
= L

and λ′′ = λ′ + (μ′ mod r) = λ′ + λ_{1,1} = λ.

Case 5: μ ≥ r · ω, |λ_{1}| ≥ 2 and γ > ν.

In this case, we must first establish that λ + (μ mod r) is defined. Recall that by definition, 0 ≤ λ_{1,1} < r. Since γ > ν, we have that η − 1 − r · ω − λ_{1,1} < γ or equivalently, r · ω + λ_{1,1} > μ. Since μ ≥ r · ω and λ_{1,1} < r, we have that 0 ≤ (μ mod r) < λ_{1,1} and that (μ mod r) ∉ λ_{1} since λ_{1,1} is the smallest entry of λ_{1}. Since μ ≥ r · ω, |λ_{1}| ≥ 2 and γ > ν, we have that λ′ = λ + (μ mod r) and L′ = L_{[0,γ]}; (L_{[γ+1,...]} − 1). Note that this means that |λ′_{1}| > 2. By construction of L′ we have that ω′ = ω and that γ′ ≤ γ. This implies that μ′ ≥ μ ≥ r · ω′.

We show that γ′ ≤ ν′. In particular, since γ′ ≤ γ, we show ν′ = γ. Recall that μ < r · ω + λ_{1,1} and that λ_{1,1} < r. This means that r · ω ≤ μ < r(ω + 1), or equivalently, μ = r · ω + (μ mod r). Since ω′ = ω and (μ mod r) = λ′_{1,1}, we have that γ = η − 1 − μ = η − 1 − r · ω′ − λ′_{1,1} = ν′. Therefore γ′ ≤ ν′.

Since μ′ ≥ r · ω′, |λ′_{1}| > 2, and γ′ ≤ ν′, we have

L′′ = L′_{[0,ν′]}; (L′_{[ν′+1,...]} + 1)
= L_{[0,γ]}; (L_{[γ+1,...]} − 1 + 1)
= L

and λ′′ = λ^{′↙} = (λ + λ′_{1,1})^{↙} = λ.

Therefore the only fixed points of τ are when μ ≥ r · ω and sh(λ) = ∅. Since the lattice path of each fixed point is an element of L(rk + n + 1, k) and each fixed point has the same shape λ with sgn(λ) = 1, then to complete the proof, we must show that |\{L ∈ L(rk + n + 1, k) | μ_{η}(L) ≥ r · ω_{η}(L)\}| = ∑_{i=0}^{k} \binom{(r+1)i+n}{i}. This follows immediately from Lemma 9 and the fact that the value of ω_{η}(L) can take on any value from {0, …, k}.

When grouping together labeled tableaux of the same shape, Theorem 12 can be restated in the following way.

Corollary 13. For all nonnegative integers k, n, and r, we have

∑_{i=0}^{k} \binom{(r + 1)i + n}{i} = ∑_{α∈C(k,r)} sgn(α)(∏_{j=1}^{ℓ(α)} \binom{r}{α_{j} − 1})\binom{(r + 1)k + n + 1 − |α| + ℓ(α)}{k − |α|}. (5)

Proof. This follows immediately from Proposition 11.

When r = 0, since the only element of C(k, 0) is the empty composition, Corollary 13 gives the hockey stick identity (2).

Corollary 14.

∑_{i=0}^{k} \binom{i + n}{i} = \binom{k + 1 + n}{k}.

When r = 1, Corollary 13 gives the big hockey stick and pucks identity (3). This is because the only compositions in C(k, 1) are those that consist only of 2’s and there is a unique way to label each tableau.

Corollary 15.

∑_{i=0}^{k} \binom{2i + n}{i} = ∑_{i=0}^{⌊ \frac{k}{2} ⌋}(−1)^{i}\binom{2k + 1 + n − i}{k − 2i}.

We conclude with an example to help illustrate which terms appear in the right-hand side of Eq. (5).

Example 16. When r = 3, k = 5, and n = 0, Eq. (5) says that

∑_{i=0}^{5} \binom{4i}{i} = \binom{21}{5} − 3\binom{20}{3} + 3\binom{19}{2} − \binom{18}{1} + 3^{2}\binom{19}{1} − 3^{2}\binom{18}{0} − 3^{2}\binom{18}{0}. (6)

Each term on the right-hand side of Eq. (6) corresponds to one of compositions listed in Example 2.2. In Figure 3, the terms from the left-hand side of Eq. (6) are circled and the terms from the right-hand side are enclosed by squares.

\begin{matrix}( & {0 \atop 0} & ) \\ ( & {1 \atop 0} & ) \\ ( & {1 \atop 1} & ) \\ ( & {2 \atop 0} & ) \\ ( & {2 \atop 1} & ) \\ ( & {2 \atop 2} & ) \\ ( & {3 \atop 0} & ) \\ ( & {3 \atop 1} & ) \\ ( & {3 \atop 2} & ) \\ ( & {3 \atop 3} & ) \\ ( & {4 \atop 0} & ) \\ ( & {4 \atop 1} & ) \\ ( & {4 \atop 2} & ) \\ ( & {4 \atop 3} & ) \\ ( & {4 \atop 4} & ) \\ ( & {5 \atop 0} & ) \\ ( & {5 \atop 1} & ) \\ ( & {5 \atop 2} & ) \\ ( & {5 \atop 3} & ) \\ ( & {5 \atop 4} & ) \\ ( & {5 \atop 5} & ) \\ ( & {6 \atop 0} & ) \\ ( & {6 \atop 1} & ) \\ ( & {6 \atop 2} & ) \\ ( & {6 \atop 3} & ) \\ ( & {6 \atop 4} & ) \\ ( & {6 \atop 5} & ) \\ ( & {6 \atop 6} & ) \\ ( & {7 \atop 0} & ) \\ ( & {7 \atop 1} & ) \\ ( & {7 \atop 2} & ) \\ ( & {7 \atop 3} & ) \\ ( & {7 \atop 4} & ) \\ ( & {7 \atop 5} & ) \\ ( & {7 \atop 6} & ) \\ ( & {7 \atop 7} & ) \\ ( & {8 \atop 0} & ) \\ ( & {8 \atop 1} & ) \\ ( & {8 \atop 2} & ) \\ ( & {8 \atop 3} & ) \\ ( & {8 \atop 4} & ) \\ ( & {8 \atop 5} & ) \\ ( & {8 \atop 6} & ) \\ ( & {8 \atop 7} & ) \\ ( & {8 \atop 8} & ) \\ ( & {9 \atop 0} & ) \\ ( & {9 \atop 1} & ) \\ ( & {9 \atop 2} & ) \\ ( & {9 \atop 3} & ) \\ ( & {9 \atop 4} & ) \\ ( & {9 \atop 5} & ) \\ ( & {9 \atop 6} & ) \\ ( & {9 \atop 7} & ) \\ ( & {9 \atop 8} & ) \\ ( & {9 \atop 9} & ) \\ ( & {10 \atop 0} & ) \\ ( & {10 \atop 1} & ) \\ ( & {10 \atop 2} & ) \\ ( & {10 \atop 3} & ) \\ ( & {10 \atop 4} & ) \\ ( & {10 \atop 5} & ) \\ ( & {10 \atop 6} & ) \\ ( & {10 \atop 7} & ) \\ ( & {10 \atop 8} & ) \\ ( & {10 \atop 9} & ) \\ ( & {10 \atop 10} & ) \\ ( & {11 \atop 0} & ) \\ ( & {11 \atop 1} & ) \\ ( & {11 \atop 2} & ) \\ ( & {11 \atop 3} & ) \\ ( & {11 \atop 4} & ) \\ ( & {11 \atop 5} & ) \\ ( & {11 \atop 6} & ) \\ ( & {11 \atop 7} & ) \\ ( & {11 \atop 8} & ) \\ ( & {11 \atop 9} & ) \\ ( & {11 \atop 10} & ) \\ ( & {11 \atop 11} & ) \\ ( & {12 \atop 0} & ) \\ ( & {12 \atop 1} & ) \\ ( & {12 \atop 2} & ) \\ ( & {12 \atop 3} & ) \\ ( & {12 \atop 4} & ) \\ ( & {12 \atop 5} & ) \\ ( & {12 \atop 6} & ) \\ ( & {12 \atop 7} & ) \\ ( & {12 \atop 8} & ) \\ ( & {12 \atop 9} & ) \\ ( & {12 \atop 10} & ) \\ ( & {12 \atop 11} & ) \\ ( & {12 \atop 12} & ) \\ ( & {13 \atop 0} & ) \\ ( & {13 \atop 1} & ) \\ ( & {13 \atop 2} & ) \\ ( & {13 \atop 3} & ) \\ ( & {13 \atop 4} & ) \\ ( & {13 \atop 5} & ) \\ ( & {13 \atop 6} & ) \\ ( & {13 \atop 7} & ) \\ ( & {13 \atop 8} & ) \\ ( & {13 \atop 9} & ) \\ ( & {13 \atop 10} & ) \\ ( & {13 \atop 11} & ) \\ ( & {13 \atop 12} & ) \\ ( & {13 \atop 13} & ) \\ ( & {14 \atop 0} & ) \\ ( & {14 \atop 1} & ) \\ ( & {14 \atop 2} & ) \\ ( & {14 \atop 3} & ) \\ ( & {14 \atop 4} & ) \\ ( & {14 \atop 5} & ) \\ ( & {14 \atop 6} & ) \\ ( & {14 \atop 7} & ) \\ ( & {14 \atop 8} & ) \\ ( & {14 \atop 9} & ) \\ ( & {14 \atop 10} & ) \\ ( & {14 \atop 11} & ) \\ ( & {14 \atop 12} & ) \\ ( & {14 \atop 13} & ) \\ ( & {14 \atop 14} & ) \\ ( & {15 \atop 0} & ) \\ ( & {15 \atop 1} & ) \\ ( & {15 \atop 2} & ) \\ ( & {15 \atop 3} & ) \\ ( & {15 \atop 4} & ) \\ ( & {15 \atop 5} & ) \\ ( & {15 \atop 6} & ) \\ ( & {15 \atop 7} & ) \\ ( & {15 \atop 8} & ) \\ ( & {15 \atop 9} & ) \\ ( & {15 \atop 10} & ) \\ ( & {15 \atop 11} & ) \\ ( & {15 \atop 12} & ) \\ ( & {15 \atop 13} & ) \\ ( & {15 \atop 14} & ) \\ ( & {15 \atop 15} & ) \\ ( & {16 \atop 0} & ) \\ ( & {16 \atop 1} & ) \\ ( & {16 \atop 2} & ) \\ ( & {16 \atop 3} & ) \\ ( & {16 \atop 4} & ) \\ ( & {16 \atop 5} & ) \\ ( & {16 \atop 6} & ) \\ ( & {16 \atop 7} & ) \\ ( & {16 \atop 8} & ) \\ ( & {16 \atop 9} & ) \\ ( & {16 \atop 10} & ) \\ ( & {16 \atop 11} & ) \\ ( & {16 \atop 12} & ) \\ ( & {16 \atop 13} & ) \\ ( & {16 \atop 14} & ) \\ ( & {16 \atop 15} & ) \\ ( & {16 \atop 16} & ) \\ ( & {17 \atop 0} & ) \\ ( & {17 \atop 1} & ) \\ ( & {17 \atop 2} & ) \\ ( & {17 \atop 3} & ) \\ ( & {17 \atop 4} & ) \\ ( & {17 \atop 5} & ) \\ ( & {17 \atop 6} & ) \\ ( & {17 \atop 7} & ) \\ ( & {17 \atop 8} & ) \\ ( & {17 \atop 9} & ) \\ ( & {17 \atop 10} & ) \\ ( & {17 \atop 11} & ) \\ ( & {17 \atop 12} & ) \\ ( & {17 \atop 13} & ) \\ ( & {17 \atop 14} & ) \\ ( & {17 \atop 15} & ) \\ ( & {17 \atop 16} & ) \\ ( & {17 \atop 17} & ) \\ ( & {18 \atop 0} & ) \\ ( & {18 \atop 1} & ) \\ ( & {18 \atop 2} & ) \\ ( & {18 \atop 3} & ) \\ ( & {18 \atop 4} & ) \\ ( & {18 \atop 5} & ) \\ ( & {18 \atop 6} & ) \\ ( & {18 \atop 7} & ) \\ ( & {18 \atop 8} & ) \\ ( & {18 \atop 9} & ) \\ ( & {18 \atop 10} & ) \\ ( & {18 \atop 11} & ) \\ ( & {18 \atop 12} & ) \\ ( & {18 \atop 13} & ) \\ ( & {18 \atop 14} & ) \\ ( & {18 \atop 15} & ) \\ ( & {18 \atop 16} & ) \\ ( & {18 \atop 17} & ) \\ ( & {18 \atop 18} & ) \\ ( & {19 \atop 0} & ) \\ ( & {19 \atop 1} & ) \\ ( & {19 \atop 2} & ) \\ ( & {19 \atop 3} & ) \\ ( & {19 \atop 4} & ) \\ ( & {19 \atop 5} & ) \\ ( & {19 \atop 6} & ) \\ ( & {19 \atop 7} & ) \\ ( & {19 \atop 8} & ) \\ ( & {19 \atop 9} & ) \\ ( & {19 \atop 10} & ) \\ ( & {19 \atop 11} & ) \\ ( & {19 \atop 12} & ) \\ ( & {19 \atop 13} & ) \\ ( & {19 \atop 14} & ) \\ ( & {19 \atop 15} & ) \\ ( & {19 \atop 16} & ) \\ ( & {19 \atop 17} & ) \\ ( & {19 \atop 18} & ) \\ ( & {19 \atop 19} & ) \\ ( & {20 \atop 0} & ) \\ ( & {20 \atop 1} & ) \\ ( & {20 \atop 2} & ) \\ ( & {20 \atop 3} & ) \\ ( & {20 \atop 4} & ) \\ ( & {20 \atop 5} & ) \\ ( & {20 \atop 6} & ) \\ ( & {20 \atop 7} & ) \\ ( & {20 \atop 8} & ) \\ ( & {20 \atop 9} & ) \\ ( & {20 \atop 10} & ) \\ ( & {20 \atop 11} & ) \\ ( & {20 \atop 12} & ) \\ ( & {20 \atop 13} & ) \\ ( & {20 \atop 14} & ) \\ ( & {20 \atop 15} & ) \\ ( & {20 \atop 16} & ) \\ ( & {20 \atop 17} & ) \\ ( & {20 \atop 18} & ) \\ ( & {20 \atop 19} & ) \\ ( & {20 \atop 20} & ) \\ ( & {21 \atop 0} & ) \\ ( & {21 \atop 1} & ) \\ ( & {21 \atop 2} & ) \\ ( & {21 \atop 3} & ) \\ ( & {21 \atop 4} & ) \\ ( & {21 \atop 5} & ) \\ ( & {21 \atop 6} & ) \\ ( & {21 \atop 7} & ) \\ ( & {21 \atop 8} & ) \\ ( & {21 \atop 9} & ) \\ ( & {21 \atop 10} & ) \\ ( & {21 \atop 11} & ) \\ ( & {21 \atop 12} & ) \\ ( & {21 \atop 13} & ) \\ ( & {21 \atop 14} & ) \\ ( & {21 \atop 15} & ) \\ ( & {21 \atop 16} & ) \\ ( & {21 \atop 17} & ) \\ ( & {21 \atop 18} & ) \\ ( & {21 \atop 19} & ) \\ ( & {21 \atop 20} & ) \\ ( & {21 \atop 21} & ) \end{matrix}

Figure 3: Eq. (5) when r = 3, k = 5, and n = 0.

4 Acknowledgments

We thank the referees and editor for a careful reading of the paper and many suggestions that have improved the manuscript.

References

[1] B. A. Bondarenko, Generalized Pascal triangles and pyramids their fractals graphs and applications, Fibonacci Quart. 31 (1993), 162–164.

[2] P. Hilton and J. Pedersen, Looking into Pascal’s triangle: Combinatorics, arithmetic, and geometry, Math. Mag. 60 (1987), 305–316.

[3] C. H. Jones, Generalized hockey stick identities and n-dimensional blockwalking, Fibonacci Quart. 34 (1996), 280–288.

[4] S. Mehri, The hockey stick theorems in Pascal and trinomial triangles, arXiv preprint arXiv:1404.5106 [math.HO], 2016. Available at https://arxiv.org/abs/1404.5106.

[5] R. Merris, Combinatorics, Wiley, August 2003.

[6] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, 2025. Published electronically at https://oeis.org.

[7] R. P. Stanley, Enumerative Combinatorics: Volume 1, Cambridge University Press, 2nd edition, 2011.

2020 Mathematics Subject Classification: 05A19 ; 05A10 . Keywords: combinatorics, binomial identity, sign-reversing involution.

(Concerned with sequences \underline{A000027}, \underline{A000217}, \underline{A000292}, \underline{A000332}, \underline{A000389}, \underline{A000579}, \underline{A006134}, \underline{A007318}, \underline{A057552}, \underline{A079309}, \underline{A087413}, \underline{A188675}, \underline{A225612}, \underline{A225615}, \underline{A263134}, \underline{A371963}, \underline{A371964}, and \underline{A371965}.)

Received June 19 2025; revised versions received June 20 2025; July 4 2025; October 9 2025; October 31 2025. Published in Journal of Integer Sequences, December 9 2025.

Return to Journal of Integer Sequences home page.