A014137 - OEIS

%I #168 Sep 02 2024 03:50:39

%S 1,2,4,9,23,65,197,626,2056,6918,23714,82500,290512,1033412,3707852,

%T 13402697,48760367,178405157,656043857,2423307047,8987427467,

%U 33453694487,124936258127,467995871777,1757900019101,6619846420553,24987199492705,94520750408709,358268702159069

%N Partial sums of Catalan numbers (A000108).

%C This is also the result of applying the transformation on generating functions A -> 1/((1 - x)*(1 - x*A)) to the g.f. for the Catalan numbers.

%C p divides a(p) - 3 for prime p = 3 and p = {7, 13, 19, 31, 37, 43, ...} = A002476 (Primes of the form 6*n + 1). p^2 divides a(p^2) - 3 for prime p > 3. - _Alexander Adamchuk_, Jul 11 2006

%C Prime p divides a(p) for p = {2, 3, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, 101, ...} = A045309 (Primes congruent to {0, 2} mod 3); and A045309 (Primes p such that x^3 = n (integer) has only one solution mod p). Nonprime numbers n such that n divides a(n) are listed in A128287 = {1, 8, 133, ...}. - _Alexander Adamchuk_, Feb 23 2007

%C For p prime >= 5, a(p-1) = 1 or -2 (mod p) according as p = 1 or -1 (mod 3) (see Pan and Sun link). For example, with p=5, a(p-1) = 23 = -2 (mod p). - _David Callan_, Nov 29 2007

%C Hankel transform is A010892(n+1). - _Paul Barry_, Apr 24 2009

%C Equals INVERTi transform of A000245: (1, 3, 9, 28, ...). - _Gary W. Adamson_, May 15 2009

%C The subsequence of prime partial sums of Catalan numbers begins: a(1) = 2, a(4) = 23, a(6) = 197, a(16) = 48760367; see A121852. - _Jonathan Vos Post_, Feb 10 2010

%C Number of lattice paths from (0,0) to (n,n) which do not go above the diagonal x=y using steps (1,k), (k,1) with k >= 1 including two kinds of (1,1). - _Alois P. Heinz_, Oct 14 2015

%C Binomial transform of A086246(n+1) = [1, 1, 1, 2, 4, 9, ...], or, equivalently, of A001006 (Motzkin numbers) with 1 prepended.

%H G. C. Greubel, <a href="/A014137/b014137.txt">Table of n, a(n) for n = 0..1000</a> (terms 0 to 200 by T. D. Noe)

%H G. Alvarez, J. E. Bergner, and R. Lopez, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Bergner/bergner2.html">Action Graphs and Catalan Numbers</a>, J. Int. Seq. 18 (2015), 15.7.2.

%H M. Apagodu, D. Zeilberger, <a href="https://doi.org/10.4169/amer.math.monthly.124.7.597">Using the Freshman's dream to prove combinatorial congruences</a>, Am. Math. Mon.  124, No. 7, 597-608 (2017), prop. 2'

%H Maciej Bendkowski and Pierre Lescanne, <a href="https://arxiv.org/abs/1804.03862">Combinatorics of explicit substitutions</a>, arXiv:1804.03862 [cs.LO], 2018.

%H W. Chammam, F. Marcellán and R. Sfaxi, <a href="http://dx.doi.org/10.1016/j.laa.2011.10.010">Orthogonal polynomials, Catalan numbers, and a general Hankel determinant evaluation</a>, Linear Algebra Appl. 436(7) (2012), 2105-2116.

%H Joel E. Cohen, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL25/Cohen/cohen13.html">Variance Functions of Asymptotically Exponentially Increasing Integer Sequences Go Beyond Taylor's Law</a>, J. Int. Seq., Vol. 25 (2022), Article 22.9.3.

%H Dennis E. Davenport, Lara K. Pudwell, Louis W. Shapiro, and Leon C. Woodson, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Davenport/dav3.html">The Boundary of Ordered Trees</a>, Journal of Integer Sequences, 18 (2015), Article 15.5.8.

%H Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, <a href="http://dx.doi.org/10.1016/j.disc.2007.04.007">2-Binary trees: bijections and related issues</a>, Discr. Math., 308 (2008), 1209-1221.

%H Guo-Niu Han, <a href="/A196265/a196265.pdf">Enumeration of Standard Puzzles</a>, 2011. [Cached copy]

%H Guo-Niu Han, <a href="https://arxiv.org/abs/2006.14070">Enumeration of Standard Puzzles</a>, arXiv:2006.14070 [math.CO], 2020.

%H Ângela Mestre and José Agapito, <a href="https://www.emis.de/journals/JIS/VOL22/Agapito/mestre8.html">A Family of Riordan Group Automorphisms</a>, J. Int. Seq., Vol. 22 (2019), Article 19.8.5.

%H I. Pak, <a href="http://dx.doi.org/10.1090/S0002-9939-04-07031-5">Partition identities and geometric bijections</a>, Proc. Amer. Math. Soc. 132 (2004), 3457-3462.

%H Hao Pan and Zhi-Wei Sun, <a href="http://arxiv.org/abs/math/0509648">A combinatorial identity with application to Catalan numbers</a>, arXiv:math/0509648 [math.CO], 2005-2006.

%H Murray Tannock, <a href="https://skemman.is/bitstream/1946/25589/1/msc-tannock-2016.pdf">Equivalence classes of mesh patterns with a dominating pattern</a>, MSc Thesis, Reykjavik Univ., May 2016. See Appendix B2.

%H Kevin Topley, <a href="http://arxiv.org/abs/1601.04223">Computationally Efficient Bounds for the Sum of Catalan Numbers</a>, arXiv:1601.04223 [math.CO], 2016.

