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

Author

N. J. A. Sloane, Mar 23 2002

Keywords

• nonn
• easy

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.

Crossrefs

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

Programs

Magma

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

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

PARI

a(n)=if(n<0,0,4^n-binomial(2*n,n))

PARI

x='x+O('x^100); concat(0, Vec(1/(1-4*x)-1/sqrt(1-4*x))) \\ Altug Alkan, Dec 29 2015

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