OFFSET
0,2
COMMENTS
Also a(n) = 2nd elementary symmetric function of binomial(n,0), binomial(n,1), ..., binomial(n,n).
Also a(n) = one half the sum of the heights, over all Dyck (n+2)-paths, of the vertices that are at even height and terminate an upstep. For example with n=1, these vertices are indicated by asterisks in the 5 Dyck 3-paths: UU*UDDD, UU*DU*DD, UDUU*DD, UDUDUD, UU*DDUD, yielding a(1)=(2+4+2+0+2)/2=5. - David Callan, Jul 14 2006
Hankel transform is (-1)^n*(2n+1); the Hankel transform of sum(k=0..n, C(2*n,k) ) - C(2n,n) is (-1)^n*n. - Paul Barry, Jan 21 2007
Row sums of the Riordan matrix (1/(1-4x),(1-sqrt(1-4x))/2) (A187926). - Emanuele Munarini, Mar 16 2011
From Gus Wiseman, Jul 19 2021: (Start)
For n > 0, a(n-1) is also the number of integer compositions of 2n with nonzero alternating sum, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. These compositions are ranked by A053754 /\ A345921. For example, the a(3-1) = 22 compositions of 6 are:
(6) (1,5) (1,1,4) (1,1,1,3) (1,1,1,1,2)
(2,4) (1,2,3) (1,1,3,1) (1,1,2,1,1)
(4,2) (1,4,1) (1,2,1,2) (2,1,1,1,1)
(5,1) (2,1,3) (1,3,1,1)
(2,2,2) (2,1,2,1)
(3,1,2) (3,1,1,1)
(3,2,1)
(4,1,1)
(End)
REFERENCES
T. Myers and L. Shapiro, Some applications of the sequence 1, 5, 22, 93, 386, ... to Dyck paths and ordered trees, Congressus Numerant., 204 (2010), 93-104.
D. Phulara and L. W. Shapiro, Descendants in ordered trees with a marked vertex, Congressus Numerantium, 205 (2011), 121-128.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..500
R. Bacher, On generating series of complementary plane trees arXiv:math/0409050 [math.CO], 2004.
Vijay Balasubramanian, Javier M. Magan, and Qingyue Wu, A Tale of Two Hungarians: Tridiagonalizing Random Matrices, arXiv:2208.08452 [hep-th], 2022.
Paul Barry, On a Central Transform of Integer Sequences, arXiv:2004.04577 [math.CO], 2020.
E. A. Bender, E. R. Canfield and R. W. Robinson, The enumeration of maps on the torus and the projective plane, Canad. Math. Bull., 31 (1988), 257-271; see p. 270.
D. E. Davenport, L. K. Pudwell, L. W. Shapiro and L. C. Woodson, The Boundary of Ordered Trees, 2014.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 185
R. K. Guy, Letter to N. J. A. Sloane
Toufik Mansour and José L. Ramirez, Enumerations of polyominoes determined by Fuss-Catalan words, Australas. J. Combin. 81 (3) (2021) 447-457, table 1.
Mircea Merca, A Special Case of the Generalized Girard-Waring Formula, J. Integer Sequences, Vol. 15 (2012), Article 12.5.7. - From N. J. A. Sloane, Nov 25 2012
D. Merlini, R. Sprugnoli and M. C. Verri, Waiting patterns for a printer, FUN with algorithm'01, Isola d'Elba, 2001.
D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344 (A_n for s=2).
Vera Posch, Correlators in Matrix Models, Master Thesis, Uppsala Univ. (Sweden 2023). See p. 44.
John Riordan, Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences. Note that the sequences are identified by their N-numbers, not their A-numbers.
W. T. Tutte, On the enumeration of planar maps. Bull. Amer. Math. Soc. 74 1968 64-74.
T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus, J. Comb. Thy B13 (1972), 122-141 and 192-218 (eq. 5, b=1).
N. J. A. Sloane, Notes
FORMULA
G.f.: c(x)/(1-4x), c(x) = g.f. of Catalan numbers.
Convolution of Catalan numbers and powers of 4.
Also one half of convolution of central binomial coeffs. A000984(n), n=0, 1, 2, ... with shifted central binomial coeffs. A000984(n), n=1, 2, 3, ...
a(n) = Sum_{k=0..n+1} binomial(n+k, k-1)2^(n-k+1). - Paul Barry, Nov 13 2004
a(n) = Sum_{i=0..n} binomial(2n+2, i). See A008949. - Ed Catmur (ed(AT)catmur.co.uk), Dec 09 2006
a(n) = Sum_{k=0..n+1, C(2n+2,k)} - C(2n+2,n+1). - Paul Barry, Jan 21 2007
Logarithm g.f. log(1/(2-C(x)))=sum(n>0, a(n)/n*x^n), C(x)=(1-sqrt(1-4*x))/2x (A000108). - Vladimir Kruchinin, Aug 10 2010
D-finite with recurrence: (n+3) a(n+2) - 2(4n+9) a(n+1) + 8(2n+3) a(n) = 0. - Emanuele Munarini, Mar 16 2011
E.g.f.:exp(2*x)*(2*exp(2*x) - BesselI(0,2*x) - BesselI(1,2*x)).
This is the first derivative of exp(2*x)*(exp(2*x) - BesselI(0,2*x))/2. See the e.g.f. of A032443 (which has a plus sign) and the remarks given there. - Wolfdieter Lang, Jan 16 2012
a(n) = Sum_{0<=i<j<=n+1} binomial(n+1, i)*binomial(n+1, j). - Mircea Merca, Apr 05 2012
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>-5. - Michael Somos, Jan 25 2014
REVERT transform is [1,-5,28,-168,1056,...] = alternating signed version of A069731. - Michael Somos, Jan 25 2014
Convolution square is A038806. - Michael Somos, Jan 25 2014
BINOMIAL transform of A055217(n-1) is a(n-1). - Michael Somos, Jan 25 2014
(n+1) * a(n) = A033504(n). - Michael Somos, Jan 25 2014
Recurrence: (n+1)*a(n) = 512*(2*n-7)*a(n-5) + 256*(13-5*n)*a(n-4) + 64*(10*n-17)*a(n-3) + 32*(4-5*n)*a(n-2) + 2*(10*n+1)*a(n-1), n>=5. - Fung Lam, Mar 21 2014
Asymptotic approximation: a(n) ~ 2^(2n+1)*(1-1/sqrt(n*Pi)). - Fung Lam, Mar 21 2014
a(n) = Sum_{m = n+2..2*(n+1)} binomial(2*(n+1), m), n >= 0. - Wolfdieter Lang, May 22 2015
a(n) = Sum_{j=1..n+1} Sum_{k=1..j} 2^(j-k)*binomial(n+k-1, n). - Fabio Visonà, May 04 2022
a(n) = (1/2)*(-1)^n*binomial(-(n+1), n+2)*hypergeom([1, 2*n + 3], [n + 3], 1/2). - Peter Luschny, Nov 29 2023
EXAMPLE
G.f. = 1 + 5*x + 22*x^2 + 93*x^3 + 386*x^4 + 1586*x^5 + 6476*x^6 + ...
MAPLE
seq(2^(2*n+1)-binomial(2*n, n)*(2*n+1)/(n+1), n=0..12); # Emanuele Munarini, Mar 16 2011
MATHEMATICA
Table[2^(2n+1)-Binomial[2n, n](2n+1)/(n+1), {n, 0, 20}] (* Emanuele Munarini, Mar 16 2011 *)
a[ n_] := If[ n<-4, 0, (4^(n + 1) - Binomial[2 n + 2, n + 1]) / 2]; (* Michael Somos, Jan 25 2014 *)
PROG
(PARI) {a(n) = if( n<-4, 0, n++; (2^(2*n) - binomial(2*n, n)) / 2)}; /* Michael Somos, Jan 25 2014 */
(Maxima) makelist(2^(2*n+1)-binomial(2*n, n)*(2*n+1)/(n+1), n, 0, 12); /* Emanuele Munarini, Mar 16 2011 */
(Magma) [2^(2*n+1) - Binomial(2*n+1, n+1): n in [0..30]]; // Vincenzo Librandi, Jun 07 2011
CROSSREFS
Even bisection of A294175 (without the first two terms).
The following relate to compositions of 2n with alternating sum k.
- The k > 0 case is counted by A000302.
- The k <= 0 case is counted by A000302.
- The k != 0 case is counted by A000346 (this sequence).
- The k < 0 case is counted by A008549.
- The k >= 0 case is counted by A114121.
A011782 counts compositions.
A097805 counts compositions by alternating (or reverse-alternating) sum.
A345197 counts compositions by length and alternating sum.
KEYWORD
nonn,easy
AUTHOR
EXTENSIONS
Corrected by Christian G. Bower
STATUS
approved