cp's OEIS Frontend

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

%I A003016 M0227 #73 Jun 26 2025 01:24:36
%S A003016 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 A003016 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 A003016 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 A003016 Number of occurrences of n as an entry in rows <= n of Pascal's triangle (A007318).
%C A003016 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 A003016 Sequence A138496 gives record values and where they occur. - _Reinhard Zumkeller_, Mar 20 2008
%C A003016 Singmaster conjectures that this sequence is bounded. - _Michael J. Hardy_, Jun 09 2025
%D A003016 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 93, #47.
%D A003016 C. S. Ogilvy, Tomorrow's Math. 2nd ed., Oxford Univ. Press, 1972, p. 96.
%D A003016 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003016 Reinhard Zumkeller, <a href="/A003016/b003016.txt">Table of n, a(n) for n = 0..10000</a>
%H A003016 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 A003016 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 A003016 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 A003016 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 A003016 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PascalsTriangle.html">Pascal's Triangle</a>
%H A003016 <a href="/index/Pas#Pascal">Index entries for triangles and arrays related to Pascal's triangle</a>
%t A003016 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 A003016 (Haskell)
%o A003016 a003016 n = sum $ map (fromEnum . (== n)) $
%o A003016                       concat $ take (fromInteger n + 1) a007318_tabl
%o A003016 -- _Reinhard Zumkeller_, Apr 12 2012
%o A003016 (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 A003016 (Python)
%o A003016 from math import isqrt # requires python3.8 or higher
%o A003016 def A003016(n):
%o A003016     if n < 4: return[0,3,1,2][n]
%o A003016     cnt = k = 2; r = isqrt(2*n)+1; C = r*(r-1)//2
%o A003016     while True:
%o A003016        while C < n and k < r//2:
%o A003016           C *= r-k; k += 1; C //= k
%o A003016        if C == n: cnt += 2 - (r == 2*k)
%o A003016        if k >= r//2: return cnt
%o A003016        C *= r-k; C //= r; r -= 1 # _M. F. Hasler_, Feb 16 2023
%Y A003016 Cf. A003015, A059233, A138496, A180058.
%K A003016 nonn,nice,easy
%O A003016 0,2
%A A003016 _N. J. A. Sloane_
%E A003016 More terms from _Erich Friedman_
%E A003016 Edited by _N. J. A. Sloane_, Nov 18 2007, at the suggestion of _Max Alekseyev_