A003168 Number of blobs with 2n+1 edges.

1, 1, 4, 21, 126, 818, 5594, 39693, 289510, 2157150, 16348960, 125642146, 976789620, 7668465964, 60708178054, 484093913917, 3884724864390, 31348290348086, 254225828706248, 2070856216759478, 16936016649259364

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

a(n) is the number of ways to dissect a convex (2n+2)-gon with non-crossing diagonals so that no (2m+1)-gons (m>0) appear. - Len Smiley

a(n) is the number of plane trees with 2n+1 leaves and all non-leaves having an odd number > 1 of children. - Jordan Tirrell, Jun 09 2017

a(n) is the number of noncrossing cacti with n+1 nodes. See A361242. - Andrew Howroyd, Mar 07 2023

Examples

			a(2)=4 because we may place exactly one diagonal in 3 ways (forming 2 quadrilaterals), or not place any (leaving 1 hexagon).
		

References

• 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..1000 (terms 0..100 from T. D. Noe)
• Thomas H. Bertschinger, Joseph Slote, Olivia Claire Spencer, and Samuel Vinitsky, The Mathematics of Origami, Undergrad Thesis, Carleton College (2016).
• D. Birmajer, J. B. Gil, and M. D. Weiner, Colored partitions of a convex polygon by noncrossing diagonals, arXiv preprint arXiv:1503.05242 [math.CO], 2015.
• L. Carlitz, Enumeration of two-line arrays, Fib. Quart., Vol. 11 Number 2 (1973), 113-130.
• Frédéric Chapoton and Philippe Nadeau, Combinatorics of the categories of noncrossing partitions, Séminaire Lotharingien de Combinatoire 78B (2017), Article #37.
• Michael Drmota, Anna de Mier, and Marc Noy, Extremal statistics on non-crossing configurations, Discrete Math. 327 (2014), 103--117. MR3192420. See p. 116, B_b(z). - N. J. A. Sloane, May 18 2014
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 415
• Elżbieta Liszewska and Wojciech Młotkowski, Some relatives of the Catalan sequence, arXiv:1907.10725 [math.CO], 2019.
• Jean-Christophe Novelli and Jean-Yves Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962 [math.CO], 2014.
• Jean-Christophe Novelli and Jean-Yves Thibon, Noncommutative Symmetric Functions and Lagrange Inversion II: Noncrossing partitions and the Farahat-Higman algebra, arXiv:2106.08257 [math.CO], 2021-2022.
• Ronald C. Read, On the enumeration of a class of plane multigraphs, Aequat. Math. 31 (1986) No. 1, 47-63.
• L. Smiley, Even-gon reference
• Jun Yan, Results on pattern avoidance in parking functions, arXiv:2404.07958 [math.CO], 2024. See p. 30.

Crossrefs

Cf. A049124 (no 2m-gons).

Cf. A003169, A100327, A114496, A007318, A361242.

Row sums of A102537, A243662. Column 2 of A336573.

Programs

Haskell

import Data.List (transpose)
a003168 0 = 1
a003168 n = sum (zipWith (*)
   (tail $ a007318_tabl !! n)
   ((transpose $ take (3*n+1) a007318_tabl) !! (2*n+1)))
   `div` fromIntegral n
-- Reinhard Zumkeller, Oct 27 2013

Maple

Order := 40; solve(series((A-2*A^3)/(1-A^2),A)=x,A);
A003168 := n -> `if`(n=0,1,A100327(n)/2): seq(A003168(n),n=0..20); # Peter Luschny, Jun 10 2017

Mathematica

a[0] = 1; a[n_] = (2^(-n-1)*(3n)!* Hypergeometric2F1[-1-2n, -2n, -3n, -1])/((2n+1)* n!*(2n)!); Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jul 25 2011, after Vladimir Kruchinin *)

PARI

a(n)=if(n<0,0,polcoeff(serreverse((x-2*x^3)/(1-x^2)+O(x^(2*n+2))),2*n+1))

PARI

{a(n)=local(A=1+x+x*O(x^n));for(i=1,n,A=(1+x*A)/(1-x*A)^2); sum(k=0,n,polcoeff(A^(n-k),k))} \\ Paul D. Hanna, Nov 17 2004

PARI

seq(n) = Vec( 1 + serreverse(x/((1+2*x)*(1+x)^2) + O(x*x^n)) ) \\ Andrew Howroyd, Mar 07 2023

Formula

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

G.f.: A(x) = Sum_{n>=0} a(n)*x^(2*n+1) satisfies (A-2*A^3)/(1-A^2)=x. - Len Smiley.

D-finite with recurrence 4*n*(2*n + 1)*(17*n - 22)*a(n) = (1207*n^3 - 2769*n^2 + 1850*n - 360)*a(n - 1) - 2*(17*n - 5)*(n - 2)*(2*n - 3)*a(n - 2). - Vladeta Jovovic, Jul 16 2004

G.f.: A(x) = 1/(1-G003169(x)) where G003169(x) is the g.f. of A003169. - Paul D. Hanna, Nov 17 2004

a(n) = JacobiP(n-1,1,n+1,3)/n for n > 0. - Mark van Hoeij, Jun 02 2010

a(n) = (1/(2*n+1))*Sum_{j=0..n} (-1)^j*2^(n-j)*binomial(2*n+1,j)*binomial(3*n-j,2*n). - Vladimir Kruchinin, Dec 24 2010

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

a(n) = upper left term in M^n, M = the production matrix:

1, 1

3, 3, 1

5, 5, 3, 1

7, 7, 5, 3, 1

9, 9, 7, 5, 3, 1

... (End)

a(n) ~ sqrt(14+66/sqrt(17)) * (71+17*sqrt(17))^n / (sqrt(Pi) * n^(3/2) * 2^(4*n+4)). - Vaclav Kotesovec, Jul 01 2015

From Peter Bala, Oct 05 2015: (Start)

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

O.g.f. = 1 + series reversion( x/((1 + 2*x)*(1 + x)^2) ).

Logarithmically differentiating the modified g.f. 1 + 4*x + 21*x^2 + 126*x^3 + 818*x^4 + ... gives the o.g.f. for A114496, apart from the initial term. (End)

G.f.: A(x) satisfies A = 1 + x*A^3/(1-x*A^2). - Jordan Tirrell, Jun 09 2017

a(n) = A100327(n)/2 for n>=1. - Peter Luschny, Jun 10 2017