10
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Divisibility of binomial coefficients by powers of primes

      Preprint
      ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          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,\ldots,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=(n_{\nu-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 \(\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 ("The number of nonzero binomial coefficients modulo \(p^\alpha\)", 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 in fact 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.

          Related collections

          Most cited references12

          • Record: found
          • Abstract: not found
          • Article: not found

          The ring of k-regular sequences

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Binomial Coefficients Modulo a Prime

            N. Fine (1947)
              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              Sur les congruences des nombres eulériens et des coefficients différentiels des fonctions trigonométriques suivant un module premier

              E. Lucas (1873)
                Bookmark

                Author and article information

                Journal
                2016-04-24
                2016-04-26
                Article
                1604.07089
                4c58e7bc-38e1-489d-ae14-dec5b14c0094

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                11B65 (primary), 11A63, 11B50, 05A16 (secondary)
                25 pages
                math.NT math.CO

                Combinatorics,Number theory
                Combinatorics, Number theory

                Comments

                Comment on this article