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

1, 3, 11, 42, 163, 638, 2510, 9908, 39203, 155382, 616666, 2449868, 9740686, 38754732, 154276028, 614429672, 2448023843, 9756737702, 38897306018, 155111585372, 618679078298, 2468152192772, 9848142504068, 39301087452632, 156861290196878, 626155256640188

Offset: 0

Author

J. H. Conway, Dec 11 1999

Keywords

• nonn
• easy

Comments

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

1 1 1 1 1 1 1 ...

2 3 4 5 6 7 8 ...

4 7 11 16 22 ...

8 15 26 42 64 ...

16 31 .. 99 163 ...

From Gary W. Adamson, Dec 27 2008: (Start)

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)

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

Row sums of A094527. - Paul Barry, Sep 07 2009

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

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

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

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

Examples

			G.f. = 1 + 3*x + 11*x^2 + 42*x^3 + 163*x^4 + 638*x^5 + 2510*x^6 + 9908*x^7 + ...
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
		

References

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

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200
• Véronique Bazier-Matte, Ruiyan Huang, and Hanyi Luo, Number of Triangulations of a Möbius Strip, arXiv:2009.05785 [math.CO], 2020.
• A. Bernini, F. Disanto, R. Pinzani and S. Rinaldi, Permutations defining convex permutominoes, J. Int. Seq. 10 (2007) # 07.9.7.
• Celeste Damiani, Paul Martin, and Eric C. Rowell, Generalisations of Hecke algebras from Loop Braid Groups, arXiv:2008.04840 [math.GT], 2020.
• M. Klazar, Twelve countings with rooted plane trees, European Journal of Combinatorics 18 (1997), 195-210; Addendum, 18 (1997), 739-740.
• Mircea Merca, A Note on Cosine Power Sums J. Integer Sequences, Vol. 15 (2012), Article 12.5.3.

Crossrefs

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

Cf. A000108, A000302, A110166.

Programs

Magma

[(4^n+Binomial(2*n, n))/2:n in [0.. 30]]; // Vincenzo Librandi, Oct 18 2014

Maple

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

Mathematica

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

PARI

A032443 = n->sum(i=0,n,binomial(2*n,i)) \\ M. F. Hasler, Jan 02 2014

PARI

A032443 = n->binomial(2*n-1,n)+4^n\2 \\ M. F. Hasler, Jan 02 2014

PARI

{a(n) = if( n<-3, 0, (4^n + binomial(2*n, n)) / 2)} /* Michael Somos, Jan 25 2014 */

Formula

a(n) = (4^n+binomial(2*n, n))/2. - David W. Wilson

a(n) = Sum_{0 <= i_1 <= i_2 <= n} binomial(n, i_2) * binomial(n, i_1+i_2). - Benoit Cloitre, Oct 14 2004

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

a(n) = Sum_{k=0..n} C(n+k-1, k)*2^(n-k). - Paul Barry, Sep 28 2007

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

From Sergei N. Gladkovskii, Aug 13 2012: (Start)

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).

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).

(End)

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

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

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

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

a(n) = coefficient of x^n in (4*x + 1 / (1 + x))^n. - Michael Somos, Jan 25 2014

Binomial transform is A110166. - Michael Somos, Jan 25 2014

Asymptotics: a(n) ~ 2^(2*n-1)*(1+1/sqrt(Pi*n)). - Fung Lam, Apr 13 2014

Self-convolution is A240879. - Fung Lam, Apr 13 2014

a(0) = 1, a(n+1) = A001700(n) + 2^(2n+1). - Philippe Deléham, Oct 11 2014

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

a(n) = 4*a(n-1) - A000108(n-1). - Bob Selcoe, Apr 02 2017

a(n) = [x^n] 1/((1 - x)^n*(1 - 2*x)). - Ilya Gutkovskiy, Oct 12 2017

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

O.g.f.: ( hypergeom([1/4, 3/4], [1/2], 4*x) )^2. - Peter Bala, Mar 04 2022

a(n) = binomial(2*n, n) * hypergeom([1, -n], [n + 1], -1). - Peter Luschny, Oct 06 2023