A054423 -id:A054423 - cp's OEIS frontend

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

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, 7, 6, 1, 1, 1, 1, 3, 11, 19, 14, 1, 1, 1, 1, 4, 17, 52, 86, 34, 1, 1, 1, 1, 4, 25, 102, 307, 372, 95, 1, 1, 1, 1, 5, 33, 187, 811, 1936, 1825, 280, 1, 1, 1, 1, 5, 43, 300, 1772, 6626, 13207, 9143, 854, 1

Offset: 0

Andrew Howroyd, Apr 28 2018

Also, the number of unlabeled planar k-gonal cacti having n polygons.

The number of noncrossing partitions counted distinctly is given by A070914(n,k-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    7    11     17      25      33       43       55 ...
5  | 1   6   19    52    102     187     300      463      663 ...
6  | 1  14   86   307    811    1772    3412     5993     9821 ...
7  | 1  34  372  1936   6626   17880   40770    82887   154079 ...
8  | 1  95 1825 13207  58385  191967  518043  1213879  2558305 ...
9  | 1 280 9143 93496 532251 2141232 6830545 18471584 44121134 ...
...

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], Apr 1998.
Wikipedia, Cactus graph
Wikipedia, Noncrossing partition
Index entries for sequences related to cacti

Columns 2..7 are A002995(n+1), A054423, A054362, A054365, A054368, A054371.

Cf. A070914, A209805, A303864, A303929.

T[0, _] = 1;
T[n_, k_] := (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);
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)) + 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) = ((Sum_{d|n} phi(n/d)*binomial(k*d,d)) + (Sum_{d|gcd(n-1,k)} phi(d) * binomial(n*k/d, (n-1)/d)))/(k*n) - binomial(k*n,n)/(n*(k-1)+1) for n > 0.

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

A052393 Number of unlabeled ternary cacti having n triangles.

Original entry on oeis.org

1, 1, 3, 6, 19, 57, 258, 1110, 5475, 27429, 143379, 764970, 4173906, 23140816, 130205922, 741650802, 4270593219, 24825326199, 145535320383, 859627488966, 5112006997539, 30586307211945, 184023410798910, 1112800162657902, 6760426635625170

Offset: 0

Simon Plouffe

nonn

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=3 of A303912.

Cf. A054422, A054423.

a[n_] := If[n == 0, 1, (Binomial[3*n, n]/(2*n+1) + DivisorSum[n, Binomial[ 3*#, #]*EulerPhi[n/#]*Boole[# < n]&])/n]; Table[a[n], {n, 0, 24}] (* Jean-François Alcover, Jul 17 2017 *)

a(n) = if(n==0, 1, sumdiv(n, d, eulerphi(n/d)*binomial(3*d, d))/n - 2*binomial(3*n, n)/(2*n+1)) \\ Andrew Howroyd, May 02 2018

a(n) = (1/n)*(Sum_{d|n} phi(n/d)*binomial(3*d, d)) - 2*binomial(3*n, n)/(2*n+1) for n > 0. - Andrew Howroyd, May 02 2018

a(n) ~ 3^(3*n + 1/2) / (sqrt(Pi) * 2^(2*n + 2) * n^(5/2)). - Vaclav Kotesovec, Jul 17 2017

More terms from Jean-François Alcover, Jul 17 2017

A054422 Number of unlabeled asymmetric ternary cacti having n triangles.

Original entry on oeis.org

1, 1, 0, 3, 10, 54, 222, 1107, 5346, 27399, 142770, 764967, 4170672, 23140813, 130189302, 741650172, 4270501218, 24825326196, 145534796520, 859627488963, 5112003992610, 30586307195304, 184023393204654, 1112800162657899

Offset: 0

Simon Plouffe, Mar 15 2000

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=3 of A303913.

Cf. A052393, A054423.

a[0] = 1; a[n_] := (1/n) Sum[MoebiusMu[n/d] Binomial[3d, d], {d, Divisors[n] } ] - 2 Binomial[3n, n]/(2n + 1);
Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Jul 24 2018, after Andrew Howroyd *)

a(n) = if(n==0, 1, sumdiv(n, d, moebius(n/d)*binomial(3*d, d))/n - 2*binomial(3*n, n)/(2*n+1)) \\ Andrew Howroyd, May 02 2018

a(n) = (1/n)*(Sum_{d|n} mu(n/d)*binomial(3*d, d)) - 2*binomial(3*n, n)/(2*n+1) for n > 0. - Andrew Howroyd, May 02 2018

More terms from James Sellers, Mar 16 2000

A082938 Number of solid 2-trees with 2n+1 edges.

Original entry on oeis.org

1, 1, 1, 2, 5, 13, 49, 201, 940, 4643, 24037, 127859, 696365, 3858759, 21704863, 123619126, 711787259, 4137614454, 24256010068, 143271593982, 852001881614, 5097719884665, 30670572676389, 185466705697057

Offset: 0

N. J. A. Sloane, May 26 2003

nonn

Also, the number of noncrossing partitions up to rotation and reflection composed of n blocks of size 3. - Andrew Howroyd, May 03 2018

Andrew Howroyd, Table of n, a(n) for n = 0..200
Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.
M. Bousquet and C. Lamathe, Enumeration of solid trees according to edge number and edge degree distribution, Discr. Math., 298 (2005), 115-141.

Column k=3 of A303929.

Cf. A047749, A054423.

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;
a[n_] := T[n, 3];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jun 14 2018, after Andrew Howroyd and A303929 *)

a(n) = (A047749(n)+A054423(n))/2. - Vladeta Jovovic, Sep 11 2004

a(n) ~ 3^(3*n - 1/2) / (sqrt(Pi) * n^(5/2) * 2^(2*n + 3)). - Vaclav Kotesovec, Jun 01 2022

More terms from Vladeta Jovovic, Sep 11 2004

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A052393 Number of unlabeled ternary cacti having n triangles.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A054422 Number of unlabeled asymmetric ternary cacti having n triangles.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A082938 Number of solid 2-trees with 2n+1 edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions