A361242 -id:A361242 - cp's OEIS frontend

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

N. J. A. Sloane

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

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

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

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.

Cf. A049124 (no 2m-gons).
Cf. A003169, A100327, A114496, A007318, A361242.
Row sums of A102537, A243662. Column 2 of A336573.

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

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

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

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

{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

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

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

A361245 Number of noncrossing 2,3 cacti with n nodes.

Original entry on oeis.org

1, 1, 1, 4, 20, 115, 715, 4683, 31824, 222300, 1586310, 11514030, 84742320, 630946446, 4743789260, 35965715780, 274659794160, 2110810059795, 16312695488265, 126693445737170, 988340783454380, 7740875273884445, 60846920004855985, 479854293574853085

Offset: 0

Andrew Howroyd, Mar 08 2023

nonn

A 2,3 cactus is a cactus composed of bridges and triangles.

Andrew Howroyd, Table of n, a(n) for n = 0..500
Wikipedia, Cactus graph.
Index entries for sequences related to cacti.

Cf. A091481, A091485, A091486, A091487, A361242, A361244.

seq(n) = Vec(1 + x/(1 - serreverse((sqrt(1 + 4*x + O(x^n)) - 1)*(1 - x)^2/2)))

A361236 Array read by antidiagonals: T(n,k) is the number of noncrossing k-gonal cacti with n polygons up to rotation.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 5, 11, 1, 1, 1, 1, 8, 33, 49, 1, 1, 1, 1, 9, 63, 230, 204, 1, 1, 1, 1, 12, 105, 664, 1827, 984, 1, 1, 1, 1, 13, 159, 1419, 7462, 15466, 4807, 1, 1, 1, 1, 16, 221, 2637, 21085, 90896, 137085, 24739, 1

Offset: 0

Andrew Howroyd, Mar 05 2023

The number of noncrossing k-gonal cacti is given by column 2*(k-1) of A070914. This sequence enumerates these cacti with rotations being considered equivalent.
Equivalently, T(n,k) is the number of connected acyclic k-uniform noncrossing antichains with n blocks covering (k-1)*n+1 nodes where the intersection of two blocks is at most 1 node modulo cyclic rotation of the nodes.
Noncrossing trees correspond to the case of k = 2.

			=====================================================
n\k | 1     2       3        4        5         6 ...
----+------------------------------------------------
  0 | 1     1       1        1        1         1 ...
  1 | 1     1       1        1        1         1 ...
  2 | 1     1       1        1        1         1 ...
  3 | 1     4       5        8        9        12 ...
  4 | 1    11      33       63      105       159 ...
  5 | 1    49     230      664     1419      2637 ...
  6 | 1   204    1827     7462    21085     48048 ...
  7 | 1   984   15466    90896   334707    941100 ...
  8 | 1  4807  137085  1159587  5579961  19354687 ...
  9 | 1 24739 1260545 15369761 96589350 413533260 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (first 51 antidiagonals).
Wikipedia, Cactus graph.
Index entries for sequences related to cacti.

Columns k=1..4 are A000012, A296532, A361237, A361238.
Row n=3 is A042948.
Cf. A070914, A303694, A303912, A361239, A361242.

\\ here u is Fuss-Catalan sequence with p = 2*k-1.
u(n,k,r) = {r*binomial(n*(2*k-1) + r, n)/(n*(2*k-1) + r)}
T(n,k) = if(n==0, 1, u(n, k, 1)/((k-1)*n+1) + sumdiv(gcd(k,n-1), d, if(d>1, eulerphi(d)*u((n-1)/d, k, 2*k/d)/k)))

T(0,k) = T(1,k) = T(2,k) = 1.

A243662 Triangle read by rows: the reversed x = 1+q Narayana triangle at m=2.

Original entry on oeis.org

1, 3, 1, 12, 8, 1, 55, 55, 15, 1, 273, 364, 156, 24, 1, 1428, 2380, 1400, 350, 35, 1, 7752, 15504, 11628, 4080, 680, 48, 1, 43263, 100947, 92169, 41895, 9975, 1197, 63, 1, 246675, 657800, 708400, 396704, 123970, 21560, 1960, 80, 1, 1430715, 4292145, 5328180, 3552120, 1381380, 318780, 42504, 3036, 99, 1

Offset: 1

N. J. A. Sloane, Jun 13 2014

See Novelli-Thibon (2014) for precise definition.
From Tom Copeland, Dec 13 2022: (Start)
The row polynomials are the nonvanishing numerator polynomials generated in the compositional, or Lagrange, inversion in x about the origin of the odd o.g.f. Od1(x,t) = x*(t*(1-x^2)-x^2) / (1-x^2) = t*x - x^3 - x^5 - x^7 - x^9 - ... .
For example, from the Lagrange inversion formula (LIF), the tenth derivative in x of (x/Od1(x,t))^11 / 11! = (1/((t*(1-x^2)-x^2) / (1-x^2)))^11 / 11! at x = 0 is (t^4 + 24*t^3 + 156*t^2 + 364*t + 273) / t^16. These polynomials are also generated by the iterated derivatives ((1/(D Od1(x,t)) D)^n g(x) evaluated at x = 0 where D = d/dx.
An explicit generating function for the polynomials can be obtained by finding the solution of the cubic equation y - t*x - y*x^2 + (1+t)*x^3 = 0 for x in terms of y and t that satisfies y(x=0;t) = 0 = x(y=0;t).
The row polynomials are also the polynomials generated in the compositional inverse of O(x,t) = x / (1+(1+t)x)*(1+x)^2) = x + (-t - 3)*x^2 + (t^2 + 4 t + 6)*x^3 + (-t^3 - 5*t^2 - 10*t - 10)*x^4 + ..., containing the truncated Pascal polynomials of A104712 / A325000.
For example, from the LIF, the third derivative of ((1 + (1+t)*x)*(1+x)^2)^4 / 4! at x = 0 is 55 + 55*t + 15*t^2 + t^3.
A natural refinement of this array was provided in a letter by Isaac Newton in 1676--a set of partition polynomials for generating the o.g.f. of the compositional inverse of the generic odd o.g.f. x + u_1 x^3 + u_2 x^5 + ... in the infinite set of indeterminates u_n. (End)
T(n,k) is the number of noncrossing cacti with n+1 nodes and n+1-k blocks. See A361242. - Andrew Howroyd, Apr 13 2023

			Triangle begins:
     1;
     3,    1;
    12,    8,    1;
    55,   55,   15,   1;
   273,  364,  156,  24,  1;
  1428, 2380, 1400, 350, 35, 1;
  ...

Michael De Vlieger, Table of n, a(n) for n = 1..11325 (rows 1 <= n <= 150, flattened)
Paul Barry, On the inversion of Riordan arrays, arXiv:2101.06713 [math.CO], 2021.
J.-C. Novelli and J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962 [math.CO], 2014. See Fig. 10.

Cf. A001764, A001263, A243663 (m=3).
Row sums give A003168.
Row reversed triangle is A102537.

T[m_][n_, k_] := Binomial[(m + 1) n + 1 - k, n - k] Binomial[n, k - 1]/n;
Table[T[2][n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Feb 12 2019 *)

T(n)=[Vecrev(p) | p<-Vec(serreverse(x/((1+x+x*y)*(1+x)^2) + O(x*x^n)))]
{ my(A=T(10)); for(i=1, #A, print(A[i])) } \\ Andrew Howroyd, Apr 13 2023

T(n,k) = (binomial(3*n+1,n) * binomial(n,k-1) * binomial(n-1,k-1)) / (binomial(3*n,k-1) * (3*n+1)) = (A001764(n) * A001263(n,k) * k) / binomial(3*n,k-1) for 1 <= k <= n (conjectured). - Werner Schulte, Nov 22 2018
T(n,k) = binomial(3*n+1-k,n-k) * binomial(n,k-1) / n for 1 <= k <= n, more generally: T_m(n,k) = binomial((m+1)*n+1-k,n-k) * binomial(n,k-1) / n for 1 <= k <= n and some fixed integer m > 1. - Werner Schulte, Nov 22 2018
G.f.: A(x,y) is the series reversion of x/((1 + x + x*y)*(1 + x)^2). - Andrew Howroyd, Apr 13 2023

Data and Example (T(2,2) and T(5,3)) corrected and more terms added by Werner Schulte, Nov 22 2018

A361243 Number of nonequivalent noncrossing cacti with n nodes up to rotation and reflection.

Original entry on oeis.org

1, 1, 1, 2, 5, 17, 79, 421, 2537, 16214, 108204, 743953, 5237414, 37574426, 273889801, 2023645764, 15128049989, 114256903169, 870786692493, 6690155544157, 51771411793812, 403238508004050, 3159259746188665, 24884525271410389, 196966954270163612

Offset: 0

Andrew Howroyd, Mar 07 2023

nonn

A noncrossing cactus is a connected noncrossing graph (A007297) that is a cactus graph (a tree of edges and polygons).

			The a(4) = 5 nonequivalent cacti have the following blocks:
  {{1,2}, {1,3}, {1,4}},
  {{1,2}, {1,3}, {3,4}},
  {{1,2}, {1,4}, {2,3}},
  {{1,2}, {1,3,4}},
  {{1,2,3,4}}.
Graphically these can be represented:
   1---4    1   4    1---4    1---4    1---4
   | \      | \ |    |        | \ |    |   |
   2   3    2   3    2---3    2   3    2---3

Andrew Howroyd, Table of n, a(n) for n = 0..500
Wikipedia, Cactus graph.
Index entries for sequences related to cacti.

Cf. A003168, A007297, A361239, A361242.

\\ Here F(n) is the g.f. of A003168.
F(n) = {1 + serreverse(x/((1+2*x)*(1+x)^2) + O(x*x^n))}
seq(n) = {my(f=F(n-1)); Vec(1/(1 - x*subst(f + O(x^(n\2+1)), x, x^2)) + 1 + intformal(f) - sum(d=2, n, eulerphi(d) * log(1-subst(x*f^2 + O(x^(n\d+1)),x,x^d)) / d), -n-1)/2}

cp's OEIS Frontend

A003168 Number of blobs with 2n+1 edges.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Formula

A361245 Number of noncrossing 2,3 cacti with n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A361236 Array read by antidiagonals: T(n,k) is the number of noncrossing k-gonal cacti with n polygons up to rotation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A243662 Triangle read by rows: the reversed x = 1+q Narayana triangle at m=2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A361243 Number of nonequivalent noncrossing cacti with n nodes up to rotation and reflection.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A361244 Number of noncrossing bridgeless cacti with n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula