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

DOI10.4064/AA8524-6-2017zbMATH Open1426.11012arXiv1604.07089OpenAlexW3100857398MaRDI QIDQ4595443FDOQ4595443

Authors: Lukas Spiegelhofer, Michael Wallner 

Publication date: 30 November 2017

Published in: Acta Arithmetica (Search for Journal in Brave)

Abstract: For a prime $p$ and nonnegative integers $j$ and $n$ let $varthet{a}_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)eq(0,ldots,0)$ in $0,ldots,p-1$ we denote by $lvertnver{t}_w$ the number of times that $w$ appears as a factor (contiguous subsequence) of the base-$p$ expansion $n=(n_{mu-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 $varthet{a}_p(j,n)/varthet{a}_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 $lvertnver{t}_w$. This was later made explicit by Rowland (The number of nonzero binomial coefficients modulo $p^{a}lpha$, 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 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.

Full work available at URL: https://arxiv.org/abs/1604.07089

Recommendations

• The number of binomial coefficients divisible by a fixed power of a prime
• Number of binomial coefficients divisible by a fixed power of a prime
• Subprime factorization and the numbers of binomial coefficients exactly divided by powers of a prime
• Publication:3033832
• scientific article; zbMATH DE number 613254

zbMATH Keywords

generating functionsexact enumerationbinomial coefficients modulo powers of primes

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16) Radix representation; digital problems (11A63) Sequences (mod (m)) (11B50) Binomial coefficients; factorials; (q)-identities (11B65)

Cited In (9)

• Divisibility of binomial coefficients by powers of two
• On the Reciprocal of the Binary Generating Function for the Sum of Divisors
• A new look on the generating function for the number of divisors
• Counting binomial coefficients divisible by a prime power
• A matrix generalization of a theorem of Fine
• Number of binomial coefficients divisible by a fixed power of a prime
• Subprime factorization and the numbers of binomial coefficients exactly divided by powers of a prime
• The Tu-Deng conjecture holds almost surely
• The number of binomial coefficients divisible by a fixed power of a prime

This page was built for publication: An explicit generating function arising in counting binomial coefficients divisible by powers of primes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4595443)