A303694 -id:A303694 - cp's OEIS frontend

A002995 Number of unlabeled planar trees (also called plane trees) with n nodes.

1, 1, 1, 1, 2, 3, 6, 14, 34, 95, 280, 854, 2694, 8714, 28640, 95640, 323396, 1105335, 3813798, 13269146, 46509358, 164107650, 582538732, 2079165208, 7457847082, 26873059986, 97239032056, 353218528324, 1287658723550, 4709785569184

Offset: 0

N. J. A. Sloane

Noncrossing handshakes of 2(n-1) people (each using only one hand) on round table, up to rotations - Antti Karttunen, Sep 03 2000
Equivalently, the number of noncrossing partitions up to rotation composed of n-1 blocks of size 2. - Andrew Howroyd, May 04 2018
a(n), n>2, is also the number of oriented cacti on n-1 unlabeled nodes with all cutpoints of separation degree 2, i.e. ones shared only by two (cyclic) blocks. These are digraphs (without loops) that have a unique Eulerian tour. Such digraphs with labeled nodes are enumerated by A102693. - Valery A. Liskovets, Oct 19 2005
Labeled plane trees are counted by A006963. - David Callan, Aug 19 2014
This sequence is similar to A000055 but those trees are not embedded in a plane. - Michael Somos, Aug 19 2014

			G.f. = 1 + x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 14*x^7 + 34*x^8 + 95*x^9 + ...
a(7) = 14 = 11 + 3 because there are 11 trees with 7 nodes but three of them can be embedded in a plane in two ways. These three trees have degree sequences 4221111, 3321111, 3222111, where there are two trees with each degree sequence but in the first, the two nodes of degree two are adjacent, in the second, the two nodes of degree three are adjacent, and in the third, the node of degree three is adjacent to two nodes of degree two. - _Michael Somos_, Aug 19 2014

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 304.
A. Errera, De quelques problèmes d'analysis situs, Comptes Rend. Congr. Nat. Sci. Bruxelles, (1930), 106-110.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 67, (3.3.26).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=0..200
F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, pp. 285 (4.1.26), 291 (4.1.48)
CombOS - Combinatorial Object Server, Generate free plane trees
R. Cori and M. Marcus, Counting non-isomorphic chord diagrams, Theor. Comp. Sci. 204 (1998) 55-75, Corollary 5.2.
Paul Drube and Puttipong Pongtanapaisan, Annular Non-Crossing Matchings, Journal of Integer Sequences, Vol. 19 (2016), #16.2.4.
A. Errera, Reviews of two articles on Analysis Situs, from Fortschritte [Annotated scanned copy]
D. Feldman, Counting plane trees, Unpublished manuscript, 1992. (Annotated scanned copy)
Bernold Fiedler, Scalar polynomial vector fields in real and complex time, arXiv:2410.05043 [math.DS], 2024. See pp. 21, 50.
Bernold Fiedler, Real-time blow-up and connection graphs of rational vector fields on the Riemann sphere, arXiv:2504.20503 [math.DS], 2025. See p. 23.
F. Harary and R. W. Robinson, The number of achiral trees, J. Reine Angew. Math., 278 (1975), 322-335.
F. Harary and R. W. Robinson, The number of achiral trees, J. Reine Angew. Math., 278 (1975), 322-335. (Annotated scanned copy)
G. Labelle, Sur la symétrie et l'asymétrie des structures combinatoires, Theor. Comput. Sci. 117, No. 1-2, 3-22 (1993).
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
Torsten Mütze, Proof of the middle levels conjecture, arXiv preprint arXiv:1404.4442 [math.CO], 2014.
Torsten Mütze, A book proof of the middle levels theorem, arXiv:2306.13019 [math.CO], 2023.
Torsten Mütze and Franziska Weber, Construction of 2-factors in the middle layer of the discrete cube, arXiv preprint arXiv:1111.2413 [math.CO], 2011.
Torsten Mütze and F. Weber, Construction of 2-factors in the middle layer of the discrete cube, Journal of Combinatorial Theory, Series A, 119(8) (2012), 1832-1855.
J. Sawada, Generating rooted and free plane trees, ACM Transactions on Algorithms, Vol. 2 No. 1 (2006), 1-13.
Seunghyun Seo and Heesung Shin, Two involutions on vertices of ordered trees, FPSAC'02 (2002). (see p_n).
Alexander Stoimenow, On the number of chord diagrams, Discr. Math. 218 (2000), 209-233. See Table 1.
D. W. Walkup, The number of plane trees, Mathematika, vol. 19, No. 2 (1972), 200-204.
Index entries for sequences related to trees

