Two Combinatorial Interpretations of Rascal Numbers

Amelia Gibbs and Brian K. Miceli One Trinity Place Department of Mathematics Trinity University San Antonio, TX 78212 USA

                  tgibbs@trinity.edu
                  bmiceli@trinity.edu

Abstract

The rascal triangle, a clever play on Pascal’s triangle, was defined recursively by Anggoro et al., and has since been studied by many others. We assign two combinatorial interpretations to the elements of the rascal triangle, and these elements are dubbed the rascal numbers. The first combinatorial interpretation of the rascal numbers involves counting ascents in binary words; the second interpretation involves pattern avoidance in the ascent sequences studied by Duncan and Steingrímsson and is directly related to a more recent paper by Baxter and Pudwell. We provide many new Pascal-like formulas involving rascal numbers, and we conclude with a natural generalization of these numbers.

1 Introduction

Anggoro et al. [1] defined a Pascal-like triangular sequence, which they called the rascal triangle. Accordingly, let us call the numbers in the n-th row and k-th column of this triangle the n,k-th rascal number, R_{n,k}, which corresponds to the sequence \underline{A077028} in the On-Line Encyclopedia of Integer Sequences (OEIS) [9]. Then Anggoro et al. defined^{1} R_{0,0} = R_{1,0} = R_{1,1} = 1, and for n ≥ 2,

R_{n,k} = \frac{R_{n−1,k}R_{n−1,k−1} + 1}{R_{n−2,k−1}},  (1)

where R_{n,k} = 0 whenever k > n, n < 0, or k < 0. The first few rows of the rascal triangle are shown below, where the top row is the 0-th row, the leftmost column is the 0-th column, and all (unshown) entries above, to the left, or to the right of the given entries are equal to 0.

1

1 1
1 2 1
1 3 3 1
1 4 5 4 1
1 5 7 7 5 1
1 6 9 10 9 6 1

Anggoro et al. then showed that R_{n,k} is indeed an integer for all n, k, which is not immediately obvious from Equation (1), and they did this by showing, algebraically, that R_{n,k} = k(n − k) + 1. For instance we can see in our triangle above that R_{6,3} = 10, and it is in fact the case that 10 = 3(6 − 3) + 1. In a subsequent note by Fleron [7], it is shown, again algebraically, that the rascal numbers also satisfy the following linear recurrence, subject to identical initial conditions given above:

R_{n,k} = R_{n−1,k} + R_{n−1,k−1} − R_{n−2,k−1} + 1.  (2)

Subsequently, Ashfaque [2] gave a single identity involving rascal numbers and binomial coefficients (our Theorem 11, which that author proved algebraically, but we prove combinatorially). Later, an extensive paper by Hotchkiss [8] generalized the idea of the rascal triangle, but this work was also algebraic, and giving a combinatorial sense of these generalized objects was not the goal of that work. And yet, as rascal numbers may be defined in a way that so closely resembles the recursion for binomial coefficients, it seems like some straightforward combinatorial interpretation(s) of rascal numbers must exist.

2 Ascents and binary words

Given a set, S, of integers and a string, w = w_{1}w_{2} ⋯ w_{n}, of elements from S, we call w a word of length n over S. Two sets we regularly use in this paper are [m] = {1, 2, …, m} and [m]_{0} = {0, 1, 2, …, m}, where m is a nonnegative integer. Given w, we define an ascent position of w to be an index 1 ≤ i ≤ n − 1 such that w_{i} < w_{i+1}, and we define the ascent number of w to be the number of distinct ascent positions of w, denoted by asc(w). For example, w = 2051159858 is a word of length 10 over [9]_{0}, and asc(2\underline{0}51\underline{1}\underline{5}98\underline{5}8) = 4, where the ascent positions of w have been underlined. The word of length n = 0, denoted by ϵ, is called the empty word, and asc(ϵ) = 0. From here onward we adopt the notation x^{j} to denote the letter x repeated j times; for example, we may write the word u = 11110220005 as u = 1^{4}02^{2}0^{3}5. Now, w is a binary word if w_{i} ∈ [1]_{0} for all 1 ≤ i ≤ n. We then define B_{k}(n) to be the set of binary words of length n with exactly k 1’s and at most 1 ascent, and set b_{k}(n) = |B_{k}(n)|. As an example,

1Anggoro et al. [1] did not technically do it this way, because they did not give an explicit indexing, but this is the corresponding recursion based on their description. The same is true for Fleron’s note [7].

B_{4}(6) = {1^{4}0^{2}, 1^{3}010, 1^{3}0^{2}1, 1^{2}01^{2}0, 1^{2}0^{2}1^{2}, 101^{3}0, 10^{2}1^{3}, 0^{2}1^{4}, 01^{4}0},

so that b_{4}(6) = 9, which happens to be exactly R_{6,4}. We are now ready to give our first combinatorial interpretation of rascal numbers.

Theorem 1. For n, k ∈ ℤ, we have R_{n,k} = b_{k}(n).

Proof. First we see that B_{k}(n) is the empty set whenever k > n or either of n or k is negative, and so b_{k}(n) = 0 = R_{n,k} in those cases. Next, b_{0}(0) = |B_{0}(0)| = |{ϵ}| = 1 = R_{0,0}; similarly, B_{0}(1) = {0} and B_{1}(1) = {1}, so that b_{0}(1) = 1 = R_{1,0} and b_{1}(1) = 1 = R_{1,1}. Therefore, the initial conditions for b_{k}(n) and R_{n,k} are identical.

Now suppose 0 ≤ k ≤ n and n ≥ 2. Then every b ∈ B_{k}(n) has one of following two forms:

(1) 1^{k} 0^{n−k} if b has 0 ascents, or

(2) 1^{k−i} 0^{j} 1^{i} 0^{n−k−j} with 0 < i ≤ k and 0 < j ≤ n − k if b has 1 ascent.

Accordingly, there is only one such word in B_{k}(n) with 0 ascents. To construct the words in B_{k}(n) with exactly 1 ascent, we simply choose allowed values for i, j. We can see that there are k choices for i, namely 1, 2, …, k, and similarly, there are n−k choices for j. Thus, there are k(n − k) elements of B_{k}(n) with exactly 1 ascent, giving b_{k}(n) = 1 + k(n − k) = R_{n,k}.

We now prove many other facts about rascal numbers using this combinatorial interpretation, beginning with showing that these numbers are unimodal and symmetric. To see unimodality, we need only notice that b_{k}(n) is quadratic in k, and thus each row of the rascal Triangle consists of a unimodal sequence. To show symmetry, we first give a couple of standard definitions for words. Given the binary word b = b_{1}b_{2} ⋯ b_{n}, define the reverse of b to be b^{r} = b_{n} ⋯ b_{2}b_{1}, and the complement of b to be b^{c} = b′_{1}b′_{2} ⋯ b′_{n}, where b′_{i} = 0 if b_{i} = 1 and b′_{i} = 1 if b_{i} = 0. Second, notice that the reverse and complement operations are their own inverses, that is, b = (b^{r})^{r} = (b^{c})^{c}.

Theorem 2. For n, k ∈ ℤ with 0 ≤ k ≤ n we have R_{n,k} = R_{n,n−k}.

