Divisibility of binomial coefficients by powers of primes

Abstract

For a prime \(p\) and nonnegative integers \(j\) and \(n\) let \(\vartheta_p(j,n)\) be the number of entries in the \(n\)-th row of Pascal's triangle that are exactly divisible by \(p^j\). Moreover, for a finite sequence \(w=(w_{r-1}\cdots w_0)\neq (0,\ldots,0)\) in \(\{0,\ldots,p-1\}\) we denote by \(\lvert n\rvert_w\) the number of times that \(w\) appears as a factor (contiguous subsequence) of the base-\(p\) expansion \(n=(n_{\nu-1}\cdots n_0)_p\) of \(n\). It follows from the work of Barat and Grabner ("Digital functions and distribution of binomial coefficients", J. London Math. Soc. (2) 64(3), 2001), that \(\vartheta_p(j,n)/\vartheta_p(0,n)\) is given by a polynomial \(P_j\) in the variables \(X_w\), where \(w\) are certain finite words in \(\{0,\ldots,p-1\}\), and each variable \(X_w\) is set to \(\lvert n\rvert_w\). This was later made explicit by Rowland ("The number of nonzero binomial coefficients modulo \(p^\alpha\)", J. Comb. Number Theory 3(1), 2011), independently from Barat and Grabner's work, and Rowland described and implemented an algorithm computing these polynomials \(P_j\). In this paper, we express the coefficients of \(P_j\) using generating functions, and we prove that these generating functions can be determined explicitly by means of a recurrence relation. Moreover, we prove that \(P_j\) is in fact uniquely determined, and we note that the proof of our main theorem also provides a new proof of its existence. Besides providing insight into the structure of the polynomials \(P_j\), our results allow us to compute them in a very efficient way.