The number of binomial coefficients divisible by a fixed power of a prime (Q2534217): Difference between revisions

Let \(p\) be a fixed prime and let \(\theta_j(n)\) denote the number of binomial coefficients \(\binom{n}{r}\) \((0\le r\le n)\), divisible by exactly \(p^j\). If \(n = n_0 +n-1p+ \ldots +n_rp^r\) \((0\le n_i \le p)\), it is well known that \[ \theta_0(n) = (n_0 + 1)(n_1 + 1) \cdots (n_r +1).\] The evaluation of \(\theta_j(n)\) for arbitrary \(j\) seems to be considerably more difficult. It is convenient to introduce an auxiliary function \(\psi_j(n)\) which is defined as the number of products \((n+1)\binom{n}{r}\) \((0\le r\le n)\) divisible by exactly \(p^j\). It is proved that \(\theta_j(n)\), \(\psi_j(n)\) satisfy the mixed recurrences \((j\ge 1)\) \[ \begin{cases} \theta_j(a_0 + ap) = (a_0 + 1) \theta_j(a) + (p - a_0 - 1) \psi_{j-1}(a - 1)\quad &(0\le a_0<p), \\ \psi_j(a_0 + ap) = (a_0 + 1) \theta_j(a) + (p - a_0 - 1) \psi_{j-1}(a - 1)\quad &(0\le a_0< p - 1), \\ \psi_j(p-1 + ap)) = p \psi_{j - 1}(a), \end{cases} \tag{*} \] where \(a\) is an arbitrary nonnegative integer and \(\psi_j(-1) = 0\). This result is equivalent to \[ \begin{split}F(x,y) &= f_0(x) F(x^p,y) + yg_0(x) G(x^p,y), \\ G(x,y) &= f_1(x) F(x^p,y) + yg_1(x) G(x^p,yY), \end{split} \] where \[ F(x,y) = \sum_{n=0}^\infty \sum_{j=0}^\infty \theta_j(n)x^ny^j,\quad G(x,y)= \sum_{n=0}^\infty \sum_{j=0}^\infty \psi_j(n)y^i. \] Making use of the recurrences, \(\theta_j(n)\), \(\psi_j(n)\) can be evaluated explicitly in certain cases. For example \(\theta_j(ap^s - 1) = p^s \theta_j(a - 1)\) \((a_s\ge 1)\), which yields \((0\le a < p)\) \[\theta_j(ap^{s+1} + p^s - 1) = \begin{cases} (a+1)p^s\qquad &(j = 0) \\ ap^{s+j-1}(p-1)\quad &(0<j\le t). \end{cases} \] The functions \(\theta_j(an_r )\), \(\theta_j(an_r - 1)\), where \(n_r = (p^r - 1)/(p - 1)\), are evaluated explicitly. Also the sum functions \[ S_j(r)= \sum_{a=0} ^{p^r -1} \theta_j(a),\quad S'_j(r)= \sum_{a=0} ^{p^r -1} \psi_j(a) \] are evaluated. Finally we mention that recurrences generalizing (*) are obtained for the functions \(\theta_j(a+ bp^r )\), \(\psi(a+ bp^r)\), where \(0\le a<p^r\), \(b\ge 0\).