A003645 a(n) = 2^n * C(n+1), where C(n) = A000108(n) Catalan numbers.

1, 4, 20, 112, 672, 4224, 27456, 183040, 1244672, 8599552, 60196864, 426008576, 3042918400, 21909012480, 158840340480, 1158600130560, 8496400957440, 62605059686400, 463277441679360, 3441489566760960, 25654740406763520, 191852841302753280, 1438896309770649600

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• changed

Comments

Number of nonisomorphic unrooted unicursal planar maps with n+2 edges and exactly one vertex of valency 1 (unicursal means that exactly two vertices are of odd valency). - Valery A. Liskovets, Apr 07 2002

Total number of vertices in rooted Eulerian planar maps with n+1 edges.

Half the number of ways to dog-ear every page of an (n+1)-page book. - R. H. Hardin, Jun 21 2002

Convolution of A052701(n+1) with itself.

Number of Motzkin lattice paths with weights: 1 for up step, 4 for level step and 4 for down step. - Wenjin Woan, Oct 24 2004

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

Also the number of paths of length 2n+1 in a binary tree between two vertices that are one step away from each other. - David Koslicki (koslicki(AT)math.psu.edu), Nov 02 2010

2*a(n) for n > 1 is the number of increasing strict binary trees with 2n-1 nodes that simultaneously avoid 213 and 231 in the classical sense. For more information about increasing strict binary trees with an associated permutation, see A245894. - Manda Riehl, Aug 22 2014

References

• L. M. Koganov, V. A. Liskovets, T. R. S. Walsh, Total vertex enumeration in rooted planar maps, Ars Combin. 54 (2000), 149-160.
• V. A. Liskovets and T. R. Walsh, Enumeration of unrooted maps on the plane, Rapport technique, UQAM, No. 2005-01, Montreal, Canada, 2005.

Links

• A. Claesson, S. Kitaev and A. de Mier, An involution on bicubic maps and beta(0,1)-trees, arXiv preprint arXiv:1210.3219 [math.CO], 2012. - From _N. J. A. Sloane_, Jan 01 2013
• S. B. Ekhad and M. Yang, Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences, 2017.
• Samuele Giraudo, Pluriassociative algebras II: The polydendriform operad and related operads, arXiv:1603.01394 [math.CO], 2016.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 652.
• Anatol N. Kirillov, Notes on Schubert, Grothendieck and key polynomials, SIGMA, Symmetry Integrability Geom. Methods Appl. 12, Paper 034, 56 p. (2016).
• Huyile Liang, Jeffrey Remmel, and Sainan Zheng, Stieltjes moment sequences of polynomials, arXiv:1710.05795 [math.CO], 2017, see page 13.
• V. A. Liskovets and T. R. S. Walsh, Enumeration of Eulerian and unicursal planar maps, Discr. Math., Vol. 282, No. 1-3 (2004), pp. 209-221.
• V. A. Liskovets and T. R. Walsh, Counting unrooted maps on the plane, Advances in Applied Math., Vol. 36, No.4 (2006), pp. 364-387.
• Amya Luo, Pattern Avoidance in Nonnesting Permutations, Undergraduate Thesis, Dartmouth College (2024). See p. 11.
• Youngja Park and SeungKyung Park, Enumeration of generalized lattice paths by string types, peaks, and ascents, Discrete Mathematics, Vol. 339, No. 11 (2016), pp. 2652-2659.
• M. Z. Spivey and L. L. Steil, The k-Binomial Transforms and the Hankel Transform, J. Integ. Seq., Vol. 9 (2006), Article 06.1.1.

Crossrefs

Cf. A069724, A069725, A090375.

Third row of array A102539.

Column of array A073165.

Cf. A000108, A052701, A195699.

Programs

Magma

[2^n*Binomial(2*n+3, n+1)/(2*n+3) : n in [0..30]]; // Wesley Ivan Hurt, Aug 23 2014

Maple

A003645:=n->2^n*binomial(2*n+3, n+1)/(2*n+3): seq(A003645(n), n=0..30); # Wesley Ivan Hurt, Aug 23 2014

Mathematica

Table[2^n CatalanNumber[n+1],{n,0,20}] (* Harvey P. Dale, May 07 2013 *)

PARI

a(n)=if(n<0,0,2^n*(2*n+2)!/(n+1)!/(n+2)!)

Formula

a(n) = A052701(n+2)/2.

2*a(n) matches the odd-indexed terms of A090375.

a(n) = 2^n * binomial(2n+3, n+1) / (2n+3). - Len Smiley, Feb 24 2006

G.f.: (1-4x-sqrt(1-8x))/(8x^2) = C(2x)^2, where C(x) is the g.f. for Catalan numbers, A000108.

From Gary W. Adamson, Jul 12 2011: (Start)

Let M = the following production matrix:

2, 2, 0, 0, 0, ...

2, 2, 2, 0, 0, ...

2, 2, 2, 2, 0, ...

2, 2, 2, 2, 2, ...

...

a(n) = sum of top row terms in M^n. Example: top row of M^3 = (40, 40, 24, 8, 0, 0, 0, ...), sum = 112 = a(3). (End)

D-finite with recurrence (n+2)*a(n) - 4*(2n+1)*a(n-1) = 0. - R. J. Mathar, Apr 01 2012

E.g.f.: a(n) = n!* [x^n] exp(4*x)*BesselI(1, 4*x)/(2*x). - Peter Luschny, Aug 25 2012

Expansion of square of continued fraction 1/(1 - 2*x/(1 - 2*x/(1 - 2*x/(1 - ...)))). - Ilya Gutkovskiy, Apr 19 2017

From Amiram Eldar, Mar 06 2022: (Start)

Sum_{n>=0} 1/a(n) = 38/49 + 192*arcsin(sqrt(1/8))/(49*sqrt(7)).

Sum_{n>=0} (-1)^n/a(n) = 14/27 + 32*log(2)/81. (End)

a(n) = Product_{1 <= i <= j <= n} (i + j + 2)/(i + j - 1). Cf. A001700. - Peter Bala, Feb 22 2023