{
  "id": "1604.07089",
  "version": "v1",
  "published": "2016-04-24T22:33:46.000Z",
  "updated": "2016-04-24T22:33:46.000Z",
  "title": "Divisibility of binomial coefficients by powers of primes",
  "authors": [
    "Michael Wallner",
    "Lukas Spiegelhofer"
  ],
  "comment": "25 pages",
  "categories": [
    "math.NT",
    "math.CO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-04-24T22:33:46.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "11B65",
      "11A63",
      "11B50",
      "05A16"
    ],
    "keywords": [
      "divisibility",
      "nonzero binomial coefficients modulo",
      "polynomial",
      "generating functions",
      "finite words"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 25,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2016arXiv160407089S"
    }
  }
}