JEDNOSTKA NAUKOWA KATEGORII A+

# Wydawnictwa / Czasopisma IMPAN / Acta Arithmetica / Wszystkie zeszyty

## Acta Arithmetica

Artykuły w formacie PDF dostępne są dla subskrybentów, którzy zapłacili za dostęp online, po podpisaniu licencji Licencja użytkownika instytucjonalnego. Czasopisma do 2009 są ogólnodostępne (bezpłatnie).

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

### Tom 181 / 2017

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

#### Streszczenie

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.

#### Autorzy

• 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

## Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

## Przepisz kod z obrazka Odśwież obrazek