Proof. Given b = 1^{v}0^{u}1^{t}0^{s} ∈ B_{k}(n), define the function f by f(b) = (b^{r})^{c}. Notice that b^{r} = 0^{s}1^{t}0^{u}1^{v} still has length n and k 1’s. Then (b^{r})^{c} = 1^{s}0^{t}1^{u}0^{v} has length n and n − k 1’s. Accordingly, f is a map from B_{k}(n) into B_{n−k}(n). However, since f is the composition of two invertible functions, it is itself invertible, and thus a bijection, giving that |B_{k}(n)| = |B_{n−k}(n)|, as desired.

Next we turn our attention to Fleron’s recursion from Equation (2), which we prove using the principle of inclusion and exclusion, and then we subsequently prove a generalization of Equation (1). Both proofs rely heavily on the following lemma.

Lemma 3. For n, k, ℓ, u ∈ ℤ with 0 ≤ ℓ, u and ℓ ≤ k ≤ n−u, the quantity R_{n−u−ℓ,k−ℓ} counts the number of elements in B_{k}(n) which start with at least ℓ 1’s and end with at least u 0’s.

Proof. Given an element of B_{k}(n) that starts with at least ℓ 1’s and ends with at least u 0’s, we can remove ℓ leading 1’s and u trailing 0’s to get an element of B_{k−ℓ}(n − ℓ − u). Since this process is invertible, we have a bijection, and thus we obtain our desired result.

Theorem 4 (Fleron’s recursion). Given R_{0,0} = R_{1,0} = R_{1,1} = 1 and R_{n,k} = 0 if k > n or if n or k is negative, we have

R_{n,k} = R_{n−1,k} + R_{n−1,k−1} − R_{n−2,k−1} + 1.

Proof. We have that the left side of this recursion, R_{n,k}, counts the number of words in B_{k}(n), and all of these words either end in a 0 or end in a 1. By Lemma 3, there are exactly R_{n−1,k} of these that end in 0. Similarly, we may add a 1 to the end of every binary word of length n − 1 with exactly k − 1 1’s and at most 1 ascent, and we will obtain all the words counted ending in 1 counted by R_{n,k}: there are R_{n−1,k−1} such words. However, we have possibly overcounted in this latter case, because every word of length n − 1 that was of the form 1^{k−1−u}0^{t}1^{u}0^{v} with t, u, v > 0 has 2 ascents when we add a 1 to the end. Reapplying our lemma, there are R_{n−2,k−1} − 1 such words, because 1^{k−1}0^{n−k+1} is counted by R_{n−2,k−1}, but this is the only such word which is not of the form 1^{k−1−u}0^{t}1^{u}0^{v} with t, u, v > 0. Thus, the number of words in B_{k}(n) ending in 1 is R_{n−1,k−1} − (R_{n−2,k−1} − 1).

To make the proof of the following theorem a bit more clear and concise, we introduce some notation. Throughout the following proof, we use β to mean any “appropriate” binary word. Formally, for the binary words w_{0} and w_{2}, the β in w_{0}βw_{2} ∈ B_{k}(n) represents any binary word w_{1} such that w_{0}w_{1}w_{2} ∈ B_{k}(n). For example, if we have 1β0 ∈ B_{2}(4), then β represents any word in the set {10, 01}.

Theorem 5 (Generalization of Equation (1)). Let n, k, ℓ, u ∈ ℤ with 0 ≤ ℓ, u and ℓ ≤ k ≤ n − u. Then we have

R_{n,k} = \frac{R_{n−u,k}R_{n−ℓ,k−ℓ} + uℓ}{R_{n−u−ℓ,k−ℓ}}.  (3)

Proof. We will equivalently prove that

uℓ = R_{n,k}R_{n−ℓ−u,k−ℓ} − R_{n−u,k}R_{n−ℓ,k−ℓ}

by creating a sequence of pairs of sets, (S_{i}, T_{i}), such that |S_{i}| − |T_{i}| = uℓ. To that end, Lemma 3 motivates us to first consider the following sets, S_{0} and T_{0}, which are counted by R_{n,k}R_{n−ℓ−u,k−ℓ} and R_{n−u,k}R_{n−ℓ,k−ℓ}, respectively:

S_{0} = {(w, 1^{ℓ}β0^{u}) ∈ (B_{k}(n))^{2}} and T_{0} = {(β0^{u}, 1^{ℓ}β) ∈ (B_{k}(n))^{2}}.

First, note that elements of the form (β0^{u}, 1^{ℓ}β0^{u}) are in both S_{0} and T_{0}. So they naturally pair off with one another, which leaves us with

S_{1} = {(β10^{x}, 1^{ℓ}β0^{u}) ∈ (B_{k}(n))^{2} | 0 ≤ x < u}

and T_{1} = {(β0^{u}, 1^{ℓ}β10^{x}) ∈ (B_{k}(n))^{2} | 0 ≤ x < u}.

Now we can apply the map (w, z) ↦ (z, w) on elements in T_{1} of the form (1^{ℓ}β0^{u}, 1^{ℓ}β10^{x}) where 0 ≤ x < u. This results in all elements of the form (1^{ℓ}β10^{x}, 1^{ℓ}β0^{u}) in S_{1} being paired off with an element of T_{1}. Therefore we are left with

S_{2} = {(1^{y}0β10^{x}, 1^{ℓ}β0^{u}) ∈ (B_{k}(n))^{2} | 0 ≤ x < u, 0 ≤ y < ℓ}

and T_{2} = {(1^{y}0β0^{u}, 1^{ℓ}β10^{x}) ∈ (B_{k}(n))^{2} | 0 ≤ x < u, 0 ≤ y < ℓ}.

We observe that T_{2} does not contain any elements where either component has 0 ascents as those are of the form 1^{k}0^{n−k}, but x < u ≤ n − k and y < ℓ ≤ k. So both components of a pair in T_{2} must have 1 ascent. Now, knowing that a binary word has 1 ascent, starts with a 1’s, and ends with b 0’s, is sufficient to uniquely determine the word. Therefore, 1^{a}0β10^{b} must be the word 1^{a}0^{n−k−b}1^{k−a}0^{b}, and we will exploit this to make the following map easier to read. We apply the map (1^{y}0β10^{a}, 1^{b}0β10^{x}) ↦ (1^{y}0β10^{x}, 1^{b}0β10^{a}) to all elements of T_{2} to get elements of S_{2}—this simply interchanges the number of 0’s that each component ends in, and adjusting the number of zeros elsewhere in the word (to ensure the words in each component remain in B_{k}(n)). This map is injective, as we only need to know a, b, x, y to reconstruct the original pair, and that information can be extracted from the image of the pair. Also, since 0 < n − k − a and 0 < k − b, the above map does not map to elements of the form (1^{y}β0^{x}, 1^{k}0^{n−k}) ∈ S_{2} where 0 ≤ x < u and 0 ≤ y < ℓ. Since choosing a value for x and y uniquely determines such an element of S_{2}, we only need to count the number of choices for x, y. There are u choices for x and ℓ choices for y so there are exactly uℓ elements of S_{2} which are not in the image of this map. Therefore we conclude that

