%I M0227 #66 Jan 25 2024 07:52:07

%S 0,3,1,2,2,2,3,2,2,2,4,2,2,2,2,4,2,2,2,2,3,4,2,2,2,2,2,2,4,2,2,2,2,2,

%T 2,4,4,2,2,2,2,2,2,2,2,4,2,2,2,2,2,2,2,2,2,4,4,2,2,2,2,2,2,2,2,2,4,2,

%U 2,2,3,2,2,2,2,2,2,2,4,2,2,2,2,2,4,2,2,2,2,2,2,4,2,2,2,2,2,2,2,2,2,2

%N Number of occurrences of n as an entry in rows <= n of Pascal's triangle (A007318).

%C Or, number of occurrences of n as a binomial coefficient. [Except for 1 which occurs infinitely many times. This is the only reason for the restriction "row <= n" in the definition. Any other number can only appear in rows <= n. - _M. F. Hasler_, Feb 16 2023]

%C Sequence A138496 gives record values and where they occur. - _Reinhard Zumkeller_, Mar 20 2008

%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 93, #47.

%D C. S. Ogilvy, Tomorrow's Math. 2nd ed., Oxford Univ. Press, 1972, p. 96.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Reinhard Zumkeller, <a href="/A003016/b003016.txt">Table of n, a(n) for n = 0..10000</a>

%H H. L. Abbott, P. Erdős and D. Hanson, <a href="http://www.jstor.org/stable/2319526">On the numbers of times an integer occurs as a binomial coefficient</a>, Amer. Math. Monthly, (1974), 256-261.

%H Daniel Kane, <a href="http://www.emis.de/journals/INTEGERS/papers/e7/e7.Abstract.html">New Bounds on the Number of Representations of t as a Binomial Coefficient</a>, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 4, Paper A7, 2004.

%H Kaisa Matomäki, Maksym Radziwill, Xuancheng Shao, Terence Tao, and Joni Teräväinen, <a href="https://arxiv.org/abs/2106.03335">Singmaster's conjecture in the interior of Pascal's triangle</a>, arXiv:2106.03335 [math.NT], 2021.

%H D. Singmaster, <a href="http://www.jstor.org/stable/2316907">How often does an integer occur as a binomial coefficient?</a>, Amer. Math. Monthly, 78 (1971), 385-386.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PascalsTriangle.html">Pascal's Triangle</a>

%H <a href="/index/Pas#Pascal">Index entries for triangles and arrays related to Pascal's triangle</a>

%t a[0] = 0; t = {{1}}; a[n_] := Count[ AppendTo[t, Table[ Binomial[n, k], {k, 0, n}]], n, {2}]; Table[a[n], {n, 0, 101}] (* _Jean-François Alcover_, Feb 20 2012 *)

%o (Haskell)

%o a003016 n = sum $ map (fromEnum . (== n)) $

%o concat $ take (fromInteger n + 1) a007318_tabl

%o -- _Reinhard Zumkeller_, Apr 12 2012

%o (PARI) {A003016(n)=if(n<4, [0,3,1,2][n+1], my(c=2, k=2, r=sqrtint(2*n)+1, C=r*(r-1)/2); until(, while(C<n && k<r\2, C *= r-k; k += 1; C \= k); C == n && c += 2-(r == 2*k); k >= r\2 && break; C *= r-k; C \= r; r -= 1); c)} \\ _M. F. Hasler_, Feb 16 2023

%o (Python)

%o from math import isqrt # requires python3.8 or higher

%o def A003016(n):

%o if n < 4: return[0,3,1,2][n]

%o cnt = k = 2; r = isqrt(2*n)+1; C = r*(r-1)//2

%o while True:

%o while C < n and k < r//2:

%o C *= r-k; k += 1; C //= k

%o if C == n: cnt += 2 - (r == 2*k)

%o if k >= r//2: return cnt

%o C *= r-k; C //= r; r -= 1 # _M. F. Hasler_, Feb 16 2023

%Y Cf. A003015, A059233, A138496, A180058.

%K nonn,nice,easy

%O 0,2

%A _N. J. A. Sloane_

%E More terms from _Erich Friedman_

%E Edited by _N. J. A. Sloane_, Nov 18 2007, at the suggestion of _Max Alekseyev_