An explicit generating function arising in counting binomial coefficients divisible by powers of primes

Lukas Spiegelhofer ¹   ; Michael Wallner ²

¹ Institute of Discrete Mathematics and Geometry Vienna University of Technology Wiedner Hauptstraße 8-10 1040 Wien, Austria
² Institute of Discrete Mathematics and Geometry Vienna University of Technology Wiedner Hauptstraße 8–10 1040 Wien, Austria

Acta Arithmetica, Tome 181 (2017) no. 1, pp. 27-55

Résumé

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\cdots 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_{\mu-1}\cdots n_0$ of $n$. It follows from the work of Barat and Grabner [J. London Math. Soc. 64 (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 [J. Combin. Number Theory 3 (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 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.

Détail

DOI : 10.4064/aa8524-6-2017

Keywords: prime nonnegative integers vartheta number entries nth row pascal triangle exactly divisible nbsp moreover finite sequence r cdots neq cdots ldots p denote lvert rvert number times appears factor contiguous subsequence base p expansion mu cdots follows work barat grabner london math soc vartheta vartheta given polynomial variables where certain finite words ldots p each variable set nbsp lvert rvert later made explicit rowland combin number theory independently barat grabner work rowland described implemented algorithm computing these polynomials nbsp paper express coefficients using generating functions prove these generating functions determined explicitly means recurrence relation moreover prove uniquely determined note proof main theorem provides proof its existence besides providing insight structure polynomials nbsp results allow compute efficient