A000346 a(n) = 2^(2*n+1) - binomial(2*n+1, n+1).

1, 5, 22, 93, 386, 1586, 6476, 26333, 106762, 431910, 1744436, 7036530, 28354132, 114159428, 459312152, 1846943453, 7423131482, 29822170718, 119766321572, 480832549478, 1929894318332, 7744043540348, 31067656725032, 124613686513778, 499744650202436

Offset: 0

Author

N. J. A. Sloane, Wolfdieter Lang

Keywords

• nonn
• easy

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)

Examples

			G.f. = 1 + 5*x + 22*x^2 + 93*x^3 + 386*x^4 + 1586*x^5 + 6476*x^6 + ...
		

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

Crossrefs

Cf. A000108, A014137, A014318. A column of A058893. Subdiagonal of A053979.

Bisection of A058622 and (possibly) A007008.

Cf. A045621, A068551.

Cf. A033504, A038806, A055217, A069731.

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 A001700 or A088218.

- The k < 0 case is counted by A008549.

- The k >= 0 case is counted by A114121.

A011782 counts compositions.

A086543 counts partitions with nonzero alternating sum (bisection: A182616).

A097805 counts compositions by alternating (or reverse-alternating) sum.

A103919 counts partitions by sum and alternating sum (reverse: A344612).

A345197 counts compositions by length and alternating sum.

Cf. A000070, A001791, A007318, A025047, A027306, A032443, A053754, A120452, A163493, A239830, A344611, A345921.

Programs

Magma

[2^(2*n+1) - Binomial(2*n+1,n+1): n in [0..30]]; // Vincenzo Librandi, Jun 07 2011

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

Maxima

makelist(2^(2*n+1)-binomial(2*n,n)*(2*n+1)/(n+1),n,0,12); /* Emanuele Munarini, Mar 16 2011 */

PARI

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

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) = A045621(2n+1) = (1/2)*A068551(n+1).

a(n) = Sum_{k=0..n} A000984(k)*A001700(n-k). - Philippe Deléham, Jan 22 2004

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<=iMircea Merca, Apr 05 2012

A000346 = A004171 - A001700. See A032443 for the sum. - 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>-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) = A000302(n) + A008549(n). - Gus Wiseman, Jul 19 2021

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

Extensions

Corrected by Christian G. Bower