Column k=2 of A303694 and A303864.

Cf. A000055, A000108, A002996, A003239, A005354, A057502, A061417, A064640.

with (powseries): with (combstruct): n := 27: Order := n+2: sys := {C = Cycle(B), B = Union(Z,Prod(B,B))}: G003239 := (convert(gfseries(sys,unlabeled,x) [C(x)], polynom)) / x: G000108 := convert(taylor((1-sqrt(1-4*x)) / (2*x),x),polynom): G002995 := 1 + G003239 + (eval(G000108,x=x^2) - G000108^2)/2: A002995 := 1,1,1,seq(coeff(G002995,x^i),i=1..n); # Ulrich Schimke, Apr 05 2002
with(combinat): with(numtheory): m := 2: for p from 2 to 28 do s1 := 0: s2 := 0: for d from 1 to p do if p mod d = 0 then s1 := s1+phi(p/d)*binomial(m*d, d) fi: od: for d from 1 to p-1 do if gcd(m, p-1) mod d = 0 then s2 := s2+phi(d)*binomial((p*m)/d, (p-1)/d) fi: od: printf(`%d, `, (s1+s2)/(m*p)-binomial(m*p, p)/(p*(m-1)+1)) od : # Zerinvary Lajos, Dec 01 2006

a[0] = a[1] = 1; a[n_] := (1/(2*(n-1)))*Sum[ EulerPhi[(n-1)/d]*Binomial[2*d, d], {d, Divisors[n-1]}] - CatalanNumber[n-1]/2 + If[ EvenQ[n], CatalanNumber[n/2-1]/2, 0]; Table[ a[n], {n, 0, 29}] (* Jean-François Alcover, Mar 07 2012, from formula *)

catalan(n) = binomial(2*n, n)/(n+1);
a(n) = if (n<2, 1, n--; sumdiv(n, d, eulerphi(n/d)*binomial(2*d, d))/(2*n) - catalan(n)/2 + if ((n-1) % 2, 0, catalan((n-1)/2)/2)); \\ Michel Marcus, Jan 23 2016

G.f.: 1+B(x)+(C(x^2)-C(x)^2)/2 where B is g.f. of A003239 and C is g.f. of A000108(n-1).

a(n) = 1/(2*(n-1))*sum{d|(n-1)}(phi((n-1)/d)*binomial(2d, d)) - A000108(n-1)/2 + (if n is even) A000108(n/2-1)/2.

More terms, formula from Christian G. Bower, Dec 15 1999

Name corrected ("labeled" --> "unlabeled") by David Callan, Aug 19 2014

A369929 Array read by antidiagonals: T(n,k) is the number of achiral noncrossing partitions composed of n blocks of size k.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 3, 1, 1, 1, 1, 3, 3, 6, 1, 1, 1, 1, 3, 5, 7, 10, 1, 1, 1, 1, 4, 5, 16, 12, 20, 1, 1, 1, 1, 4, 7, 18, 31, 30, 35, 1, 1, 1, 1, 5, 7, 31, 35, 102, 55, 70, 1, 1, 1, 1, 5, 9, 34, 64, 136, 213, 143, 126, 1

