A068551 a(n) = 4^n - binomial(2*n,n).

0, 2, 10, 44, 186, 772, 3172, 12952, 52666, 213524, 863820, 3488872, 14073060, 56708264, 228318856, 918624304, 3693886906, 14846262964, 59644341436, 239532643144, 961665098956, 3859788636664, 15488087080696, 62135313450064

Offset

0,2

Comments

Number of rooted two-face n-edge maps in the plane (planar with a distinguished outside face). - Valery A. Liskovets, Mar 17 2005

Total number of returns to the x axis in all lattice paths using steps (1,1) and (1,-1) from the origin to (2n,0). Cf. A108747. - Geoffrey Critzer, Jan 30 2012

Total depth of all leaves in all binary trees on 2n+1 nodes. - Marko Riedel, Sep 10 2016

References

H. W. Gould, Combinatorial Identities, Morgantown, WV, 1972. p. 32.

Hojoo Lee, Posting to Number Theory List, Feb 18 2002.

V. A. Liskovets and T. R. Walsh, Enumeration of unrooted maps on the plane, Rapport technique, UQAM, No. 2005-01, Montreal, Canada, 2005.

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..175

Dennis E. Davenport, Lara K. Pudwell, Louis W. Shapiro, and Leon C. Woodson, The Boundary of Ordered Trees, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.8.

Nicolle González, Pamela E. Harris, Gordon Rojas Kirby, Mariana Smit Vega Garcia, and Bridget Eileen Tenner, Pinnacle sets of signed permutations, arXiv:2301.02628 [math.CO], 2023.

Guo-Niu Han, Enumeration of Standard Puzzles, 2011. [Cached copy]

Guo-Niu Han, Enumeration of Standard Puzzles, arXiv:2006.14070 [math.CO], 2020.

Marko R. Riedel,  Average depth of a leaf in a binary tree, Math.Stackexchange.com.

V. A. Liskovets and T. R. Walsh, Counting unrooted maps on the plane, Advances in Applied Math., 36(4) (2006), 364-387.

Formula

G.f.: 1/(1 - 4*x) - 1/sqrt(1 - 4*x) = C(x)*2*x/(1 - 4*x) where C(x) = g.f. for Catalan numbers A000108.

a(n) = Sum_{k >= 1} binomial(2*m-2*k, m-k) * binomial(2*k, k).

a(n+1) = 4*a(n) + 2*C(n), where C(n) = Catalan numbers.

a(n) = 2*A000346(n-1) for n > 0.

a(n) = A045621(2*n).

Conjecture: n*a(n) + 2*(3-4*n)*a(n-1) + 8*(2*n-3)*a(n-2) = 0. - R. J. Mathar, Apr 01 2012

Recurrence (an alternative): n*a(n) = 2^9*(2*n - 9)*a(n-5) + 2^8*(18 - 5*n)*a(n-4) + 2^6*(10*n - 27)*a(n-3) + 2^5*(9 - 5*n)*a(n-2) + 2*(10*n - 9)*a(n-1), n >= 5. - Fung Lam, Mar 22 2014

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

E.g.f.: (exp(2*x) - BesselI(0, 2*x))*exp(2*x). - Ilya Gutkovskiy, Sep 10 2016

a(n) = (-1)^(n+1)*binomial(-n, n + 1)*hypergeom([1, 2*n + 1], [n + 2], 1/2). - Peter Luschny, Nov 29 2023

Maple

A068551:=n->4^n - binomial(2*n, n): seq(A068551(n), n=0..30); # Wesley Ivan Hurt, Mar 22 2014

Mathematica

nn=20; c=(1-(1-4x)^(1/2))/(2x); D[CoefficientList[ Series[ 1/(1-2y x c), {x, 0, nn}], x], y]/.y->1 (* Geoffrey Critzer, Jan 30 2012 *)

Prog

(PARI) a(n)=if(n<0, 0, 4^n-binomial(2*n, n))
(Magma) [4^n - Binomial(2*n, n): n in [0..35]]; // Vincenzo Librandi, Jun 07 2011
(PARI) x='x+O('x^100); concat(0, Vec(1/(1-4*x)-1/sqrt(1-4*x))) \\ Altug Alkan, Dec 29 2015

Crossrefs

Cf. A000108, A000346, A000984, A005470, A045621.

Sequence in context: A080069 A243965 A218780 * A099919 A100397 A084059

Adjacent sequences: A068548 A068549 A068550 * A068552 A068553 A068554

Keyword

nonn,easy

Author

N. J. A. Sloane, Mar 23 2002

Status

approved