A054365 -id:A054365 - 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.

A054363 Number of unlabeled 5-ary cacti having n polygons.

Original entry on oeis.org

1, 1, 5, 15, 85, 510, 4051, 33130, 291925, 2661255, 25059670, 241724380, 2379912355, 23833198140, 242173108050, 2491817151160, 25921371278805, 272256630756265, 2884054952424115, 30784716141936525, 330853932861650870, 3577823885433087690, 38907658120970944700

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

Cf. A054364, A054365.

a[n_] := If[n == 0, 1, (Binomial[5*n, n]/(4*n + 1) + DivisorSum[n, Binomial[5*#, #]*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(5*d, d))/n - 4*binomial(5*n, n)/(4*n+1)) \\ Andrew Howroyd, May 02 2018

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

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

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

A054364 Number of unlabeled asymmetric 5-ary cacti having n polygons.

Original entry on oeis.org

1, 1, 0, 10, 60, 505, 3876, 33125, 290700, 2661100, 25049020, 241724375, 2379812100, 23833198135, 242172147380, 2491817140380, 25921361665100, 272256630756260, 2884054853862540, 30784716141936520, 330853931834416520, 3577823885432126890, 38907658110093347780

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

Cf. A054363, A054365.

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

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

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

Terms a(13) and beyond from Andrew Howroyd, May 02 2018

A303871 Number of noncrossing partitions up to rotation and reflection composed of n blocks of size 5.

Original entry on oeis.org

1, 1, 1, 3, 11, 60, 423, 3381, 29335, 266703, 2507232, 24177705, 238003111, 2383370158, 24217426745, 249182213284, 2592138293117, 27225668134063, 288405507217589, 3078471666603235, 33085393411436772, 357782389095170193, 3890765813426578535, 42527471172438573757

Offset: 0

Andrew Howroyd, May 01 2018

nonn

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

Column k=5 of A303929.

Cf. A054365.

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

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

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

A054363 Number of unlabeled 5-ary cacti having n polygons.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A054364 Number of unlabeled asymmetric 5-ary cacti having n polygons.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A303871 Number of noncrossing partitions up to rotation and reflection composed of n blocks of size 5.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula