|
|
A068551
|
|
a(n) = 4^n - binomial(2*n,n).
|
|
4
|
|
|
0, 2, 10, 44, 186, 772, 3172, 12952, 52666, 213524, 863820, 3488872, 14073060, 56708264, 228318856, 918624304, 3693886906, 14846262964, 59644341436, 239532643144, 961665098956, 3859788636664, 15488087080696, 62135313450064
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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, Leon C. Woodson, The Boundary of Ordered Trees, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.8.
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
|
|
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
|
|
|
|