Counting odd numbers in truncations of Pascal's triangle

Robert G. Donnelly, Molly W. Dunkum, Courtney George, Stefan SchnakearXiv 2018 · DOI · arXiv

Abstract

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.

Introduction

In the classic Pascal’s triangle, a well-known result derived from Lucas’s Theorem states that the number of odd entries in any given row is always a power of two. However, mathematicians frequently work with variations of this triangle, such as the Catalan triangle or "ballot numbers," which are used to count specific types of lattice paths or valid voting sequences.

A truncated Pascal's triangle (t=2) where certain entries are forced to zero, generalizing the Catalan triangle.

These variations are essentially "truncations" where certain entries are forced to be zero. While the parity (odd/even) patterns of the full Pascal’s triangle are famous, this research bridges a gap by defining a generalized family of truncations indexed by a parameter $t$ and establishing a clear rule for when their rows maintain the "power of two" property for odd numbers.

Methodology

The study employs a combination of classical combinatorics and linear algebra to define and analyze these truncated arrays $a_t(n, k)$:

  • Recurrence Relations: The arrays follow the standard Pascal recurrence $A(n, k) = A(n-1, k-1) + A(n-1, k)$ but incorporate a specific boundary condition based on $t$.
  • The Reflection Principle: To prove that these numbers represent specific lattice paths (paths that stay above a certain line), the authors use André’s reflection principle—a geometric technique that creates a bijection between "bad" paths and paths starting from a reflected point.
  • Differential Operators: These numbers also arise as coefficients when applying the inverse of a specific differential operator ($D(y) = y' + y''$) to polynomial spaces.
  • Lucas’s Theorem: This is the primary tool for parity analysis, allowing the determination of binomial coefficient congruence modulo 2 by examining the binary digits of the indices.
Lattice paths representing the combinatorial interpretation of the truncated numbers, staying above a boundary line.

Key Insights and Results

The research successfully generalizes the Catalan triangle (where $t=1$) to any positive integer $t$. This parameter represents the first row where the array deviates from the standard Pascal's triangle. The study demonstrates that these truncated numbers are simultaneously differences of binomial coefficients, counts of "t-admissible" lattice paths, and counts of specific "columnar tableaux."

The Power of Two Rule: The most significant finding is that the "power of two" behavior for odd entries is fragile. It persists across all rows if and only if the truncation parameter $t$ is itself a power of two ($1, 2, 4, 8, \dots$). Specifically:

  • Theorem 3.4: Confirms the equivalence of the recurrence-defined array and the binomial difference formula: $a_t(n, k) = \binom{n}{k} - \binom{n}{k-t}$.
  • Theorem 4.3: Establishes that the number of odd entries in each row is a power of two if and only if $t = 2^q$.
  • Quantitative Parity: If $t$ is a power of two, the number of odd entries in row $n$ is exactly $\frac{1}{2} \cdot 2^{d(n+t)}$, where $d(m)$ is the number of ones in the binary representation of $m$.

Conclusion and Future Work

This work provides a robust framework for understanding parity in truncated Pascal's triangles, yet it opens several avenues for future research. The current focus is almost exclusively on parity (modulo 2); future studies could explore patterns modulo other primes. Furthermore, while the $t=1$ case has deep roots in the representation theory of symplectic Lie groups, the broader algebraic context for $t > 1$ remains an open question. Finally, other classic Pascal's triangle properties, such as the "Star of David" theorem, could be generalized to these truncated versions.

Summary updated

Abstract

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.
BibTeX
@misc{donnelly2018counting,
  author = {Robert G. Donnelly and Molly W. Dunkum and Courtney George and Stefan Schnake},
  title = {{Counting odd numbers in truncations of Pascal's triangle}},
  year = {2018},
  eprint = {1807.08181},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1807.08181},
}

Loading related content...

Figure