|
%I #87 Nov 29 2023 11:42:16
%S 0,2,10,44,186,772,3172,12952,52666,213524,863820,3488872,14073060,
%T 56708264,228318856,918624304,3693886906,14846262964,59644341436,
%U 239532643144,961665098956,3859788636664,15488087080696,62135313450064
%N a(n) = 4^n - binomial(2*n,n).
%C Number of rooted two-face n-edge maps in the plane (planar with a distinguished outside face). - _Valery A. Liskovets_, Mar 17 2005
%C 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
%C Total depth of all leaves in all binary trees on 2n+1 nodes. - _Marko Riedel_, Sep 10 2016
%D H. W. Gould, Combinatorial Identities, Morgantown, WV, 1972. p. 32.
%D Hojoo Lee, Posting to Number Theory List, Feb 18 2002.
%D V. A. Liskovets and T. R. Walsh, Enumeration of unrooted maps on the plane, Rapport technique, UQAM, No. 2005-01, Montreal, Canada, 2005.
%H Vincenzo Librandi, <a href="/A068551/b068551.txt">Table of n, a(n) for n = 0..175</a>
%H Dennis E. Davenport, Lara K. Pudwell, Louis W. Shapiro, and Leon C. Woodson, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Davenport/dav3.html">The Boundary of Ordered Trees</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.8.
%H Nicolle González, Pamela E. Harris, Gordon Rojas Kirby, Mariana Smit Vega Garcia, and Bridget Eileen Tenner, <a href="https://arxiv.org/abs/2301.02628">Pinnacle sets of signed permutations</a>, arXiv:2301.02628 [math.CO], 2023.
%H Guo-Niu Han, <a href="/A196265/a196265.pdf">Enumeration of Standard Puzzles</a>, 2011. [Cached copy]
%H Guo-Niu Han, <a href="https://arxiv.org/abs/2006.14070">Enumeration of Standard Puzzles</a>, arXiv:2006.14070 [math.CO], 2020.
%H Marko R. Riedel, <a href="http://math.stackexchange.com/questions/1920118/">Average depth of a leaf in a binary tree</a>, Math.Stackexchange.com.
%H V. A. Liskovets and T. R. Walsh, <a href="http://dx.doi.org/10.1016/j.aam.2005.03.006">Counting unrooted maps on the plane</a>, Advances in Applied Math., 36(4) (2006), 364-387.
%F 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.
%F a(n) = Sum_{k >= 1} binomial(2*m-2*k, m-k) * binomial(2*k, k).
%F a(n+1) = 4*a(n) + 2*C(n), where C(n) = Catalan numbers.
%F a(n) = 2*A000346(n-1) for n > 0.
%F a(n) = A045621(2*n).
%F 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
%F 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
%F Asymptotics: a(n) ~ 2^(2*n)*(1 - 1/sqrt(n*Pi)). - _Fung Lam_, Mar 22 2014
%F E.g.f.: (exp(2*x) - BesselI(0, 2*x))*exp(2*x). - _Ilya Gutkovskiy_, Sep 10 2016
%F a(n) = (-1)^(n+1)*binomial(-n, n + 1)*hypergeom([1, 2*n + 1], [n + 2], 1/2). - _Peter Luschny_, Nov 29 2023
%p A068551:=n->4^n - binomial(2*n,n): seq(A068551(n), n=0..30); # _Wesley Ivan Hurt_, Mar 22 2014
%t 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 *)
%o (PARI) a(n)=if(n<0,0,4^n-binomial(2*n,n))
%o (Magma) [4^n - Binomial(2*n,n): n in [0..35]]; // _Vincenzo Librandi_, Jun 07 2011
%o (PARI) x='x+O('x^100); concat(0, Vec(1/(1-4*x)-1/sqrt(1-4*x))) \\ _Altug Alkan_, Dec 29 2015
%Y Cf. A000108, A000346, A000984, A005470, A045621.
%K nonn,easy
%O 0,2
%A _N. J. A. Sloane_, Mar 23 2002
|
