A032443 - OEIS

%I #145 Aug 06 2024 21:16:22

%S 1,3,11,42,163,638,2510,9908,39203,155382,616666,2449868,9740686,

%T 38754732,154276028,614429672,2448023843,9756737702,38897306018,

%U 155111585372,618679078298,2468152192772,9848142504068,39301087452632,156861290196878,626155256640188

%N a(n) = Sum_{i=0..n} binomial(2*n, i).

%C Array interpretation: first row is filled with 1's, first column with powers of 2, b(i,j) = b(i-1,j) + b(i,j-1); then a(n) = b(n,n). - _Benoit Cloitre_, Apr 01 2002

%C    1   1   1   1   1   1   1 ...

%C    2   3   4   5   6   7   8 ...

%C    4   7  11  16  22 ...

%C    8  15  26  42  64 ...

%C   16  31  ..  99 163 ...

%C From _Gary W. Adamson_, Dec 27 2008: (Start)

%C This is an analog of the Catalan sequence: Let M denote an infinite Cartan matrix (-1's in the super and subdiagonals and (2,2,2,...) in the main diagonal which we modify to (1,2,2,2,...)). Then A000108 can be generated by accessing the leftmost term in M^n * [1,0,0,0,...]. Change the operation to M^n * [1,2,3,...] to get this sequence. Or, take iterates M * [1,2,3,...] -> M * ANS, -> M * ANS,...; accessing the leftmost term. (End)

%C Convolved with the Catalan sequence, A000108: (1, 1, 2, 5, 14, ...) = powers of 4, A000302: (1, 4, 16, 64, ...). - _Gary W. Adamson_, May 15 2009

%C Row sums of A094527. - _Paul Barry_, Sep 07 2009

%C Hankel transform of the aeration of this sequence is C(n+2, 2). - _Paul Barry_, Sep 26 2009

%C Number of 4-ary words of length n in which the number of 1's does not exceed the number of 0's. - _David Scambler_, Aug 14 2012

%C Number of options available to a voter who has up to n (0-n) votes to allot among 2n candidates. - _Lorraine Lee_, Apr 27 2019

%C 2*a(n-1) is the number of all triangulations that can be obtained from a Möbius strip with n chosen points on its edge. See Bazier-Matte et al. - _Michel Marcus_, Sep 15 2020

%D D. Phulara and L. W. Shapiro, Descendants in ordered trees with a marked vertex, Congressus Numerantium, 205 (2011), 121-128.

%H Vincenzo Librandi, <a href="/A032443/b032443.txt">Table of n, a(n) for n = 0..200</a>

%H Véronique Bazier-Matte, Ruiyan Huang, and Hanyi Luo, <a href="https://arxiv.org/abs/2009.05785">Number of Triangulations of a Möbius Strip</a>, arXiv:2009.05785 [math.CO], 2020.

%H A. Bernini, F. Disanto, R. Pinzani and S. Rinaldi, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Rinaldi/rinaldi5.html">Permutations defining convex permutominoes</a>, J. Int. Seq. 10 (2007) # 07.9.7.

%H Celeste Damiani, Paul Martin, and Eric C. Rowell, <a href="https://arxiv.org/abs/2008.04840">Generalisations of Hecke algebras from Loop Braid Groups</a>, arXiv:2008.04840 [math.GT], 2020.

%H M. Klazar, <a href="http://dx.doi.org/10.1006/eujc.1995.0095">Twelve countings with rooted plane trees</a>, European Journal of Combinatorics 18 (1997), 195-210; Addendum, 18 (1997), 739-740.

%H Mircea Merca, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL15/Merca1/merca6.html">A Note on Cosine Power Sums</a> J. Integer Sequences, Vol. 15 (2012), Article 12.5.3.

%F a(n) = (4^n+binomial(2*n, n))/2. - _David W. Wilson_

%F a(n) = Sum_{0 <= i_1 <= i_2 <= n} binomial(n, i_2) * binomial(n, i_1+i_2). - _Benoit Cloitre_, Oct 14 2004

%F Sequence with interpolated zeros has a(n) = Sum_{k=0..floor(n/2)} (if((n-2k) mod 2)=0, C(n, k), 0). - _Paul Barry_, Jan 14 2005

%F a(n) = Sum_{k=0..n} C(n+k-1, k)*2^(n-k). - _Paul Barry_, Sep 28 2007

%F E.g.f.: exp(2*x)*(exp(2*x) + BesselI(0,2*x))/2. For BesselI see Abramowitz-Stegun (reference and link under A008277), p. 375, eq. 9.6.10. See also A000984 for its e.g.f. - _Wolfdieter Lang_, Jan 16 2012

%F From _Sergei N. Gladkovskii_, Aug 13 2012: (Start)

%F G.f.: (1/sqrt(1-4*x) + 1/(1-4*x))/2 = G(0)/2 where G(k) = 1 + ((2*k)!)/(k!)^2/(4^k - 4*x*(16^k)/( 4*x*(4^k) + (2*k)!)/(k!)^2/G(k+1))); (continued fraction).

