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

Lukas Spiegelhofer, Michael Wallner 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

Odśwież obrazek