login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000346 2^(2*n+1) - binomial(2*n+1, n+1).
(Formerly M3920 N1611)
27
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 (list; graph; refs; listen; history; text; internal format)
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

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

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.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 185

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

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.

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

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

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

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

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

Bisection of A058622 and (possibly) A007008.

Cf. A045621, A068551.

Cf. A033504, A038806, A055217, A069731.

Sequence in context: A010036 A127617 A095932 * A026672 A049652 A026877

Adjacent sequences:  A000343 A000344 A000345 * A000347 A000348 A000349

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane, Wolfdieter Lang

EXTENSIONS

Corrected by Christian G. Bower

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified August 22 11:20 EDT 2014. Contains 245954 sequences.