uℓ = |S_{2}| − |T_{2}|
= |S_{1}| − |T_{1}|
= |S_{0}| − |T_{0}|
= R_{n,k}R_{n−u−ℓ,k−ℓ} − R_{n−u,k}R_{n−ℓ,k−ℓ}.

The following results provide two other recursive relationships between rascal numbers.

Theorem 6. For n, m, k ∈ ℤ with n, m, k ≥ 0, we have

R_{n+m,k} = R_{n,k} + R_{m+k,k} − 1.  (4)

Proof. By Theorem 1, R_{n+m,k} = b_{k}(n + m), so we need to show that the right-hand side of Equation (4) counts this as well.

By Lemma 3, R_{n,k} is the number of w ∈ B_{k}(n + m) which end with at least m 0’s. So, we only need to count the number of w ∈ B_{k}(n + m) which end in strictly less than m 0’s. Since w ends in less than m 0’s and there are n + m − k total 0’s in w, the first consecutive string of 0’s must contain more than n − k 0’s. So, we can remove the first n − k 0’s in the string to get a word with k 1’s and n + m − k − (n − k) = m 0’s and one ascent. This new word is an element of B_{k}(m + k) \ {1^{k}0^{m}}. Furthermore, since this process is reversible, there are exactly |B_{k}(m + k) \ {1^{k}0^{m}}| = R_{m+k.k} − 1 such words. Summing these two cases, we get the right-hand side of Equation (4), as desired.

Theorem 7. For n, k ∈ ℤ with 0 < k < n, we have kR_{n−1,k−1} − 1 = (k − 1)R_{n,k}.

Proof. Let S be the set of w ∈ B_{k}(n) where w begins with a 1 and we have circled one of the 1’s in w, and let T be the set of w ∈ B_{k}(n) where we have circled a 1 in w which is not the first in w. By Lemma 3, R_{n−1,k−1} counts w ∈ B_{k}(n) which begin with a 1, we have

|S| = kR_{n−1,k−1} and |T | = (k − 1)R_{n,k},

where k and k − 1 account for circling the 1’s, respectively. So it suffices to construct an injective map f: T → S whose image has cardinality |S| − 1. Given w ∈ T, we define f as follows.

(1) If w starts with a 1, then set f(w) = w ∈ S.

(2) If w starts with a 0, then all 1’s in w are located in a consecutive string. Split this consecutive string of 1’s before the circled 1, and then move the right half to the beginning of w. Since this new word, z, is still in B_{k}(n), has a circled 1, and begins with a 1, it is an element of S. So set f(w) = z.

As constructed, case (1) maps w to a word whose first 1 is not circled while case (2) maps w to a word whose first 1 is circled, so there is no overlap in the image of cases (1) and (2). Since both case (1) and (2) are easily inverted, f is injective. Moreover, the element b = 1^{k}0^{n−k} which has its first 1 circled is in S but is not mapped to by f, as if there exists w ∈ T such that f(w) = b, then w must fall into case (2) since the first 1 of b is circled. However, since the first 1 of w is not circled, applying f to w leaves an ascent, but asc(b) = 0. Since f is injective and only 1 element of S is not in the image of f, we conclude that |T | = |f(T)| = |S| − 1, that is (k − 1)R_{n,k} = kR_{n−1,k−1} − 1.

3 Some identities

Since our primary combinatorial interpretation of the rascal numbers involves a subset of binary words of length n with k 1’s, whereas \binom{n}{k} counts the total number of binary words with length n and k 1’s, it seems natural to look for binomial-type identities involving R_{n,k}. To that end, we begin by proving various row and column sum identities for R_{n,k}.

Theorem 8 (Row sum). For n ∈ ℤ with n ≥ 0, we have

∑_{k=0}^{n} R_{n,k} = \binom{n + 1}{3} + n + 1.  (5)

Proof. Setting

B(n) = ⋃_{k=0}^{n} B_{k}(n),

we first note that the left-hand side of Equation (5) counts B(n).

Now pick w ∈ B(n). If asc(w) = 0, then w = 1^{k}0^{n−k} for some 0 ≤ k ≤ n. Since there are n + 1 choices of k, there are exactly n + 1 such w. Otherwise asc(w) = 1, so that w = 1^{x}0^{z}1^{y}0^{n−x−y−z} where 0 < z, y and 0 ≤ x with x+y+z ≤ n. Choosing appropriate x, y, z uniquely determines w, so it suffices to count solutions to x+y+z ≤ n. If x+y+z ≤ n, then there exists some t ∈ ℤ with t ≥ 0 such that x + y + z + t = n, and solutions to this equation are in one-to-one correspondence with positive integer solutions to x′ + y + z + t′ = n + 2. There are exactly

\binom{n + 2 − 1}{4 − 1} = \binom{n + 1}{3}

such solutions, so there are the same number of w ∈ B(n) with asc(w) = 1.

Summing these two cases, we find that the right-hand side of Equation (5) also counts B(n), giving the desired equality.

Theorem 9 (Column sum). For k, r ∈ ℤ with k, r ≥ 0, we have

∑_{i=0}^{r} R_{k+i,k} = k\binom{r + 1}{2} + r + 1.  (6)

Proof. The left-hand side of Equation (6) counts B = ⋃_{i=0}^{r} B_{k}(k + i), and every word in B must have a length of at least k but at most k + r. So, for each possible length, there is exactly one word in B with 0 ascents. Therefore, there are r + 1 such words in B. Now we only need to count w ∈ B such that asc(w) = 1. Such w must have the form 1^{k−x}0^{y+1}1^{x}0^{z} where 1 ≤ x ≤ k, 0 ≤ y, z and (y + 1) + z ≤ r. A given choice of x, y, z uniquely determines w, and vice versa, so such 3-tuples are in one-to-one correspondence with w ∈ B such that asc(w) = 1. Therefore, it suffices to count all such 3-tuples. If (y + 1) + z ≤ r, then there exists t ∈ ℤ with 0 ≤ t and (y + 1) + z + t = r, or equivalently, y + z + t = r − 1. There are exactly

\binom{(r − 1) + 3 − 1}{3 − 1} = \binom{r + 1}{2}

nonnegative integer solutions to this equation, and since there are exactly k choices for x, we have that there are exactly

k\binom{r + 1}{2}

such 3-tuples. Summing the two cases together, we find that

∑_{i=0}^{r} R_{k+i,k} = |B| = k\binom{r + 1}{2} + r + 1,

as desired.

Theorem 10 (Binomial-weighted row sum). For n ∈ ℤ with n ≥ 0, we have

∑_{k=0}^{n} \binom{n}{k}R_{n,k} = 2^{n−2}\binom{n}{2} + 2^{n}.  (7)

Proof. For 0 ≤ k ≤ n, let T_{k} be the set of all pairs (w_{1}, w_{2}) where w_{1} is a binary word of length n with exactly k 1’s and w_{2} ∈ B_{k}(n), and set T = ⋃_{k=0}^{n} T_{k}. Then |T_{k}| = \binom{n}{k}R_{n,k}, and T_{i} ∩ T_{j} = ∅ whenever i ≠ j. Accordingly, the left-hand side of Equation (7) is |T |. Now for every (w_{1}, w_{2}) ∈ T, either asc(w_{2}) = 0 or asc(w_{2}) = 1.

