A003168 Number of blobs with 2n+1 edges. (Formerly M3574)

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

Offset

0,3

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

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.

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

Example

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

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 *)

Prog

(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
(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

Crossrefs

Cf. A049124 (no 2m-gons).

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

Row sums of A102537, A243662.

Sequence in context: A195262 A162480 A275758 * A211249 A185047 A353608

Adjacent sequences: A003165 A003166 A003167 * A003169 A003170 A003171

Keyword

nonn,easy,nice,changed

Author

N. J. A. Sloane

Status

approved