%F a(n) = A014138(n-1) + 1.

%F G.f.: (1 - (1 - 4*x)^(1/2))/(2*x*(1 - x)).

%F a(n) = Sum_{k=0..n} (2k)!/(k!)^2/(k+1). - _Alexander Adamchuk_, Jul 11 2006

%F D-finite with recurrence: (n+1)*a(n) + (1-5*n)*a(n-1) + 2*(2*n-1)*a(n-2) = 0. - _R. J. Mathar_, Dec 14 2011

%F Mathar's formula reduces to 2*(2*n-1)*C(n-1) = (n+1)*C(n), which is a known recurrence of the Catalan numbers, so the conjecture is true. - _Peter J. Taylor_, Mar 23 2015

%F Let C(n+1) = binomial(2*n+2,n+1)/(n+2) and H(n) = hypergeometric([1,n+3/2],[n+3],4) then A014137(n) = -(-1)^(2/3) - C(n+1)*H(n) and A014138(n) = -I^(2/3) - C(n+1)*H(n). - _Peter Luschny_, Aug 09 2012

%F G.f. (conjecture): Q(0)/(1-x), where Q(k)= 1 + (4*k + 1)*x/(k + 1 - 2*x*(k + 1)*(4*k + 3)/(2*x*(4*k + 3) + (2*k + 3)/Q(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, May 14 2013

%F a(n) ~ 2^(2*n + 2)/(3*sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Dec 10 2013

%F 0 =  a(n)*(16*a(n+1) - 26*a(n+2) + 10*a(n+3)) + a(n+1)*(-14*a(n+1) + 23*a(n+2) - 11*a(n+3)) + a(n+2)*(a(n+2) + a(n+3)) if n >= 0. - _Michael Somos_, Oct 24 2015

%F a(n) = (1 + A000108(n)*(3*(n+1)*hypergeom([1,-n], [1/2-n], 1/4) - 4*n - 2))/2. - _Vladimir Reshetnikov_, Oct 03 2016

%F G.f. A(x) satisfies: A(x) = 1 / (1 - x) + x * (1 - x) * A(x)^2. - _Ilya Gutkovskiy_, Jul 25 2021

%F From _Peter Luschny_, Nov 16 2022: (Start)

%F a(n) = C(n)*hypergeom([1, -n - 1], [1/2 - n], 1/4) + 1/2.

%F a(n) = A358436(n) / C(n). (End)

%F E.g.f.: exp(2*x)*(BesselI(0, 2*x)/2 - BesselI(1, 2*x)) + exp(x)/2*(3*Integral_{x=-oo..oo} BesselI(0,2*x)*exp(x) dx + 1). - _Mélika Tebni_, Sep 01 2024

%e G.f. = 1 + 2*x + 4*x^2 + 9*x^3 + 23*x^4 + 65*x^5 + 197*x^6 + 626*x^7 + 2056*x^8 + ...

%p a:= proc(n) option remember; `if`(n<2, n+1,

%p       ((5*n-1)*a(n-1)-(4*n-2)*a(n-2))/(n+1))

%p     end:

%p seq(a(n), n=0..30);  # _Alois P. Heinz_, May 18 2013

%p A014137List := proc(m) local A, P, n; A := [1]; P := [1];

%p for n from 1 to m - 2 do P := ListTools:-PartialSums([op(P), P[-n]]);

%p A := [op(A), P[-1]] od; A end: A014137List(30); # _Peter Luschny_, Mar 26 2022

%t Table[Sum[(2k)!/(k!)^2/(k+1),{k,0,n}],{n,0,30}] (* _Alexander Adamchuk_, Jul 11 2006 *)

%t Accumulate[CatalanNumber[Range[0,30]]] (* _Harvey P. Dale_, May 08 2012 *)

%t a[ n_] := SeriesCoefficient[ (1 - (1 - 4 x)^(1/2)) / (2 x (1 - x)), {x, 0, n}]; (* _Michael Somos_, Oct 24 2015 *)

%t Table[(1 + CatalanNumber[n] (3 (n + 1) Hypergeometric2F1[1, -n, 1/2 - n, 1/4] - 4 n - 2))/2, {n, 0, 20}] (* _Vladimir Reshetnikov_, Oct 03 2016 *)

%o (PARI) Vec((1-(1-4*x)^(1/2))/(2*x*(1-x))+O(x^99)) \\ _Charles R Greathouse IV_, Feb 11 2011

%o (PARI)

%o sm(v)={my(s=vector(#v)); s[1]=v[1]; for(n=2, #v, s[n]=v[n]+s[n-1]); s; }

%o C(n)=binomial(2*n, n)/(n+1);

%o sm(vector(66, n, C(n-1)))

%o /* _Joerg Arndt_, May 04 2013 */

%o (Python)

%o from __future__ import division

%o A014137_list, b, s = [], 1, 0

%o for n in range(10**2):

%o     s += b

%o     A014137_list.append(s)

%o     b = b*(4*n+2)//(n+2) # _Chai Wah Wu_, Jan 28 2016

%o (Sage)

%o def A014137():

%o     f, c, n = 1, 1, 1

%o     while True:

%o         yield f

%o         n += 1

%o         c = c * (4*n - 6) // n

%o         f = c + f

%o a = A014137()

%o print([next(a) for _ in range(29)]) # _Peter Luschny_, Nov 30 2016

%o (Magma)

%o [(&+[Catalan(k): k in [0..n]]): n in [0..40]]; // _G. C. Greubel_, Jun 30 2024

%Y Cf. A000108, A000245, A000984, A001246, A002476, A002897, A006134, A033536, A045309, A079727, A082894, A094638, A094639, A128287, A358436.

%K nonn,nice

%O 0,2

%A _N. J. A. Sloane_