(1) There are 2^{n} total binary words of length n, and for each 0 ≤ k ≤ n there is exactly one word with 0 ascents. So, there are 2^{n} pairs (w_{1}, w_{2}) ∈ T such that asc(w_{2}) = 0.

(2) If asc(w_{2}) = 1, then w_{1}, w_{2} must both have at least one 0 and one 1, so we construct the pair (w_{1}, w_{2}) as follows. Choose {i, j} ⊆ [n] with i < j and place a 0 at the i-th index of w_{1} and a 1 at the j-th index of w_{1}. Then fill in the remaining n − 2 spots of w_{1}. Let k be the number of 1’s in w_{1}, r be the number of 1’s with index strictly less that j, and s be the number of 0’s with index strictly less than i. Then we set w_{2} = 1^{k−r−1}0^{s+1}1^{r+1}0^{n−k−s−1}. We can then recover r and s from w_{2}, which gives that the i-th bit of w_{1} is the 0 which is preceded by exactly s 0’s and the j-th bit is the 1 which is preceded by exactly r 1’s. Therefore, we can determine {i, j} and the binary word of length n − 2 from the pair (w_{1}, w_{2}) so this construction is invertible. Thus, there are 2^{n−2}\binom{n}{2} such pairs.

Summing cases (1) and (2), we conclude that the right-hand side of Equation (7) is also |T |, giving the desired equality.

The next identity was proved algebraically by Ashfaque [2], but we provide a combinatorial proof here. This identity also gives a combinatorial interpretation of the sequence \underline{A051744} in the OEIS [9].

Theorem 11. For n ∈ ℤ with n ≥ 2, we have

∑_{i=1}^{n} ∑_{j=1}^{i−1} R_{i,j} = \binom{n + 2}{4} + \binom{n}{2}.  (8)

Proof. Define

T = ⋃_{i=1}^{n} (⋃_{j=1}^{i−1} B_{j}(i)) ,

that is, T is the set of all binary words of length at most n with at most 1 ascent and at least one 0 and one 1. Then the left-hand side of Equation (8) is exactly |T |. Let w ∈ T.

(1) If asc(w) = 0, then w takes the form 1^{x}0^{y} where x, y > 0 and x + y ≤ n. The choice of x, y uniquely determines w so it suffices to count such pairs (x, y). Since x + y ≤ n, there exists a t ∈ ℤ such that t ≥ 0 and x + y + t = n. Solutions to this equation are in one-to-one correspondence with positive integer solutions to x + y + t′ = n + 1, which are counted by

\binom{n + 1 − 1}{3 − 1} = \binom{n}{2}.

(2) Alternatively, asc(w) = 1, in which case w has the form 1^{x}0^{y}1^{z}0^{t} such that y, z > 0, x, t ≥ 0, and x + y + z + t ≤ n. Choosing such x, y, z, t uniquely determines w, so it suffices to count all such tuples (x, y, z, t). Since x + y + z + t ≤ n, there exists some a ∈ ℤ such that a ≥ 0 and x + y + z + t + a = n. Solutions to this equation are in one-to-one correspondence with positive integer solutions to x′ + y + z + t′ + a′ = n + 3, which are counted by

\binom{n + 3 − 1}{5 − 1} = \binom{n + 2}{4}.

Thus, summing cases (1) and (2) gives that |T | is also the right-hand side of Equation (8).

The next identity involves alternating sums, and to prove this result we construct involutions to pair off elements of opposite sign. To begin, for a function f: X → X, we let fix(f) denote the set of all fixed points of f.

Theorem 12. For n, k, r ∈ ℤ with 0 ≤ k ≤ n and r ≥ 2, we have

∑_{j=0}^{r}(−1)^{r−j}\binom{r}{j}R_{n+j,k} = 0.  (9)

Proof. Let r ≥ 2, with P([r]) denoting the power set of [r]. Set

T = {(S, w) ∈ P([r]) × B_{k}(n + r) | w ends in at least r − |S| 0’s},

and for any set S define

S ⊕ x = \begin{cases}S \ \{x\}, & if x ∈ S; \\ S ∪ \{x\}, & if x ∉ S. \end{cases}

Next, define wt : T → {±1} by (S, w) ↦ (−1)^{r−|S|}. Then

∑_{j=0}^{r}(−1)^{r−j}\binom{r}{j}R_{n+j,k} = ∑_{(S,w)∈T} wt(S, w).  (10)

Now, define I_{1}: T → T as follows.

(1) If w ends in at least r 0’s then set

I_{1}(S, w) = (S ⊕ r, w).

(2) This leaves the case where w ends in fewer than r 0’s so w = 1^{k−x}0^{n+r−k−y}1^{x}0^{y} where 1 ≤ x ≤ k and r − |S| ≤ y < r. Then we set

I_{1}(S, w) = \begin{cases}(S ⊕ r, w), & if r − |S| < y; \\ (S ⊕ r, w), & if r − |S| = y and r ∉ S; \\ (S, w), & if r − |S| = y and r ∈ S. \end{cases}

Since ⊕ is an involution, I_{1} is itself a sign-reversing, weight-preserving involution, and so Equation (10) becomes

∑_{j=0}^{r}(−1)^{r−j}\binom{r}{j}R_{n+j,k} = ∑_{(S,w)∈fix(I_{1})} wt(S, w).

By construction of I_{1}, we have fix(I_{1}) = {(S, w) ∈ T | w ends in exactly r − |S| 0’s and r ∈ S}. Now define I_{2}: fix(I_{1}) → fix(I_{1}) as follows. For (S, w) ∈ fix(I_{1}) where w = 1^{k−x}0^{n+|S|−k}1^{x}0^{r−|S|}, set

I_{2}(S, w) = \begin{cases}(S ⊕ 1, 1^{k−x}0^{n+|S|+1−k}1^{x}0^{r−|S|−1}), & if 1 ∉ S; \\ (S ⊕ 1, 1^{k−x}0^{n+|S|−1−k}1^{x}0^{r−|S|+1}), & if 1 ∈ S. \end{cases}

By construction, I_{2} is a sign-reversing, weight-preserving involution with no fixed points. Thus, our sum is 0 when r ≥ 2, as desired.

Another alternating sum identity is given here, but this result follows directly from Theorem 23 in Section 5, and so we omit a proof here.

Theorem 13 (Alternating row sum). For n ∈ ℤ with n ≥ 0, we have

∑_{k=0}^{n}(−1)^{k}R_{n,k} = \begin{cases}0, & if n ≡ 1 (mod 2); \\ 1 − \frac{n}{2}, & if n ≡ 0 (mod 2). \end{cases}

We conclude this section with two product formulas involving rascal numbers. First, for nonnegative integers n, k, we define the falling factorial, (n)↓_{k}, as follows:

(n)↓_{k}= \begin{cases}0, & if k > n; \\ 1, & if k = 0; \\ ∏_{i=1}^{k}(n − i + 1), & otherwise. \end{cases}

Theorem 14. For n, m ∈ ℤ with 1 ≤ m ≤ n, we have

∏_{k=1}^{m}(R_{n,k} − 1) = ∑_{S⊆[m]}(−1)^{m−|S|} ∏_{i∈S} R_{n,i} = m!(n − 1)↓_{m} .  (11)

