A006419 a(n) = 2^(2*n+1) - C(2*n+3,n+1) + C(2*n+1,n).

0, 1, 7, 37, 176, 794, 3473, 14893, 63004, 263950, 1097790, 4540386, 18696432, 76717268, 313889477, 1281220733, 5219170052, 21224674118, 86188320962, 349550141078, 1416102710912, 5731427140268, 23177285611082, 93655986978002, 378195990166136, 1526289367335244

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn

Comments

Number of rooted isthmusless planar maps with n+1 faces and 2 vertices. - Dan Drake, Aug 08 2005

a(n) = total area below all Dyck (n+1)-paths and above the lowest possible Dyck path, namely, UDUD...UD (taking upsteps of unit length). For example, the areas below the 5 Dyck 3-paths UUUDDD, UUDUDD, UDUUDD, UUDDUD, UDUDUD are 3,2,1,1,0 respectively, yielding a(2)=3+2+1+1+0=7. - David Callan, Jul 03 2006

Convolution of A000245 and A000302 (powers of 4).- Philippe Deléham, Jun 02 2013

Examples

			G.f. = x + 7*x^2 + 37*x^3 + 176*x^4 + 794*x^5 + 3473*x^6 + 14893*x^7 + 63004*x^8 + ...
		

References

• D. Phulara and L. W. Shapiro, Descendants in ordered trees with a marked vertex, Congressus Numerantium, 205 (2011), 121-128.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..1660
• Jason Bandlow and Kendra Killpatrick, An area-to-inv bijection between Dyck paths and 312-avoiding permutations,Electron. J. Combin. 8 (2001), no. 1, Research Paper 40, 16 pp.
• Miklós Bóna, Surprising Symmetries in Objects Counted by Catalan Numbers, Electronic J. Combin., 19 (2012), #P62, eq. (5).
• Pudwell, Lara; Scholten, Connor; Schrock, Tyler; Serrato, Alexa Noncontiguous pattern containment in binary trees, ISRN Comb. 2014, Article ID 316535, 8 p. (2014), Table 1.
• R. P. Stanley, F. Zanello, The Catalan case of Armstrong's conjecture on core partitions, arXiv preprint arXiv:1312.4352 [math.CO], 2013.
• T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus. III: Nonseparable maps, J. Combinatorial Theory Ser. B 18 (1975), 222-259.

Crossrefs

A diagonal of A342981.

Cf. A386612, A386614, A386616, A386617.

Programs

Maple

f := n->2^(2*n+1)-binomial(2*n+3,n+1)+binomial(2*n+1,n); seq(f(n), n=0..30);

Mathematica

Table[2^(2 n + 1) - Binomial[2 n + 3, n + 1] +
Binomial[2 n + 1, n], {n, 0, 30}] (* Wesley Ivan Hurt, Mar 30 2014 *)

Maxima

a(n):=sum(binomial(2*(n+1),n-k-1),k,0,n); /* Vladimir Kruchinin, Oct 23 2016 */

Formula

a(n+1) = Sum_{k=0..n} (n-k)*A000108(n-k)*A001700(k). - Philippe Deléham, Jan 25 2004

G.f.: c(x)^3*x/(1-4x) where c(x) = g.f. for the Catalan numbers A000108. - Philippe Deléham, Jun 02 2013

a(n) = Integral_{x=0..4} x^n*W(x)*dx, n >= 0, is the integral representation as n-th moment of a signed weight function W(x), where W(x) = W_a(x) + W_c(x), with W_a(x) = 2*Dirac(x-4), which is the discrete (atomic) part, and W_c(x) = (1/(2*Pi))*(1-x)*sqrt(x/(4-x)) is the continuous part of W(x): W_c(0) = W_c(1) = 0, W_c(x) > 0 for x < 1, lim_{x->4} W_c(x) = -oo. - Karol A. Penson, Jul 31 2013 [edited by Michel Marcus, Mar 14 2020]

(n+2)*a(n) + (-9*n-10)*a(n-1) + 2*(12*n+1)*a(n-2) + 8*(-2*n+3)*a(n-3) = 0. - R. J. Mathar, Mar 30 2014

a(n) = Sum_{k=0..n} binomial(2*(n+1), n-k-1). - Vladimir Kruchinin, Oct 23 2016

0 = a(n)*(+256*a(n+1) - 992*a(n+2) + 520*a(n+3) - 72*a(n+4)) + a(n+1)*(+224*a(n+1) + 344*a(n+2) - 398*a(n+3) + 70*a(n+4)) + a(n+2)*(+6*a(n+2) + 59*a(n+3) - 17*a(n+4)) + a(n+3)*(-a(n+3) + a(n+4)), for all n >= 0. - Michael Somos, Oct 23 2016

a(n) = [x^n] x/((1 - 2*x)*(1 - x)^(n+3)). - Ilya Gutkovskiy, Oct 25 2017

From Seiichi Manyama, Jul 29 2025: (Start)

a(n) = Sum_{k=0..n-1} binomial(2*k+1+l,k) * binomial(2*n-2*k-l,n-k-1) for every real number l.

a(n) = Sum_{k=0..n-1} 2^(n-k-1) * binomial(n+k+2,k). (End)