%F E.g.f.: G(0)/2 where G(k)= 1 + ((2*k)!)/(k!)^2/(4^k - 4*x*(16^k)/( 4*x*(4^k) + (k+1)*(2*k)!)/(k!)^2/G(k+1))); (continued fraction).

%F (End)

%F O.g.f.: (1 - x*(2 + c(x)))/(1 - 4*x)^(3/2), with c the o.g.f. of A000108 (Catalan). - _Wolfdieter Lang_, Nov 22 2012

%F D-finite with recurrence: n*a(n) + 2*(-4*n+3)*a(n-1) + 8*(2*n-3)*a(n-2) = 0. - _R. J. Mathar_, Dec 04 2012

%F a(n) = binomial(2*n-1,n) + floor(4^n/2), or a(n+1) = A001700(n) + A004171(n), for all n >= 0. See A000346 for the difference. - _M. F. Hasler_, Jan 02 2014

%F 0 = a(n) * (256*a(n+1) - 224*a(n+2) + 40*a(n+3)) + a(n+1) * (-32*a(n+1) + 56*a(n+2) - 14*a(n+3)) + a(n+2) * (-2*a(n+2) + a(n+3)) if n > -4. - _Michael Somos_, Jan 25 2014

%F a(n) = coefficient of x^n in (4*x + 1 / (1 + x))^n. - _Michael Somos_, Jan 25 2014

%F Binomial transform is A110166. - _Michael Somos_, Jan 25 2014

%F Asymptotics: a(n) ~ 2^(2*n-1)*(1+1/sqrt(Pi*n)). - _Fung Lam_, Apr 13 2014

%F Self-convolution is A240879. - _Fung Lam_, Apr 13 2014

%F a(0) = 1, a(n+1) = A001700(n) + 2^(2n+1). - _Philippe Deléham_, Oct 11 2014

%F exp( Sum_{n >= 1} a(n)*x^n/n ) = 1 + 3*x + 10*x^2 + 35*x^3 + 126*x^4 + ... is the o.g.f. for A001700. - _Peter Bala_, Jul 21 2015

%F a(n) = 4*a(n-1) - A000108(n-1). - _Bob Selcoe_, Apr 02 2017

%F a(n) = [x^n] 1/((1 - x)^n*(1 - 2*x)). - _Ilya Gutkovskiy_, Oct 12 2017

%F The Gauss congruences a(n*p^k) == a(n*p^(k-1)) (mod p^k) hold for prime p and positive integers n and k. - _Peter Bala_, Jan 08 2022

%F O.g.f.: ( hypergeom([1/4, 3/4], [1/2], 4*x) )^2. - _Peter Bala_, Mar 04 2022

%F a(n) = binomial(2*n, n) * hypergeom([1, -n], [n + 1], -1). - _Peter Luschny_, Oct 06 2023

%e G.f. = 1 + 3*x + 11*x^2 + 42*x^3 + 163*x^4 + 638*x^5 + 2510*x^6 + 9908*x^7 + ...

%e According to the second formula, we see the fourth row of Pascal's triangle has the terms 1,4,6,4,1 and the partial sums are 1,5,11,15,16. Using these we get 1*1 + 4*5 + 6*11 + 4*15*1*16 = 1 + 20 + 66 + 60 + 16 = 163 = a(4). - _J. M. Bergot_, Apr 29 2014

%p A032443:=n->(4^n + binomial(2*n, n))/2; seq(A032443(n), n=0..30); # _Wesley Ivan Hurt_, Apr 15 2014

%t a[ n_] := If[ n<-3, 0, (4^n + Binomial[2 n, n]) / 2]; Table[a[n], {n, 0, 30}] (* _Michael Somos_, Jan 25 2014 *)

%o (PARI) A032443 = n->sum(i=0,n,binomial(2*n,i)) \\ _M. F. Hasler_, Jan 02 2014

%o (PARI) A032443 = n->binomial(2*n-1,n)+4^n\2 \\ _M. F. Hasler_, Jan 02 2014

%o (PARI) {a(n) = if( n<-3, 0, (4^n + binomial(2*n, n)) / 2)} /* _Michael Somos_, Jan 25 2014 */

%o (Magma) [(4^n+Binomial(2*n, n))/2:n in [0.. 30]]; // _Vincenzo Librandi_, Oct 18 2014

%Y Binomial transform of A027914. Hankel transform is {1, 2, 3, 4, ..., n, ...}.

%Y Cf. A000108, A000302, A110166.

%K nonn,easy

%O 0,2

%A _J. H. Conway_, Dec 11 1999