Proof. Notice that R_{n,k} − 1 is the number of binary words with length n and k 1’s which have 1 ascent. Therefore, the product on the left of Equation (11) counts |T |, where

T = {(w_{1}, …, w_{m}) | w_{i} ∈ B_{i}(n) and asc(w_{i}) = 1}.

Given (w_{1}, …, w_{m}) ∈ T, each w_{i} = 1^{i−x}0^{y}1^{x}0^{n−i−y} where 1 ≤ x ≤ i and 1 ≤ y ≤ n − i. So choosing values for x and y uniquely determines w_{i}. Since 1 ≤ x ≤ i and 1 ≤ y ≤ n − i, there are i(n − i) such w_{i}’s, which implies that there are m!(n − 1)↓_{m} such (w_{1}, …, w_{m})’s. Alternatively, we can find |T | using the principle of inclusion and exclusion by considering the set V = {(w_{1}, …, w_{m})|w_{i} ∈ B_{i}(n)}. Then, setting A_{i} = {(w_{1}, …, w_{m}) ∈ V | asc(w_{i}) = 0} gives that |T | = |A_{1}^{c} ∩ ⋯ ∩ A_{m}^{c}| where A_{i}^{c} denotes the complement of A_{i} in V. Since there is exactly one word in B_{i}(n) with 0 ascents,

|A_{i_{1}} ∩ ⋯ ∩ A_{i_{k}}| = ∏_{j∈[m]\{i_{1},...,i_{k}}} R_{n,j}.

Thus, we get

|T | = ∑_{k=0}^{m}(−1)^{k} ∑_{|S|=m−k^{S⊆[m]}} ∏_{i∈S} R_{n,i} = ∑_{S⊆[m]}(−1)^{m−|S|} ∏_{i∈S} R_{n,i}.

With the above result established, another relationship between binomial coefficients and R_{n,k} becomes apparent, and while the following result is a direct consequence of simply dividing both sides of Equation (11) by (m!)^{2}, we provide a standalone combinatorial proof.

Corollary 15. For n, m ∈ ℤ with 1 ≤ m ≤ n, we have

\frac{1}{(m!)^{2}} ∏_{k=1}^{m}(R_{n,k} − 1) = \frac{1}{(m!)^{2}} ∑_{S⊆[m]}(−1)^{m−|S|} ∏_{i∈S} R_{n,i} = \binom{n − 1}{m}.  (12)

Proof. Let T = {(w_{1}, …, w_{m}) | w_{i} ∈ B_{i}(n) and asc(w_{i}) = 1}, as defined in the proof of Theorem 14, so that Equation (12) becomes

\frac{1}{(m!)^{2}} |T | = \frac{1}{(m!)^{2}} |T | = \binom{n − 1}{m}.

Now define ∼_{1} on B_{i}(n) \ {1^{i}0^{n−i}} by w_{1} ∼_{1} w_{2} if and only if w_{1} = 1^{i−x}0^{y}1^{x}0^{n−i−y} where 1 ≤ x ≤ i, 1 ≤ y ≤ n − i and w_{2} = 1^{i−z}0^{y}1^{z}0^{n−i−y} where 1 ≤ z ≤ n − i. In essence, under ∼_{1} we only care about the relative position of the 0’s in the words without regard for the position of the 1’s. Next, we define ∼_{2} on T by (w_{1}, …, w_{m}) ∼_{2} (w′_{1}, …, w′_{m}) if and only if w_{i} ∼_{1} w′_{i} for all 1 ≤ i ≤ m. Since, for a fixed y, there are i choices of x, we have that |[w_{i}]_{∼_{1}} | = i for every w_{i} ∈ B_{i}(n) \ {1^{i}0^{n−i}}. So

|[(w_{1}, …, w_{m})]_{∼_{2}} | = ∏_{i=1}^{m} |[w_{i}]_{∼_{1}} | = m!

for every (w_{1}, …, w_{m}) ∈ T, which implies |T/ ∼_{2} | = |T |/m!. Note that to uniquely determine an equivalence class of ∼_{2}, we only need a y_{i}, where w_{i} = 1^{∗}0^{y_{i}}1^{∗}0^{n−i−y_{i}} with 1 ≤ y_{i} ≤ n − i for each i ∈ [m]. Moreover, given an equivalence class of ∼_{2}, we can uniquely determine an m-tuple, (y_{1}, …, y_{m}) with 1 ≤ y_{i} ≤ n − i, by taking y_{i} to be the number of 0’s preceding the first ascent. Therefore, elements of T/ ∼_{2} are in one-to-one correspondence with m-tuples of the form (y_{1}, …, y_{m}) with 1 ≤ y_{i} ≤ n − i. Let f be a map which takes such an m-tuple, (y_{1}, …, y_{m}), to an m-permutation of [n − 1], a_{1} … a_{m}, defined as follows. Set a_{1} = y_{1} and S_{1} = [n − 1] − {y_{1}}. Then set a_{i} to the y_{i}-th smallest element of S_{i−1} for 1 < i ≤ m. This map can be inverted by setting y_{1} = a_{1} and S_{1} = [n − 1] − {a_{1}}. Then set y_{i} = j where a_{i} is the j-th smallest element of S_{i−1} for 1 < i ≤ m. Thus, T/ ∼_{2} is in one-to-one correspondence with m-permutations of [n−1]. Then we can remove the ordering of the m-permutations giving us m-element subsets of [n − 1] which implies that

\binom{n − 1}{m} = \frac{|T/ ∼_{2} |}{m!} = \frac{1}{(m!)^{2}} |T |.

4 Ascent sequences and pattern avoidance

Going back to ascents in words, notice that only the relative values of the integers that comprise a word are important when computing the ascent number of a word, and so it is common to define the reduction of a word, w = w_{1}w_{2} ⋯ w_{n}, to be the word obtained by replacing the i-th smallest letter of w with the letter i − 1, denoted by red(w). For example, red(2151159858) = 1020024323, and we see that for every w, asc(w) = asc(red(w)). We now define a pattern to be any word which is its own reduction; for instance w = 01259 is not a pattern, while p = 0210 is a pattern. We then say that the word w contains the pattern p = p_{1}p_{2} ⋯ p_{k} if there exist 1 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ n such that red(w_{i_{1}}w_{i_{2}} ⋯ w_{i_{k}}) = p, and otherwise we say that w avoids p. Considering the word u = \underline{5}579\underline{0}2\underline{4}, u contains the pattern p = 201, which may be realized by the underlined letters of u (and by many other subwords as well), while the pattern q = 210 is avoided by u, as indeed there is no 3-letter subsequence of u in which the letters appear in decreasing order. A special type of pattern that we will use in this section is a restricted growth function, or RGF, which is any pattern in which the first occurrence of the letter k must be preceded by the letter k − 1 for every k ≥ 1, and hence, the first occurrence of k must actually be preceded by all of 0, 1, …, k − 1. For example, p = 0012332041 is an RGF, while q = 210 is not. Finally, we define an ascent sequence to be a word w = w_{1}w_{2} ⋯ w_{n} such that

(1) w_{1} = 0, and

(2) for 1 < i ≤ n, w_{i} ≤ asc(w_{1} ⋯ w_{i−1}) + 1.

