OFFSET
0,2
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
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.
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
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
EXAMPLE
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
MAPLE
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 *)
PROG
(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 */
(Magma) [(4^n+Binomial(2*n, n))/2:n in [0.. 30]]; // Vincenzo Librandi, Oct 18 2014
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
J. H. Conway, Dec 11 1999
STATUS
approved