Offset: 0

Andrew Howroyd, Feb 07 2024

T(n,2*k-1) is the number of achiral noncrossing k-gonal cacti with n polygons.

			Array begins:
===============================================
n\k| 1  2   3   4    5    6    7    8     9 ...
---+-------------------------------------------
0  | 1  1   1   1    1    1    1    1     1 ...
1  | 1  1   1   1    1    1    1    1     1 ...
2  | 1  1   1   1    1    1    1    1     1 ...
3  | 1  2   2   3    3    4    4    5     5 ...
4  | 1  3   3   5    5    7    7    9     9 ...
5  | 1  6   7  16   18   31   34   51    55 ...
6  | 1 10  12  31   35   64   70  109   117 ...
7  | 1 20  30 102  136  296  368  651   775 ...
8  | 1 35  55 213  285  663  819 1513  1785 ...
9  | 1 70 143 712 1155 3142 4495 9304 12350 ...
...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (first 51 antidiagonals)
Michel Bousquet and Cédric Lamathe, On symmetric structures of order two, Discrete Math. Theor. Comput. Sci. 10 (2008), 153-176. See Table 1.
Wikipedia, Fuss-Catalan number.
Wikipedia, Noncrossing partition.

Columns are: A000012, A001405(n-1), A047749 (k=3), A369930 (k=4), A143546 (k=5), A143547 (k=7), A143554 (k=9), A192893 (k=11).

Cf. A070914, A303694, A303929, A361236, A361239, A370060, A370062.

\\ u(n,k,r) are Fuss-Catalan numbers.
u(n,k,r) = {r*binomial(k*n + r, n)/(k*n + r)}
e(n,k) = {sum(j=0, n\2, u(j, k, 1+(n-2*j)*k/2))}
T(n, k)={if(n==0, 1, if(k%2, if(n%2, 2*u(n\2, k, (k+1)/2), u(n/2, k, 1) + u(n/2-1, k, k)), e(n, k) + if(n%2, u(n\2, k, k/2)))/2)}

T(n,k) = 2*A303929(n,k) - A303694(n,k).

T(n,2*k-1) = 2*A361239(n,k) - A361236(n,k).

A303912 Array read by antidiagonals: T(n,k) is the number of (planar) unlabeled k-ary cacti having n polygons.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 3, 1, 1, 1, 4, 6, 6, 1, 1, 1, 5, 10, 19, 10, 1, 1, 1, 6, 15, 44, 57, 28, 1, 1, 1, 7, 21, 85, 197, 258, 63, 1, 1, 1, 8, 28, 146, 510, 1228, 1110, 190, 1, 1, 1, 9, 36, 231, 1101, 4051, 7692, 5475, 546, 1, 1, 1, 10, 45, 344, 2100, 10632, 33130, 52828, 27429, 1708, 1

Offset: 0

Andrew Howroyd, May 02 2018

A k-ary cactus is a planar k-gonal cactus with vertices on each polygon numbered 1..k counterclockwise with shared vertices having the same number. In total there are always exactly k ways to number a given cactus since all polygons are connected. See the reference for a precise definition.

			Array begins:
===============================================================
n\k| 1   2     3      4       5        6        7         8
---+-----------------------------------------------------------
0  | 1   1     1      1       1        1        1         1 ...
1  | 1   1     1      1       1        1        1         1 ...
2  | 1   2     3      4       5        6        7         8 ...
3  | 1   3     6     10      15       21       28        36 ...
4  | 1   6    19     44      85      146      231       344 ...
5  | 1  10    57    197     510     1101     2100      3662 ...
6  | 1  28   258   1228    4051    10632    23884     47944 ...
7  | 1  63  1110   7692   33130   107062   285390    662628 ...
8  | 1 190  5475  52828  291925  1151802  3626295   9711032 ...
9  | 1 546 27429 373636 2661255 12845442 47813815 147766089 ...
...

