PDF files of articles are only available for institutions which have paid for the online version upon signing an Institutional User License.

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

Volume 181 / 2017

Lukas Spiegelhofer, Michael Wallner Acta Arithmetica 181 (2017), 27-55 MSC: Primary 11B65, 05A15; Secondary 11A63, 11B50, 05A16. DOI: 10.4064/aa8524-6-2017 Published online: 11 September 2017

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\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.

Authors

  • Lukas SpiegelhoferInstitute of Discrete Mathematics and Geometry
    Vienna University of Technology
    Wiedner Hauptstraße 8-10
    1040 Wien, Austria
    e-mail
  • Michael WallnerInstitute of Discrete Mathematics and Geometry
    Vienna University of Technology
    Wiedner Hauptstraße 8–10
    1040 Wien, Austria
    e-mail

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image