Matrix Product Formulas for Generating Functions for p-adic Valuations of Generalized Binomial Coefficients

Overview

For the last 20 years, many researchers have explored divisibility properties of integer sequences arising from combinatorial structures. In particular, binomial coefficients have been the subject of several papers. Rowland found a matrix product formula for counting binomials by their divisibility by a prime p (p-adic valuations). I generalize this to a broader class of sequences, deriving analogous matrix product formulas for C-nomials – extensions of binomial coefficients based on integer sequences C inspired by Knuth and Wilf. This generalization shows that, surprisingly, Rowland’s binomial matrices exhibit a universality across all C-nomial coefficients, expanding their known significance in combinatorics. To obtain this generalization, I used Mathematica to compute sequences of C-nomial generating functions, and identified linear relations between subsequences of the form s(p^e * n + r), for e>=0, 0 <= r < p^e. Refining these initial relations through structural observations and change-of-basis techniques led to conjectured formulas. Next, by introducing classifications of “ideal” and “somewhat-ideal” primes, I derived explicit p-adic valuation formulas for C-nomials. This allowed me to prove the conjectures using a counting argument relating C-nomial and binomial valuations. To manage repetitive casework, I designed an algorithm that systematically constructs the key vector factor in the matrix product. The sequences studied are k-regular, a notion introduced in 1992, suggesting connections to automata theory, including algorithmic analysis. This research deepens understanding of divisibility in combinatorial structures by discovering strong relations to binomials, and significantly improves time complexity, enabling efficient computation of C-nomial properties.

Competition history

• ISEF 2025 Mathematics · Entry MATH022

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.