For example, 012345 and 012000 are both ascent sequences, whereas w = 001162 is not, since 6 = w_{5} > asc(w_{1}w_{2}w_{3}w_{4})+1 = asc(0011)+1 = 2. Bousquet-Mélou et al. [4] were the first to define ascent sequences. Subsequently, Duncan and Steingrímsson [5] were the first to study pattern avoidance in ascent sequences, specifically considering how many ascent sequences of length n avoid various given patterns. A more recent paper by Baxter and Pudwell [3] asked how many ascent sequences of length n simultaneously avoid a given collection of patterns. To this end, let us define A_{P}(n) to be the set of ascent sequences of length n that avoid the collection of patterns P, where P may contain only a single pattern. For example, there are 15 ascent sequences of length 4:

0000, 0001, 0010, 0100, 0011, 0101, 0110, 0111, 0012, 0102, 0112, 0120, 0121, 0122, 0123.

By inspection, A_{{001,210}}(4) = {0000, 0100, 0110, 0111, 0120, 0121, 0122, 0123}. If we further restrict the elements of A_{{001,210}}(n) by defining A_{{001,210}}(n, k) to be the set of all w ∈ A_{{001,210}}(n) where asc(w) = k, we have the following:

A_{{001,210}}(4, 0) = {0000},
A_{{001,210}}(4, 1) = {0100, 0110, 0111},
A_{{001,210}}(4, 2) = {0120, 0121, 0122},
A_{{001,210}}(4, 3) = {0123},
A_{{001,210}}(4, 4) = ∅.

From the above example, we can conjecture and prove a nice form for words in A_{{001,210}}(n, k).

Lemma 16. For n, k ∈ ℤ with 0 ≤ k ≤ n, all w ∈ A_{{001,210}}(n, k) have the form

01 ⋯ k^{n−k} or 01 ⋯ k^{y}x^{n−k−y},

where 1 ≤ y < n − k and 0 ≤ x < k.

Proof. Let w = w_{1} ⋯ w_{n} ∈ A_{{001,210}}(n, k) and define M to be the largest letter in w. Since our statement is trivially true when k = 0, we may consider when k > 0 and, therefore, there are at least 2 distinct letters in w. Since 001 is a subpattern of 01012 and w avoids 001, Lemma 2.4 of Duncan and Steingrímsson [5] gives that w is an RGF. So, 0, 1, …, M must all appear in w and their first occurrences must appear in this order. Suppose that a < M occurs more than once before M, then we would have the subsequence aaM which forms a 001 pattern. Therefore, w = 01 ⋯ (M − 1)Mw′ for some word w′. Suppose that w′ contains letters a, b with M > a > b. If a occurs first in w′, then we have the subsequence Mab which forms a 210 pattern. If b occurs first in w′, then, since b must occur in 01 ⋯ (M − 1)M, we have the subsequence bba which forms a 001 pattern. Thus, w′ can contain at most one letter strictly less than M which implies that w′ must be weakly decreasing. Therefore, w′ has no ascents, which gives k = asc(w) = asc(01 ⋯ Mw′) = M. So, we have that w = 01 ⋯ k^{n−k} if no letter other than k appears in w′, and otherwise w = 01 ⋯ k^{y}x^{n−k−y}, where x is the letter strictly less than k which occurs in w′.

We are now in a position to prove that A_{{001,210}}(n + 1, k) is counted by R_{n,k} by constructing a bijection between A_{{001,210}}(n + 1, k) and B_{k}(n).

Theorem 17. For n, k ∈ ℤ, we have

|A_{{001,210}}(n + 1, k)| = R_{n,k}.

Proof. When n, k < 0, we have that A_{{001,210}}(n + 1, k) = ∅, so |A_{{001,210}}(n + 1, k)| = 0 = R_{n,k} in such cases. Also, since a word of length n + 1 can have at most n ascents, A_{{001,210}}(n + 1, k) = ∅ when k > n, so |A_{{001,210}}(n + 1, k)| = 0 = R_{n,k} in such cases. Now assume that 0 ≤ k ≤ n. Define f: B_{k}(n) → A_{{001,210}}(n + 1, k) by

f(1^{k}0^{n−k}) = 01 ⋯ k^{n+1−k} and f(1^{k−x}0^{y}1^{x}0^{n−k−y}) = 01 ⋯ k^{y}(k − x)^{n+1−k−y}

where 1 ≤ x ≤ k and 1 ≤ y ≤ n − k. By Lemma 16, all elements of A_{{001,210}}(n + 1, k) have such a form. This map is invertible since we only need x, y to reconstruct the original binary word, and x, y can be recovered from the image. Therefore, f is a bijection, yielding the desired result.

With this bijection, all proofs of identities in Section 3 can be translated into the language of ascent sequences with some effort. For example, a proof of Theorem 8 using ascent sequences is given in Proposition 9 of Baxter and Pudwell [3].

5 A generalization

We return briefly to our binary word interpretation of R_{n,k} to offer a natural generalization. We have shown that R_{n,k} counts binary words with length n, exactly k 1’s, and at most 1 ascent, but the choice to only count such binary words with at most 1 ascent is (more or less) arbitrary. So, in this section, we consider a generalization where we allow for at most j ascents. Let B_{k}^{(j)}(n) be the set of all binary words of length n with exactly k 1’s and at most j ascents, and set R_{n,k}^{(j)} = |B_{k}^{(j)}(n)| and B^{(j)}(n) = ⋃_{k} B_{k}^{(j)}(n). An equivalent generalization was discovered independently in a recent paper by Gregory et al. [6], where they discuss the numbers they refer to |\binom{n}{k}_{j}|, which are exactly what we call R_{n,k}^{(j)}. In that paper the authors gave a different combinatorial interpretation for the generalized rascal numbers— namely, they count k-element subsets of {1, 2, …, n} whose intersection with {1, 2, …, n−k} contains at most j elements—and they independently proved some of our following results, which we prove using our binary word interpretation. That said, Theorem 20 is not given in the Gregory paper, and indeed, Theorem 20 proves Conjecture 7.5 from that paper. For completeness, Theorem 24 provides a bijection between the binary strings counted by R_{n,k}^{(j)}

and the restricted subsets counted by |\binom{n}{k}_{j}|.

With our generalization, it is natural to ask how (or if) our previous results apply to this generalization. To begin, our previous use of a quadratic formula no longer holds for proving unimodality, so a more computational proof would be needed to show this fact, and Gregory et al. [6] gave such a proof; on the other hand, these numbers are symmetric, and the proof is identical to the j = 1 case (see Theorem 2). Indeed, we expect that many of the identities in Section 3 can be generalized to hold for R_{n,k}^{(j)} as well, however, the proofs seem unlikely to differ greatly from the j = 1 case. As such, we leave it to the reader to explore them further. That said, there are a couple of results which do differ enough to warrant special mention. To wit, the next result yields a recurrence that is nearly identical to Equation (2), whose proof follows a similar idea to that in Theorem 4.

Theorem 18 (Generalized Fleron recurrence). Set R_{n,n}^{(j)} = R_{n,0}^{(j)} = 1 for n ≥ 0 and R_{n,k}^{(j)} = 0 when n, k < 0 or k > n. Also, R_{n,k}^{(0)} = 1 when 0 ≤ k ≤ n. Then for 2 ≤ n, 0 ≤ k ≤ n, and 1 ≤ j we have

R_{n,k}^{(j)} = R_{n−1,k}^{(j)} + R_{n−1,k−1}^{(j)} − R_{n−2,k−1}^{(j)} + R_{n−2,k−1}^{(j−1)}.

Proof. Every w ∈ B_{k}^{(j)}(n) either ends in a 0 or 1, and so define T (w) = w_{1} ⋯ w_{n−1} for every word w = w_{1} ⋯ w_{n}.

(1) If w ends in a 0 then T (w) ∈ B_{k}^{(j)}(n − 1). Since T is an invertible map when acting on words ending in 0, there are R_{n−1,k}^{(j)} such w.

(2) If w ends in a 1 then T (w) ∈ B_{k−1}^{(j)}(n − 1). Furthermore, T (w) either ends in a 0 and has at most j − 1 ascents or still ends in a 1 with at most j ascents. So the only words in B_{k−1}^{(j)}(n − 1) which cannot be mapped to by T acting on words ending in a 1 are those which end in a 0 and have exactly j ascents. There are R_{n−2,k−1}^{(j)} such words in B_{k−1}^{(j)}(n − 1) which end in 0, by the same argument in part (1), of which exactly R_{n−2,k−1}^{(j−1)} have fewer than j ascents. Thus, there are R_{n−2,k−1}^{(j)} − R_{n−2,k−1}^{(j−1)} elements of B_{k−1}^{(j)}(n − 1) which end in a 0 and have j ascents. Therefore, there are exactly

R_{n−1,k−1}^{(j)} − (R_{n−2,k−1}^{(j)} − R_{n−2,k−1}^{(j−1)})

such w.

Summing the two cases gives our desired recurrence.

And we also have a closed form for R_{n,k}^{(j)} in terms of binomial coefficients.

Theorem 19. For n, k, j ∈ ℤ with n, k, j ≥ 0, we have

R_{n,k}^{(j)} = ∑_{r=0}^{j} \binom{k}{i}\binom{n − k}{i}.

Proof. Let w ∈ B_{k}^{(j)}(n) such that asc(w) = r. Then w = 1^{x_{0}}0^{y_{1}}1^{x_{1}} ⋯ 0^{y_{r}}1^{x_{r}}0^{y_{0}} with

∑_{i=0}^{r} x_{i} = k and ∑_{i=0}^{r} y_{i} = n − k,

where x_{0}, y_{0} ≥ 0 and x_{i}, y_{i} > 0 for i > 0. Solutions to the above equations are in one-to-one correspondence with positive integral solutions to

∑_{i=0}^{r} x′_{i} = k + 1 and ∑_{i=0}^{r} y′_{i} = n − k + 1,

respectively. Thus, there are

\binom{k + 1 − 1}{i + 1 − 1} = \binom{k}{i}

solutions to left equation and

\binom{n − k + 1 − 1}{i + 1 − 1} = \binom{n − k}{i}

solutions to the right equation. Thus, there are \binom{k}{i}\binom{n−k}{i} such w. Summing over all values of r we get our desired result.

Finally, we give a formula to compute the row sums of generalized rascal triangles, and we note that this theorem also proves Conjecture 7.5 from Gregory et al. [6], which we give as a corollary.

Theorem 20 (Generalized row sum). For n, j ∈ ℤ with n, j ≥ 0, we have

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

Proof. By definition, the left-hand side counts B^{(j)}(n). We can also count B^{(j)}(n) by beginning with some S ⊆ [n] where |S| ≤ 2j + 1. Next, letting w = w_{1} ⋯ w_{n}, place a divider before the w_{i} for each i ∈ S, and label each divided section from left to right with 0, 1, …, |S| in increasing order. For each section, if it is labeled with an even number then set all w_{i} in the section equal to 1’s, and if it is labeled with an odd number then set all w_{i} in the section to 0’s. This process can be inverted for a w = w_{1} ⋯ w_{n} ∈ B^{(j)}(n) by taking Des(w)∪Asc(w) and unioning the singleton set \{n\} if w_{1} = 0. For a fixed 0 ≤ k ≤ 2j + 1, there are \binom{n}{k} such S with |S| = k, so by summing over all k we get |B^{(j)}(n)|, thus achieving our desired result.

Corollary 21 (Conjecture 7.5 of Gregory et al. [6]). For j ∈ ℤ with j ≥ 0,

∑_{k=0}^{4j+3} R_{4j+3,k}^{(j)} = 2^{4j+2}.

Proof. By Theorem 20, we have

∑_{k=0}^{4j+3} R_{4j+3,k}^{(j)} = ∑_{k=0}^{2j+1} \binom{4j + 3}{k}

which is the sum of the first half of the (4j +3)-rd row of Pascal’s triangle. Due to symmetry of binomial coefficients, this sum is half that of the whole row sum, which is 2^{4j+3}.

We also use Theorem 20 to provide a slightly more direct proof of the following result.

Corollary 22 (Theorem 7.3 of Gregory et al. [6]). For n, j ∈ ℤ with n, j ≥ 0,

Δ^{2j+1} (∑_{k=0}^{n} R_{n,k}^{(j)}) = 1

where Δ is the forward difference operator with respect to n, i.e., for the sequence (a_{n})_{n≥0}, Δa_{n} = a_{n+1} − a_{n}.

Proof. By Theorem 20, we have

Δ^{2j+1} (∑_{k=0}^{n} R_{n,k}^{(j)}) = Δ^{2j+1} (∑_{k=0}^{2j+1} \binom{n}{k})

= ∑_{k=0}^{2j+1} Δ^{2j+1}\binom{n}{k},

where the last equality follows by linearity of Δ. It is a well-known result that

Δ\binom{n}{k} = \binom{n}{k − 1},

and so our sum becomes

Δ^{2j+1} (∑_{k=0}^{n} R_{n,k}^{(j)}) = ∑_{k=0}^{2j+1} \binom{n}{k − (2j + 1)}

= \binom{n}{0} = 1.

Theorem 23. For n, j ∈ ℤ with n, j ≥ 0, we have

∑_{k=0}^{n}(−1)^{k}R_{n,k}^{(j)} = \begin{cases}0, & if n ≡ 1 (mod 2); \\ (−1)^{j}\binom{n/2−1}{j}, & if n ≡ 0 (mod 2). \end{cases}

with the convention \binom{−1}{j} = (−1)^{j}. Proof. To prove this result, we will repeatedly use the involution principle to pair off words of opposite sign until the remaining words have a nice form which we can easily count. First, define wt : B^{(j)}(n) → B^{(j)}(n) by wt(w) = (−1)^{#(1’s in w)}. Next, define I_{0}: B^{(j)}(n) → B^{(j)}(n) as follows: if w = 1^{x_{0}}w′0^{y_{0}} where w′ does not begin in a 1 or end in a 0, then

(1) I_{0}(w) = 1^{x_{0}−1}w′0^{y_{0}+1} whenever 2 ∤ x_{0},

(2) I_{0}(w) = 1^{x_{0}+1}w′0^{y_{0}−1} whenever 2 | x_{0} and y_{0} > 0, and

(3) I_{0}(w) = w whenever 2 | x_{0} and y_{0} = 0. The function I_{0} is a weight-preserving, sign-reversing involution; further, w = 1^{x_{0}}w′0^{y_{0}} ∈ fix(I_{0}) implies that 2 | x_{0} and y_{0} = 0, so w = 1^{2x′_{0}}w′. Now, for d > 0, define I_{d}: fix(I_{d−1}) → fix(I_{d−1}) as follows: if

w = 1^{2x_{0}} ( ∏_{i=1}^{asc(w)} 0^{y_{i}}1^{x_{i}} ) ∈ fix(I_{d−1}),

then

(1) I_{d}(w) = 1^{2x_{0}} (∏_{i=1}^{d−1} 0^{y_{i}}1^{x_{i}}) 0^{y_{d}+1}1^{x_{d}−1} ( ∏_{i=d+1}^{asc(w)} 0^{y_{i}}1^{x_{i}} ) whenever 2 | x_{d},

(2) I_{d}(w) = 1^{2x_{0}} (∏_{i=1}^{d−1} 0^{y_{i}}1^{x_{i}}) 0^{y_{d}−1}1^{x_{d}+1} ( ∏_{i=d+1}^{asc(w)} 0^{y_{i}}1^{x_{i}} ) whenever 2 ∤ x_{d} and y_{d} > 1, and

(3) I_{d}(w) = w whenever 2 ∤ x_{d} and y_{d} = 1 or asc(w) < d.

Here, I_{d} is also a weight-preserving, sign-reversing involution for all 1 ≤ d ≤ j. Furthermore, for w ∈ fix(I_{j}), we must have that 2 ∤ x_{d} and y_{d} = 1 for all 1 ≤ d ≤ j, that is,

w = 1^{2z_{0}} ( ∏_{i=1}^{asc(w)} 0^{1}1^{2z_{i}+1})

with z_{i} ≥ 0 and

2z_{0} + ∑_{i=1}^{asc(w)}(2z_{i} + 1) + asc(w) = 2 ( ∑_{i=0}^{asc(w)} z_{i} + asc(w)) = n.

If 2 ∤ n, then the above equation has no integer solutions and therefore there cannot exist a w ∈ fix(I_{j}) so our sum is 0 as desired.

Now assume that 2 | n. Then picking the z_{i}’s in the above equation uniquely determines w, so we simply need to count solutions. Since solutions to the above are in 1-1 correspondence with solutions to

∑_{i=0}^{asc(w)} z′_{i} = n/2 + 1

with z′_{i} > 0, there are \binom{n/2}{asc(w)} solutions. Also, as 2 | n, wt(w) = (−1)^{n−asc(w)} = (−1)^{asc(w)}. Thus, we have

∑_{k=0}^{n}(−1)^{k}R_{n,k}^{(j)} = ∑_{ℓ=0}^{j}(−1)^{ℓ}\binom{n/2}{ℓ}

= (−1)^{j}\binom{n/2 − 1}{j},

as desired. Note that the j = 1 case yields Theorem 13.

We conclude with a bijection between the binary strings counted by R_{n,k}^{(j)} and the restricted subsets in \binom{n}{k}_{j}.

Theorem 24. For n, k, j ∈ ℤ with n, k, j ≥ 0, we have R_{n,k}^{(j)} = |\binom{n}{k}_{j}|.

Proof. Let S ∈ \binom{n}{k}_{j}, and then set S_{x} = S ∩ \{n − k + 1, …, n\} and S_{y} = S ∩ \{1, 2, …, n − k\}, so that S = S_{x} ∪ S_{y} and S_{x} ∩ S_{y} = ∅. Then we can write S_{y} as

S_{y} = {y_{1}, y_{1} + y_{2}, …, y_{1} + y_{2} + ⋯ + y_{m}}

where y_{i} > 0 and 0 ≤ m ≤ j. Define h: ℤ → ℤ by a ↦ a − (n − k) which is invertible and therefore a bijection. Then since n − k < x ≤ n for every x ∈ S_{x}, we see that h(S_{x}) ⊂ {1, 2, …, k}. Accordingly, we write h(S_{x}) as

h(S_{x}) = {1, 2, …, k} \ {x_{1}, x_{1} + x_{2}, …, x_{1} + x_{2} + ⋯ + x_{m}}

with x_{i} > 0. Now, define f: \binom{n}{k}_{j} → B_{k}^{(j)}(n) by

f(S) = f(S_{x} ∪ S_{y}) = 1^{k−X} (∏_{i=1}^{m} 0^{y_{i}}1^{x_{i}}) 0^{n−k−Y} ,

where X = max S_{x} and Y = max S_{y}. Given w ∈ B_{k}^{(j)}(n), we can determine its corresponding x_{i} and y_{i} values, which in turn gives us S_{y} and h(S_{x}). Since h is invertible, we know S_{x} as well, which gives us the S ∈ \binom{n}{k}_{j} that is mapped to w by f. Therefore, f is invertible, completing the proof.

As a closing observation, we see that since Theorem 18 gives a recurrence that is so similar to Fleron’s recurrence, it seems natural that the generalized Rascal numbers should satisfy a recurrence similar to Equation (3), proven in Theorem 5.

Conjecture 25. For 2 ≤ n, 0 ≤ k ≤ n, and 1 ≤ j,

R_{n,k}^{(j)} = \frac{R_{n−1,k}^{(j)}R_{n−1,k−1}^{(j)} + E(n, k, j)}{R_{n−2,k−1}^{(j)}}

for some E: ℤ^{3} → {0, 1, 2, …}.

We have not been able to find a closed form for E, but, through numerical tests, we believe one to exist.

References

[1] A. Anggoro, E. Liu, and A. Tulloch, The rascal triangle, College Math. J. 41 (2010), 393–395.

[2] J. M. Ashfaque, The rascal numbers, preprint, 2019, https://www.researchgate.net/

   publication/335686803_The_rascal_Numbers.

[3] A. Baxter and L. Pudwell, Ascent sequences avoiding pairs of patterns, Electron. J. Combin. 22 (2015), Paper no. 1.58.

[4] M. Bousquet-Mélou, A. Claesson, M. Dukes, and S. Kitaev, (2 + 2)-free posets, ascent sequences and pattern avoiding permutations, J. Combin. Theory Ser. A 117 (2010), 884–909.

[5] P. Duncan and E. Steingrímsson, Pattern avoidance in ascent sequences, Electron. J. Combin. 18 (2011), Paper no. 2.26.

[6] J. Gregory, B. Kronholm, and J. White, Iterated rascal triangles, Aequationes Math.

   (2023), https://doi.org/10.1007/s00010-023-00987-6.

[7] J. F. Fleron, Fresh perspective bring discoveries, Math Horiz. 24 (2017), 15.

[8] P. K. Hotchkiss, Generalized rascal triangles, J. Integer Sequences 23 (2020), Article 20.7.4.

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

2020 Mathematics Subject Classification: Primary 05A19; Secondary 05A05. Keywords: rascal number, binary word, ascent, ascent sequence, involution principle.

(Concerned with sequences \underline{A051744} and \underline{A077028}.)

Received May 23 2024; revised versions received June 13 2024; November 5 2024; November 11 2024. Published in Journal of Integer Sequences, November 12 2024.

Return to Journal of Integer Sequences home page.