{'fraction_non_alphanumeric': 0.07523893114881998, 'fraction_numerical': 0.0248683440608543, 'mean_word_length': 3.502524698133919, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Counting odd numbers in truncations of Pascal's triangle

A"truncation"of Pascal's triangle is a triangular array of numbers that satisfies the usual Pascal recurrence but with a boundary condition that declares some terminal set of numbers along each row of the array to be zero. Presented here is a family of natural truncations of Pascal's triangle that generalize a kind of Catalan triangle. The numbers in each array are realized as differences of binomial coefficients, as counts of certain lattice paths and tableaux, and as entries of representing matrices for certain linear transformations of polynomial spaces. Lucas's theorem is applied to determine precisely those truncations for which the number of odd entries on each row is a power of two.

§1 Introduction. Observe that the following conditions (i), (ii), and (iii) uniquely determine an integer-valued function A on Z×Z: (i) A(0, 0) = 1, (ii) A(n, k) = 0 if n < 0, k < 0, or k > ⌊n/2⌋, and (iii) A(n, k) = A(n − 1, k − 1) + A(n − 1, k) for all other integer pairs (n, k) when n > 0. The output numbers of interest are those within the triangular array (A(n, k)) indexed by integer pairs (n, k) for which 0 ≤ k ≤ n. When we display this array, we get a kind of "truncation" of Pascal's triangle. Here are the first ten rows: Note the appearance of the famous Catalan numbers in the two rightmost nonzero "columns" of the array and as sums of the numbers on northwest-to-southeast diagonals. The nonzero entries of this array are called "ballot numbers," as they count the number of ways one candidate can defeat another candidate in a two-person election, under certain constraints. For further explication of this and other well-known phenomena related to this Catalan array, see for example [A] and references therein.
In this paper we present a generalization of this array by simply and naturally varying the "boundary condition" (ii) above. We will have one such array for each positive integer t, where t identifies the first row of the array that no longer fully agrees with Pascal's triangle, i.e. the first "truncated" row. So, for example, the t = 1 array is the Catalan array depicted above. The nonzero numbers in these more general triangular arrays are shown to be differences of binomial coefficients as well as counts of certain lattice paths. The fourth author, in consultation with the first author, studied these arrays in an undergraduate student honors thesis [Schn] concerning differential operators on function spaces. A version of the motivating problem of that thesis is presented below, and in Theorem 3.4 it is shown how the numbers in our truncated Pascal arrays are coefficients for certain polynomials which arise in the study of differential operators. However, in [Reu], Reuveni independently presented the so-called "Catalan's trapezoids," which are the same as our truncated Pascal's triangles but indexed and formatted somewhat differently. In [RHEY], these trapezoids are applied in a probabilistic analysis of certain lattice-gas flow models.
We close this introduction with some descriptive comments about the content of the paper.
We think these Pascal-like arrays are inherently pretty and provide for an excellent enumerative example or exercise: We have a recurrence, an explicit formula, combinatorial interpretations, and a polynomial algebra context for these numbers, as summarized in Theorem 3.4. This would seem to place us well within an enumeratively salubrious environment as envisioned by Stanley in Chapter 1 of his classic text [St]. Our main result -Theorem 4.3 -is a (modest) enumerative application of these arrays that generalizes the well-known problem of counting odd numbers in the rows of Pascal's triangle; this new theorem, which appears in [Geo], was obtained by the third author in consultation with the first and second authors. For Pascal's triangle, solutions to this odd-counting problem and other related problems are entertainingly recounted in [Gr]. Our work in this paper leaves open the possibility of generalizing other such problems from Pascal's triangle to the truncations of Pascal's triangle presented here. §2 A family of truncations of Pascal's triangle. For the rest of the paper, t denotes a fixed positive integer, which we think of informally as designating the first truncated row of the associated Pascal-like integer array. Consider a function a t : Z × Z −→ Z satisfying (i) a t (0, 0) = 1, (ii) a t (n, k) = 0 if n < 0, k < 0, or k > min ⌊ n−1+t 2 ⌋, n , and (iii) a t (n, k) = a t (n−1, k−1)+a t (n−1, k) for all other integer pairs (n, k). Figure 2.1 displays the first ten rows of the array (a 4 (n, k)) when viewed as a truncation of Pascal's triangle. We call an array (a t (n, k)) 0≤k≤n<∞ a truncated Pascal's triangle. Of course, the Catalan array (A(n, k)) of §1 is just the t = 1 version of (a t (n, k)). In the next section we offer various interpretations of and contexts for the numbers in these truncated Pascal's triangles. 1  1  1  1  2  1  1  3  3  1  1  4  6  4  0  1  5  10  10  4  0  1  6  15  20  14  0  0  1  7  21  35  34  14  0  0  1  8  28  56  69  48  0  0  0  1  9  36  84  125  117  48  The truncated Pascal's triangle (a 4 (n, k)). §3 Algebraic-combinatorial aspects of truncated Pascal's triangles. We aim to give several different descriptions of the numbers appearing in truncated Pascal's triangles, which will lead directly to Theorem 3.4. Throughout this section, n and k are integers. Declare that with the usual understanding that the binomial coefficient p q is zero unless 0 ≤ q ≤ p. Next, we count lattice paths. An NE-path from (x 1 , y 1 ) to (x 2 , y 2 ) in the plane will be a continuous path starting at (x 1 , y 1 ), ending at (x 2 , y 2 ), and consisting of a finite number of unit steps in the north and east directions only. Say an NE-path from (0, 0) to (k, n − k) is an (n, k)-NE-path, and call such a path t-admissible if it does not intersect the line y = x − t; in such a case we say the path stays weakly above y = x − t + 1. For example, when t = 4 and (n, k) = (7, 5), then (k, n − k) = (5, 2). As we can see in the pictures below, the number of 4-admissible (7, 5)-NE-paths is 14, i.e. there are fourteen NE-paths from (0, 0) to (5, 2) that stay weakly above y = x − 3. For now, one can ignore the numbers assigned to the horizontal steps of each lattice path, although the pattern in which they are assigned should be evident. This count agrees with the (n, k) = (7, 5) entry of the example array (a 4 (n, k)) depicted in §2 above. Moreover, b 4 (7, 5) = 7 5 − 7 1 = 14. In general, we set c t (n, k) := |{t-admissible (n, k)-NE-paths}|. (2) For integers x 1 , y 1 , x 2 , and y 2 , the number of all NE-paths from (x 1 , y 1 ) to (x 2 , y 2 ) is easily seen to be . Consider for the moment those NE-paths from (0, 0) to (k, n − k) which cross the line y = x − t + 1 and therefore cross or touch the line y = x − t. At the first point of intersection with y = x − t, reflect the initial part of the path across that line to obtain an NE-path from (t, −t) to (k, n − k). This procedure can be reversed and therefore shows that the set of NE-paths from (0, 0) to (k, n − k) which cross the line y = x − t − 1 is in one-to-one correspondence with the set of all NE-paths from (t, −t) to (k, n − k). (This is an instance of the famous reflection principle of André.) That is, the number of NE-paths from (0, 0) to (k, n − k) that cross the line

This shows:
Lemma 3.1 For all integers n and k, we have b t (n, k) = c t (n, k).
For more about the well-known observation recorded above as Lemma 3.1, see Chapter 1 of [M].
For a recent and readable survey of lattice path enumeration with references to many closely related results, see [H].
In algebraic combinatorics, objects called "tableaux" are often used to index bases for representations of algebraic structures such as groups or Lie algebras. For tableaux relating to representations of symmetric groups, see for instance [Sa]; for many examples arising in Lie theory, see [P2]. Tableaux generally take the form of an array of boxes of some specified shape filled with integer entries subject to certain rules. Next, we offer a re-interpretation of t-admissible NE-paths as columnar tableaux. But before we do so, we very briefly remark on a connection between the Catalan array of §1 and the representation theory of symplectic Lie groups.
The Lie theoretic notions of the present paragraph are mentioned in order to provide some further context for the kinds of objects we are considering, but readers unfamiliar with Lie representation theory can safely skip to the next paragraph. Taking n ≥ 1, the number A(2n+1, k) = a 1 (2n+1, k) is the dimension of the kth fundamental representation of the symplectic group Sp(2n, C), when 1 ≤ k ≤ n. The number A(2n, k) = a 1 (2n, k) is the dimension of a certain indecomposable representation (that might reasonably be called the "kth fundamental representation") of the nonreductive odd symplectic group Sp(2n − 1, C); in the language of [P1], this is the Sp(2n − 1, C)module corresponding to a partition of k with k parts. In fact, certain columnar tableaux provide a concrete connection between a number of the Catalan array (say, A(2n, k) or A(2n + 1, k)) and the dimension count of the associated symplectic group representation (say, the kth fundamental representation of Sp(2n − 1, C) or Sp(2n, C)): On the one hand, the tableaux index a special basis for the representing space, but on the other hand the number of these tableaux can easily be realized as the associated ballot number from the Catalan array.
Lemma 3.2 For all integers n and k, we have c t (n, k) = c ′ t (n, k). Proof. Let P t (n, k) be the set of t-admissible (n, k)-NE-paths, and let T t (n, k) be the set of t-admissible (n, k)-columnar tableaux. In this proof, we identify an (n, k)-NE-path s with the consisting of the k successive endpoints of the horizontal, or easterly, steps of the path. For example, for the first 4-admissible (7, 5)-NE-path depicted above, the sequence of horizontal endpoints is (1, 0), (2, 0), (3, 0), (4, 1), (5, 2) .
Since x k (s) = k and y k (s) ≤ n − k, then T k ≤ n. So T is an (n, k)-columnar tableau. Now suppose t − 1 < k, and let j ∈ {1, 2, . . . , k − t + 1}. Since s is t-admissible, then we have j = Thus T is a t-admissible (n, k)-columnar tableau. We can therefore regard φ : P t (n, k) −→ T t (n, k) as a well-defined function. Now suppose that T = (T 1 , . . . , T k ) is a t-admissible (n, k)-columnar tableau. Declare that := ψ(T ). To prove that s is an (n, k)-NE-path, it suffices to check that 0 ≤ y 1 ≤ y 2 ≤ · · · ≤ y k ≤ n − k. Since 1 ≤ T 1 , then 0 ≤ T 1 − 1 = y 1 . When We can therefore regard ψ : T t (n, k) −→ P t (n, k) as a well-defined function. Clearly φ and ψ are inverses, so P t (n, k) and T t (n, k) are equinumerous, which is what we needed to show.
Finally, we consider another set of numbers d t (n, k) which arise as coefficients of certain polynomials or, from another viewpoint, as entries of representing matrices for certain linear transformations on polynomial vector spaces. It appears this can be viewed within the context of Rota's finite operator calculus (see [N]), but we use more direct and elementary reasoning here. To set things up, let {x j } j≥0 be the basis for the polynomial vector space R[x] (polynomials in the indeterminate x and with real coefficients) given by x j := x j /j!. Let S be the subspace of R[x] spanned by {x j } j≥1 .
The linear transformation D : S −→ R[x] will be the differential operator D(y) := y ′ + y ′′ . In fact, D is a vector space isomorphism. For any positive integer N , set D −N := (D −1 ) N .

It is easy to see by induction on N that for all positive integers
(For the basis step of the induction argument, check that D −1 (x t−1 ) = t−1 i=0 (−1) i x t−i .) This means that for any positive integer N we can write for some real numbers d t (i + N − 1, i). Declare d t (n, k) to be zero for any integer pair (n, k) such that for all N > 0 and 0 ≤ i ≤ t − 1 + N − 1, (n, k) = (i + N − 1, i), i.e. d t (n, k) = 0 if (n, k) does not index any term appearing in any of the sums shown in equation (4)   Now simply check inequalities to see that k ≥ 0, n ≥ 0, k ≤ n, and k ≤ ⌊ n−1+t 2 ⌋. For (iii), we apply D to each side of equation (4). First, On the other hand, where the latter is obtained by expanding and reindexing. Then by equating coefficients in the latter expression with coefficients for the expression obtained in equation (5), we see that d t (t − 1 + 2N − 2, t − 1 + N − 1) − d t (t − 1 + 2N − 3, t − 1 + 2N − 2) = 0 and that for all 0 ≤ i ≤ t − 1 + N − 2 we The latter formula actually becomes the former when i = t − 1 + N − 1, as d t (t − 1 + 2N − 3, t − 1 + N − 1) evaluates to zero. Therefore, for all N > 0 and 0 ≤ i ≤ t − 1 + N − 1. Now if (n, k) is an integer pair with n ≥ 0 and 0 ≤ k ≤ min ⌊ n−1+t 2 ⌋, n , then set i = k and N = n + 1 − k. As in the previous paragraph we can see that (i + N − 1, i) corresponds to a term from equation (4). Then from equation (6), we get − 1, k), as desired.
The preceding lemmas furnish the key steps in the proof of the main result of this section, whose value is not so much the novelty of the results (which are routine to enumeration experts) but rather the pleasantness and illustrative utility of the results taken together as an assemblage.
Theorem 3.4 For all integers n and k, we have Proof. The b t (n, k)'s are easily seen to satisfy the defining conditions (i), (ii), and (iii) which uniquely determine the a t (n, k)'s, so b t (n, k) = a t (n, k). The d t (n, k)'s satisfy these same conditions by Lemma 3.3, hence d t (n, k) = a t (n, k). And by Lemmas 3.1 and 3.2 we have b t (n, k) = c t (n, k) = c ′ t (n, k). §4 Counting odd numbers in truncations of Pascal's triangles. It is a well-known phenomenon that the number of odds on any given row of Pascal's triangle is a power of two. A classical proof of this fact utilizes Lucas's Theorem and is recapitulated in Corollary 4.2 below, cf. §8.4 of [BQ]. Before we proceed, we fix some notation. For a prime p and a nonnegative integer  From here on, we suppress the "p" superscripts and subscripts from the notation introduced above and fix p = 2 as our prime. So, for example, "d(n)" means d 2 (n), "l(n)" means l 2 (n), "D(n)" means D 2 (n), etc.
Corollary 4.2 Let n be a nonnegative integer. Then the number of odds on the n th row of Pascal's triangle is 2 d(n) .
Proof. Suppose 0 ≤ k ≤ n. Then by Lucas' Theorem, n k is odd if and only if n i = 1 whenever k i = 1. So, n k is odd if and only if D(k) ⊆ D(n). Of course, there are 2 |D(n)| = 2 d(n) choices for such subsets. Now we turn our attention to truncations of Pascal's triangle. Corollary 4.2 and the reasoning exhibited in its proof will be used in several of the lemmas that follow. These lemmas support the proof of the following theorem, which is the main result of this paper.
Theorem 4.3 The number of odds on each row of the Pascal triangle truncation (a t (n, k)) is a power of two if and only if t is a power of two. In this case, when n is a nonnegative integer, the number of odds on row n of the array is precisely 1 2 · 2 d(n+t) . The proof of Theorem 4.3 is at the end of this section and will be easily deduced from the lemmas we establish next.
Lemma 4.4 Suppose t is not a power of two. Then the number of odds on row t of the truncated Pascal's triangle (a t (n, k)) is an odd number greater than one and therefore not a power of two.
Lemma 4.6 Let n be a nonnegative integer. All entries on the n th row of Pascal's triangle are odd if and only if there is a nonnegative integer q such that n = 2 q − 1.
The following binomial coefficient identity is a version of Vandermonde's Identity, cf. Identity 132 of [BQ].  We are now ready to prove Theorem 4.3.
Proof of Theorem 4.3. Lemma 4.4 shows that if the number of odds on each row of the Pascal triangle truncation (a t (n, k)) is a power of two, then t must be a power of two. Conversely, let us now suppose that t = 2 q for some nonnegative integer q. We aim to demonstrate the following claim: When n is a nonnegative integer, the number of odds on row n of the array is precisely 1 2 · 2 d(n+t) . We begin by assuming n is odd. Write n = 2m + 1 for a nonnegative integer m. The last nonzero entry on row n occurs at position k = min t−1+n 2 , n = min 2 q +2m 2 , 2m + 1 . If q = 0, then 2 q +2m 2 = m, so k = m. Of course, we now have t = 2 0 = 1. By Lemma 4.8, the parity of entry a 1 (n, j) of the n th row of our array (where 0 ≤ j ≤ k = m) is the same as the parity of the binomial Since 2m+2 m+1 is even by Lemma 4.5, then the number of odds on the (n + 1) st row of Pascal's triangle is twice the number of odds amongst the entries entry n+1 j for 0 ≤ j ≤ k = m. Now, the number of odds on the (n + 1) st row of Pascal's triangle is 2 d(n+1) by Corollary 4.2. Therefore, the number of odds on the n th row of our truncated Pascal array is 1 2 · 2 d(n+1) , confirming our desired claim when q = 0.
Continuing with the assumption that n is odd, now assume that q > 0. Then 2 q +2m 2 = 2 q−1 +m.
If 2 q−1 + m ≥ 2m + 1 (and hence 2 q > 2m + 1), then k = 2m + 1, so the entries of the n th row of our array coincide with the entries of the n th row of Pascal's triangle. This shared number of odds is therefore 2 d(n) , by Corollary 4.2. But d(n + t) = d(n + 2 q ) = d(n) + 1 since 2 q > 2m + 1 = n. Then the number of odds on the n th row of our array is 2 d(n) = 1 2 ·2 d(n)+1 = 1 2 ·2 d(n+t) , again confirming our claim. So now consider the case that 2 q−1 +m < 2m+1. The n th row entry a t (n, j) of our truncated Pascal array (where 0 ≤ j ≤ k) has the same parity as the entry n+t j of Pascal's triangle, by Lemma 4.8. Now, k = 2 q−1 +m while n+t = 2 q +2m+2 = 2(2 q−1 +m+1). Since n+t 2 q−1 +m+1 = 2(2 q−1 +m+1) is even by Lemma 4.5, then the number of odds on the (n + t) th row of Pascal's triangle is twice the number of odds amongst the entries entry n+t j for 0 ≤ j ≤ k = 2 q−1 + m. So, the number of odds on the n th row of our truncated Pascal array is 1 2 · 2 d(n+t) , completing the confirmation of our claim when n is odd.
Next, assume n is even, and write n = 2m for some nonnegative integer m. As before, the last nonzero entry on row n occurs at position k = min t−1+n 2 , n = min 2 q −1+2m 2 , 2m . Say Keeping the hypothesis that n is even, now assume that q > 0. Then 2 q −1+2m 2 = 2 q−1 + m − 1.
If 2 q−1 + m − 1 ≥ 2m (and hence 2 q > 2m), then k = 2m, so the entries of the n th row of our array coincide with the entries of the n th row of Pascal's triangle. This shared number of odds is therefore 2 d(n) , by Corollary 4.2. But d(n + t) = d(n + 2 q ) = d(n) + 1 since 2 q > 2m = n. Then the number of odds on the n th row of our array is 2 d(n) = 1 2 · 2 d(n)+1 = 1 2 · 2 d(n+t) , again confirming our claim. So now consider the case that 2 q−1 + m − 1 < 2m. The n th row entry a t (n, j) of our truncated Pascal array (where 0 ≤ j ≤ k) has the same parity as the entry n+t j of Pascal's triangle, by Lemma 4.8. Now, k = 2 q−1 + m − 1 while n + t = 2 q + 2m = 2(2 q−1 + m). The central coefficient 2(2 q−1 +m) 2 q−1 +m of the (n + t) th row of Pascal's triangle is even by Lemma 4.5, so this entry does not contribute to the tally of odd numbers on this row. Therefore the number of odds in row n of our array is exactly one-half the number of odds on the (n + t) th row of Pascal's triangle, which is 1 2 · 2 d(n+t) . This completes the confirmation of our claim when n is odd. §5 Some thoughts on extending this work. Given that our proofs employ elementary techniques, perhaps these proofs can be modified to obtain more general results (which is, indeed, a crucial function of rigorous proof in mathematics). One possible direction is to consider patterns in truncated Pascal arrays modulo other primes or prime powers, cf. [Gr]. Also, when t = 1, the truncated Pascal array is just the Catalan triangle. In this case, as mentioned in §3, the nonzero numbers in any given row are known to be dimensions of certain fundamental representations of the associated symplectic Lie group. With t = 1, the t-admissible (n, k)-columnar tableaux we presented in §3 coincide (after a simple change in the alphabet of tableaux entries) with columnar symplectic tableaux of [P2]. It might be interesting to consider what similar algebraic contexts might be found for t-admissible (n, k)-columnar tableaux when t > 1.