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

%I #107 Jun 13 2024 11:39:06

%S 1,4,20,112,672,4224,27456,183040,1244672,8599552,60196864,426008576,

%T 3042918400,21909012480,158840340480,1158600130560,8496400957440,

%U 62605059686400,463277441679360,3441489566760960,25654740406763520,191852841302753280,1438896309770649600

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

%C 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

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

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

%C Convolution of A052701(n+1) with itself.

%C 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

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

%C 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

%C 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

%D L. M. Koganov, V. A. Liskovets, T. R. S. Walsh, Total vertex enumeration in rooted planar maps, Ars Combin. 54 (2000), 149-160.

%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 A. Claesson, S. Kitaev and A. de Mier, <a href="http://arxiv.org/abs/1210.3219">An involution on bicubic maps and beta(0,1)-trees</a>, arXiv preprint arXiv:1210.3219 [math.CO], 2012. - From _N. J. A. Sloane_, Jan 01 2013

%H S. B. Ekhad and M. Yang, <a href="http://sites.math.rutgers.edu/~zeilberg/tokhniot/oMathar1maple12.txt">Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences</a>, 2017.

%H Samuele Giraudo, <a href="http://arxiv.org/abs/1603.01394">Pluriassociative algebras II: The polydendriform operad and related operads</a>, arXiv:1603.01394 [math.CO], 2016.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=652">Encyclopedia of Combinatorial Structures 652</a>.

%H Anatol N. Kirillov, <a href="https://doi.org/10.3842/SIGMA.2016.034">Notes on Schubert, Grothendieck and key polynomials</a>, SIGMA, Symmetry Integrability Geom. Methods Appl. 12, Paper 034, 56 p. (2016).

%H Huyile Liang, Jeffrey Remmel, Sainan Zheng, <a href="https://arxiv.org/abs/1710.05795">Stieltjes moment sequences of polynomials</a>, arXiv:1710.05795 [math.CO], 2017, see page 13.

%H V. A. Liskovets and T. R. S. Walsh, <a href="http://dx.doi.org/10.1016/j.disc.2003.09.015">Enumeration of Eulerian and unicursal planar maps</a>, Discr. Math., Vol. 282, No. 1-3 (2004), pp. 209-221.

%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., Vol. 36, No.4 (2006), pp. 364-387.

%H Amya Luo, <a href="https://math.dartmouth.edu/theses/undergrad/2024/Luo-thesis.pdf">Pattern Avoidance in Nonnesting Permutations</a>, Undergraduate Thesis, Dartmouth College (2024). See p. 11.

%H Youngja Park and SeungKyung Park, <a href="https://doi.org/10.1016/j.disc.2016.04.024">Enumeration of generalized lattice paths by string types, peaks, and ascents</a>, Discrete Mathematics, Vol. 339, No. 11 (2016), pp. 2652-2659.

%H M. Z. Spivey and L. L. Steil, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Spivey/spivey7.html"> The k-Binomial Transforms and the Hankel Transform</a>, J. Integ. Seq., Vol. 9 (2006), Article 06.1.1.

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

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

%F a(n) = 2^n * binomial(2n+3, n+1) / (2n+3). - _Len Smiley_, Feb 24 2006

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

%F From _Gary W. Adamson_, Jul 12 2011: (Start)

%F Let M = the following production matrix:

%F 2, 2, 0, 0, 0, ...

%F 2, 2, 2, 0, 0, ...

%F 2, 2, 2, 2, 0, ...

%F 2, 2, 2, 2, 2, ...

%F ...

%F 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)

%F D-finite with recurrence (n+2)*a(n) - 4*(2n+1)*a(n-1) = 0. - _R. J. Mathar_, Apr 01 2012

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

%F Expansion of square of continued fraction 1/(1 - 2*x/(1 - 2*x/(1 - 2*x/(1 - ...)))). - _Ilya Gutkovskiy_, Apr 19 2017

%F From _Amiram Eldar_, Mar 06 2022: (Start)

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

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

%F a(n) = Product_{1 <= i <= j <= n} (i + j + 2)/(i + j - 1). Cf. A001700. - _Peter Bala_, Feb 22 2023

%p 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

%t Table[2^n CatalanNumber[n+1],{n,0,20}] (* _Harvey P. Dale_, May 07 2013 *)

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

%o (Magma) [2^n*Binomial(2*n+3, n+1)/(2*n+3) : n in [0..30]]; // _Wesley Ivan Hurt_, Aug 23 2014

%Y Cf. A069724, A069725, A090375.

%Y Third row of array A102539.

%Y Column of array A073165.

%Y Cf. A000108, A052701, A195699.

%K nonn,easy

%O 0,2

%A _N. J. A. Sloane_