Andrew Howroyd, Table of n, a(n) for n = 0..1274
Miklos Bona, Michel Bousquet, Gilbert Labelle, Pierre Leroux, Enumeration of m-ary cacti, arXiv:math/9804119 [math.CO], 1998-1999.
Wikipedia, Cactus graph
Index entries for sequences related to cacti

Columns 2..7 are A054357, A052393, A052394, A054363, A054366, A054369.

Cf. A070914, A303694, A303913.

T[0, _] = 1;
T[n_, k_] := DivisorSum[n, EulerPhi[n/#] Binomial[k #, #]&]/n - (k-1) Binomial[n k, n]/((k-1) n + 1);
Table[T[n-k, k], {n, 0, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, May 22 2018 *)

T(n,k)={if(n==0, 1, sumdiv(n, d, eulerphi(n/d)*binomial(k*d, d))/n - (k-1)*binomial(k*n, n)/((k-1)*n+1))}

T(n,k) = (Sum_{d|n} phi(n/d)*binomial(k*d, d))/n - (k-1)*binomial(k*n, n)/((k-1)*n+1) for n > 0.

T(n,k) ~ A070914(n,k-1)/n for fixed k > 1.

A303913 Array read by antidiagonals: T(n,k) is the number of (planar) unlabeled asymmetric k-ary cacti having n polygons.

Original entry on oeis.org

1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 3, 2, 0, 1, 1, 0, 6, 10, 8, 0, 1, 1, 0, 10, 28, 54, 18, 0, 1, 1, 0, 15, 60, 193, 222, 61, 0, 1, 1, 0, 21, 110, 505, 1140, 1107, 170, 0, 1, 1, 0, 28, 182, 1095, 3876, 7688, 5346, 538, 0, 1, 1, 0, 36, 280, 2093, 10326, 33125, 52364, 27399, 1654, 0

Offset: 0

Andrew Howroyd, May 02 2018

			Array begins:
===============================================================
n\k| 1   2     3      4       5        6        7         8
---+-----------------------------------------------------------
0  | 1   1     1      1       1        1        1         1 ...
1  | 1   1     1      1       1        1        1         1 ...
2  | 0   0     0      0       0        0        0         0 ...
3  | 0   1     3      6      10       15       21        28 ...
4  | 0   2    10     28      60      110      182       280 ...
5  | 0   8    54    193     505     1095     2093      3654 ...
6  | 0  18   222   1140    3876    10326    23394     47208 ...
7  | 0  61  1107   7688   33125   107056   285383    662620 ...
8  | 0 170  5346  52364  290700  1149126  3621150   9702008 ...
9  | 0 538 27399 373560 2661100 12845166 47813367 147765409 ...
...

Andrew Howroyd, Table of n, a(n) for n = 0..1274
Miklos Bona, Michel Bousquet, Gilbert Labelle, Pierre Leroux, Enumeration of m-ary cacti, arXiv:math/9804119 [math.CO], 1998-1999.
Wikipedia, Cactus graph
Index entries for sequences related to cacti

Columns k=2..7 are A054358, A054422, A052395, A054364, A054367, A054370.

Cf. A303694, A303912.

T[0, _] = 1;
T[n_, k_] := DivisorSum[n, MoebiusMu[n/#] Binomial[k #, #] &]/n - (k-1) Binomial[n k, n]/((k-1) n + 1);
Table[T[n-k, k], {n, 0, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, May 22 2018 *)

T(n,k)={if(n==0, 1, sumdiv(n, d, moebius(n/d)*binomial(k*d, d))/n - (k-1)*binomial(k*n, n)/((k-1)*n+1))}

T(n,k) = (Sum_{d|n} mu(n/d)*binomial(k*d, d))/n - (k-1)*binomial(k*n, n)/((k-1)*n+1) for n > 0.

A303929 Array read by antidiagonals: T(n,k) is the number of noncrossing partitions up to rotation and reflection composed of n blocks of size k.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 3, 1, 1, 1, 1, 3, 5, 6, 1, 1, 1, 1, 3, 8, 13, 12, 1, 1, 1, 1, 4, 11, 34, 49, 27, 1, 1, 1, 1, 4, 16, 60, 169, 201, 65, 1, 1, 1, 1, 5, 20, 109, 423, 1019, 940, 175, 1, 1, 1, 1, 5, 26, 167, 918, 3381, 6710, 4643, 490, 1

Offset: 0

Andrew Howroyd, May 02 2018

			=================================================================
n\k| 1   2    3     4      5       6       7       8        9
---+-------------------------------------------------------------
0  | 1   1    1     1      1       1       1       1        1 ...
1  | 1   1    1     1      1       1       1       1        1 ...
2  | 1   1    1     1      1       1       1       1        1 ...
3  | 1   2    2     3      3       4       4       5        5 ...
4  | 1   3    5     8     11      16      20      26       32 ...
5  | 1   6   13    34     60     109     167     257      359 ...
6  | 1  12   49   169    423     918    1741    3051     4969 ...
7  | 1  27  201  1019   3381    9088   20569   41769    77427 ...
8  | 1  65  940  6710  29335   96315  259431  607696  1280045 ...
9  | 1 175 4643 47104 266703 1072187 3417520 9240444 22066742 ...
...

Andrew Howroyd, Table of n, a(n) for n = 0..1274
Wikipedia, Noncrossing partition

Columns 2..5 are A006082(n+1), A082938, A303870, A303871.

Cf. A111275, A209612, A211359, A303694, A303875.

u[n_, k_, r_] := (r*Binomial[k*n + r, n]/(k*n + r));
e[n_, k_] := Sum[ u[j, k, 1 + (n - 2*j)*k/2], {j, 0, n/2}]
c[n_, k_] := If[n == 0, 1, (DivisorSum[n, EulerPhi[n/#]*Binomial[k*#, #]&] + DivisorSum[GCD[n - 1, k], EulerPhi[#]*Binomial[n*k/#, (n - 1)/#]&])/(k*n) - Binomial[k*n, n]/(n*(k - 1) + 1)];
T[n_, k_] := (1/2)*(c[n, k] + If[n == 0, 1, If[OddQ[k], If[OddQ[n], 2*u[ Quotient[n, 2], k, (k + 1)/2], u[n/2, k, 1] + u[n/2 - 1, k, k]], e[n, k] + If[OddQ[n], u[Quotient[n, 2], k, k/2]]]/2]) /. Null -> 0;
Table[T[n - k, k], {n, 1, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Jun 14 2018, translated from PARI *)

\\ here c(n,k) is A303694
u(n,k,r) = {r*binomial(k*n + r, n)/(k*n + r)}
e(n,k) = {sum(j=0, n\2, u(j, k, 1+(n-2*j)*k/2))}
c(n, k)={if(n==0, 1, (sumdiv(n, d, eulerphi(n/d)*binomial(k*d, d)) + sumdiv(gcd(n-1, k), d, eulerphi(d)*binomial(n*k/d, (n-1)/d)))/(k*n) - binomial(k*n, n)/(n*(k-1)+1))}
T(n,k)={(1/2)*(c(n,k) + if(n==0, 1, if(k%2, if(n%2, 2*u(n\2,k,(k+1)/2), u(n/2,k,1) + u(n/2-1,k,k)), e(n,k) + if(n%2, u(n\2,k,k/2)))/2))}

A303864 Array read by antidiagonals: T(n,k) = number of noncrossing path sets on k*n nodes up to rotation with each path having exactly k nodes.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 6, 2, 1, 1, 4, 36, 38, 3, 1, 1, 10, 210, 960, 384, 6, 1, 1, 16, 1176, 18680, 35956, 4425, 14, 1, 1, 36, 6328, 313664, 2280910, 1588192, 57976, 34, 1, 1, 64, 32896, 4683168, 111925464, 323840016, 77381016, 807318, 95, 1

Offset: 0

Andrew Howroyd, May 01 2018

			Array begins:
=======================================================
n\k| 1  2     3        4           5              6
---+---------------------------------------------------
0  | 1  1     1        1           1              1 ...
1  | 1  1     1        3           4             10 ...
2  | 1  1     6       36         210           1176 ...
3  | 1  2    38      960       18680         313664 ...
4  | 1  3   384    35956     2280910      111925464 ...
5  | 1  6  4425  1588192   323840016    46552781760 ...
6  | 1 14 57976 77381016 50668922540 21346459738384 ...
...

Andrew Howroyd, Table of n, a(n) for n = 0..1274

Columns 2..4 are A002995(n+1), A303865, A303866.
Row n=1 is A051437(k-3).
Cf. A302828, A303844, A303869.
Cf. A295224 (polygon dissections), A303694 (sets of cycles instead of paths).

nmax = 10; seq[n_, k_] := Module[{p, q, h}, p = 1 + InverseSeries[ x/(k*2^If[k == 1, 0, k - 3]*(1 + x)^k) + O[x]^n, x ]; h = p /. x -> x^2 + O[x]^n; q = x*D[p, x]/p; Integrate[((p - 1)/k + Sum[EulerPhi[d]*(q /. x -> x^d + O[x]^n), {d, 2, n}])/x, x] + If[OddQ[k], 0, 2^(k/2 - 2)*x*h^(k/2)] + 1];
Clear[col]; col[k_] := col[k] = CoefficientList[seq[nmax, k], x];
T[n_, k_] := col[k][[n + 1]];
Table[T[n - k, k], {n, 0, nmax}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Jul 04 2018, after Andrew Howroyd *)

seq(n,k)={ \\ gives gf of k'th column
my(p=1 + serreverse( x/(k*2^if(k==1, 0, k-3)*(1 + x)^k) + O(x*x^n) ));
my(h=subst(p,x,x^2+O(x*x^n)), q=x*deriv(p)/p);
intformal( ((p-1)/k + sum(d=2,n,eulerphi(d)*subst(q,x,x^d+O(x*x^n))))/x) + if(k%2, 0, 2^(k/2-2)*x*h^(k/2)) + 1;
}
Mat(vector(6, k, Col(seq(7, k))))

A332649 Array read by antidiagonals: T(n,k) is the number of unlabeled k-gonal cacti having n polygons.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 3, 1, 1, 1, 1, 3, 4, 6, 1, 1, 1, 1, 3, 7, 8, 11, 1, 1, 1, 1, 4, 8, 25, 19, 23, 1, 1, 1, 1, 4, 13, 31, 88, 48, 47, 1, 1, 1, 1, 5, 14, 67, 132, 366, 126, 106, 1, 1, 1, 1, 5, 20, 80, 372, 636, 1583, 355, 235, 1

Offset: 0

Andrew Howroyd, Feb 18 2020

The number of nodes will be n*(k-1) + 1.

			Array begins:
======================================================
n\k | 1  2   3    4    5     6     7     8      9
----+-------------------------------------------------
  0 | 1  1   1    1    1     1     1     1      1 ...
  1 | 1  1   1    1    1     1     1     1      1 ...
  2 | 1  1   1    1    1     1     1     1      1 ...
  3 | 1  2   2    3    3     4     4     5      5 ...
  4 | 1  3   4    7    8    13    14    20     22 ...
  5 | 1  6   8   25   31    67    80   143    165 ...
  6 | 1 11  19   88  132   372   504  1093   1391 ...
  7 | 1 23  48  366  636  2419  3659  9722  13485 ...
  8 | 1 47 126 1583 3280 16551 28254 91391 138728 ...
...

Andrew Howroyd, Table of n, a(n) for n = 0..1325
Maryam Bahrani and Jérémie Lumbroso, Enumerations, Forbidden Subgraph Characterizations, and the Split-Decomposition, arXiv:1608.01465 [math.CO], 2016.
Wikipedia, Cactus graph
Index entries for sequences related to cacti

Columns k=1..4 are A000012, A000055(n+1), A003081, A287892.

Cf. A303694, A332648, A332650, A332651.

\\ here R(n,k) is column k+1 of A332648.
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
R(n,k)={my(v=[]); for(n=1, n, my(g=1+x*Ser(v)); v=EulerT(Vec((g^k + g^(k%2)*subst(g^(k\2), x, x^2))/2))); concat([1], v)}
U(n,k)={my(p=Ser(R(n,k-1))); my(g(d)=subst(p + O(x*x^(n\d)), x, x^d)); Vec(g(1) + x*sumdiv(k, d, eulerphi(d)*g(d)^(k/d))/(2*k) - x*(g(1)^k)/2 + x*if(k%2==0, g(2)^(k/2) - g(1)^2*g(2)^(k/2-1))/4)}
T(n)={Mat(concat([vectorv(n+1,i,1)], vector(n, k, Col(U(n,k+1)))))}
{ my(A=T(8)); for(n=1, #A, print(A[n,])) }

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.

A054362 Number of unlabeled 4-gonal cacti having n polygons.

Original entry on oeis.org

1, 1, 1, 3, 11, 52, 307, 1936, 13207, 93496, 683988, 5127163, 39230669, 305299420, 2410624122, 19273255184, 155780437711, 1271253542364, 10462650241996, 86765190816362, 724450039738076, 6086167189623746, 51416796881915019

Offset: 0

Simon Plouffe

nonn

Also, the number of noncrossing partitions up to rotation composed of n blocks of size 4. - Andrew Howroyd, Apr 30 2018

Andrew Howroyd, Table of n, a(n) for n = 0..200
Miklos Bona, Michel Bousquet, Gilbert Labelle, and Pierre Leroux, Enumeration of m-ary cacti, Advances in Applied Mathematics, 24 (2000), 22-56.
Index entries for sequences related to cacti

Column k=4 of A303694.

Cf. A052394, A052395, A303870.

with(combinat): with(numtheory): m := 4: for p from 2 to 28 do s1 := 0: s2 := 0: for d from 1 to p do if p mod d = 0 then s1 := s1+phi(p/d)*binomial(m*d, d) fi: od: for d from 1 to p-1 do if gcd(m, p-1) mod d = 0 then s2 := s2+phi(d)*binomial((p*m)/d, (p-1)/d) fi: od: printf(`%d, `, (s1+s2)/(m*p)-binomial(m*p, p)/(p*(m-1)+1)) od: # Zerinvary Lajos, Dec 01 2006

a[0] = 1;
a[n_] := (DivisorSum[n, EulerPhi[n/#] Binomial[4#, #]&] + DivisorSum[GCD[n - 1, 4], EulerPhi[#] Binomial[4n/#, (n-1)/#]&])/(4n) - Binomial[4n, n]/ (3n + 1);
Table[a[n], {n, 0, 22}] (* Jean-François Alcover, Jun 29 2018, after Andrew Howroyd *)

a(n) = {if(n==0, 1, (sumdiv(n, d, eulerphi(n/d)*binomial(4*d, d)) + sumdiv(gcd(n-1, 4), d, eulerphi(d)*binomial(4*n/d, (n-1)/d)))/(4*n) - binomial(4*n, n)/(3*n+1))} \\ Andrew Howroyd, Apr 30 2018

a(n) = ((Sum_{d|n} phi(n/d)*binomial(4*d, d)) + (Sum_{d|gcd(n-1, 4)} phi(d)*binomial(4*n/d, (n-1)/d)))/(4*n) - binomial(4*n, n)/(3*n+1) for n > 0. - Andrew Howroyd, Apr 30 2018

More terms from Zerinvary Lajos, Dec 01 2006

A054365 Number of unlabeled 5-gonal cacti having n polygons.

Original entry on oeis.org

1, 1, 1, 3, 17, 102, 811, 6626, 58385, 532251, 5011934, 48344880, 475982471, 4766639628, 48434621610, 498363430232, 5184274255789, 54451326151253, 576810990484823, 6156943228387305, 66170786572330174, 715564777086617766

Offset: 0

Simon Plouffe

nonn

Also, the number of noncrossing partitions up to rotation composed of n blocks of size 5. - Andrew Howroyd, May 04 2018

Andrew Howroyd, Table of n, a(n) for n = 0..200
Miklos Bona, Michel Bousquet, Gilbert Labelle, and Pierre Leroux, Enumeration of m-ary cacti, Advances in Applied Mathematics, 24 (2000), 22-56.
Luke Lippstreu, Jorge Mago, Marcus Spradlin, and Anastasia Volovich, Weak Separation, Positivity and Extremal Yangian Invariants, arXiv:1906.11034 [hep-th], 2019.
Index entries for sequences related to cacti

Column k=5 of A303694.

Cf. A054363, A054364, A303871.

with(combinat): with(numtheory): m := 5: for p from 2 to 28 do s1 := 0: s2 := 0: for d from 1 to p do if p mod d = 0 then s1 := s1+phi(p/d)*binomial(m*d, d) fi: od: for d from 1 to p-1 do if gcd(m, p-1) mod d = 0 then s2 := s2+phi(d)*binomial((p*m)/d, (p-1)/d) fi: od: printf(`%d, `, (s1+s2)/(m*p)-binomial(m*p, p)/(p*(m-1)+1)) od: # Zerinvary Lajos, Dec 01 2006

a[0] = 1;
a[n_] := (DivisorSum[n, EulerPhi[n/#] Binomial[5#, #]&] + DivisorSum[GCD[n - 1, 5], EulerPhi[#] Binomial[5n/#, (n-1)/#]&])/(5n) - Binomial[5n, n]/ (4n+1);
Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Jul 01 2018, after Andrew Howroyd *)

a(n) = {if(n==0, 1, (sumdiv(n, d, eulerphi(n/d)*binomial(5*d, d)) + sumdiv(gcd(n-1, 5), d, eulerphi(d)*binomial(5*n/d, (n-1)/d)))/(5*n) - binomial(5*n, n)/(4*n+1))} \\ Andrew Howroyd, May 04 2018

a(n) = ((Sum_{d|n} phi(n/d)*binomial(5*d, d)) + (Sum_{d|gcd(n-1, 5)} phi(d)*binomial(5*n/d, (n-1)/d)))/(5*n) - binomial(5*n, n)/(4*n+1) for n > 0. - Andrew Howroyd, May 04 2018

More terms from Zerinvary Lajos, Dec 01 2006

cp's OEIS Frontend

A002995 Number of unlabeled planar trees (also called plane trees) with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A369929 Array read by antidiagonals: T(n,k) is the number of achiral noncrossing partitions composed of n blocks of size k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A303912 Array read by antidiagonals: T(n,k) is the number of (planar) unlabeled k-ary cacti having n polygons.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A303913 Array read by antidiagonals: T(n,k) is the number of (planar) unlabeled asymmetric k-ary cacti having n polygons.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A303929 Array read by antidiagonals: T(n,k) is the number of noncrossing partitions up to rotation and reflection composed of n blocks of size k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A303864 Array read by antidiagonals: T(n,k) = number of noncrossing path sets on k*n nodes up to rotation with each path having exactly k nodes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A332649 Array read by antidiagonals: T(n,k) is the number of unlabeled k-gonal cacti having n polygons.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs