A020475 - OEIS

A020475

a(n) is the number of k for which binomial(n,k) is divisible by n.

0, 2, 1, 2, 2, 4, 2, 6, 4, 6, 6, 10, 5, 12, 6, 8, 8, 16, 10, 18, 10, 14, 14, 22, 10, 20, 18, 18, 14, 28, 11, 30, 16, 26, 30, 26, 22, 36, 30, 30, 22, 40, 20, 42, 26, 26, 30, 46, 20, 42, 34, 32, 34, 52, 26, 46, 33, 50, 42, 58, 26, 60, 30, 46, 32, 50, 48, 66, 58, 50, 44, 70, 40, 72, 66, 46, 58

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

Note that n is prime iff a(n) = n-1. - T. D. Noe, Feb 23 2006

a(n) >= phi(n) (cf. Robbins). - Michel Marcus, Oct 31 2012

For n > 0: number of zeros in n-th row of A053200. - Reinhard Zumkeller, Jan 01 2013

binomial(n, k) / binomial(n, k-1) = k / (n - k + 1) which eases computation. - David A. Corneth, May 04 2025

LINKS

David A. Corneth, Table of n, a(n) for n = 0..10000 (first 1001 terms from T. D. Noe)

H. Harborth, Divisibility of binomial coefficients by their row number, The American Mathematical Monthly, Vol. 84, No. 1 (Jan., 1977), pp. 35-37.

N. Robbins, On the number of binomial coefficients which are divisible by their row number, Canad. Math. Bull. 25(1982), 363-365.

N. Robbins, On the number of binomial coefficients which are divisible by their row number. II, Canad. Math. Bull. 28(1985), 481-486.

David A. Corneth, PARI program

FORMULA

a(n) = n + 1 - A007012(n). - T. D. Noe, Feb 23 2006

EXAMPLE

From David A. Corneth, May 04 2025: (Start)

a(6) = 2 as binomial(6, k) = 1, 6, 15, 20, 15, 6, 1 for k = 0 through 6 respectively. Among these, a(6) = 2 numbers are divisible by 6.

a(12) = 5. We start at 1 and know that 12 = 2^2 * 3^1 and so the valuation of 2 and 3 are 2 and 1 respectively.

We compute binomial(n, k) / binomial(n, k-1) = k / (n - k + 1) for k = 1 through floor((n-1)/2) = 3 and keep track the valuation of 2 and 3 of binomial(n, k) via this telescoping product.

We get (2, 1), (1, 1), (2, 0), (0, 2), (3, 2). Of them (2, 1) and (3, 2) indicate divisibility by 12 so that's two numbers and four via symmetry. For binomial(12, 6) we get (2, 1) which as symmetry doesn't give two solutions only counts towards one value of k. This gives a total 4+1 = 5 for a(12). (End)

MATHEMATICA

Table[cnt=0; Do[If[Mod[Binomial[n, k], n]==0, cnt++ ], {k, 0, n}]; cnt, {n, 0, 100}] (* T. D. Noe, Feb 23 2006 *)

Join[{0}, Table[Count[Table[Binomial[n, k], {k, 0, n}], _?(Mod[#, n]==0&)], {n, 100}]] (* Harvey P. Dale, Sep 20 2024 *)

PROG

(Haskell)

a020475 n = a020475_list !! n

a020475_list = 0 : map (sum . map (0 ^)) (tail a053200_tabl)

-- Reinhard Zumkeller, Jan 24 2014

(PARI) apply( A020475(n)=sum(k=0, n, binomial(n, k)%n==0), [1..30]) \\ M. F. Hasler, May 04 2025

(PARI) \\ See Corneth link

CROSSREFS

Cf. A007012.