A303694 -id:A303694 - cp's OEIS frontend

A054423 Number of unlabeled 3-gonal cacti having n triangles.

1, 1, 1, 2, 7, 19, 86, 372, 1825, 9143, 47801, 254990, 1391302, 7713642, 43401974, 247216934, 1423531255, 8275108733, 48511773461, 286542497274, 1704002332513, 10195435737315, 61341136938138, 370933387552634, 2253475545208390, 13748639775492766, 84211761819147696

Offset: 0

Simon Plouffe, Mar 15 2000

nonn

Also, the number of noncrossing partitions up to rotation composed of n blocks of size 3. - Andrew Howroyd, May 04 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.
Miklos Bona, Michel Bousquet, Gilbert Labelle, and Pierre Leroux, Enumeration of m-ary cacti, Advances in Applied Mathematics, 24 (2000), 22-56.
M. Bousquet and C. Lamathe, Enumeration of solid trees according to edge number and edge degree distribution, Discr. Math., 298 (2005), 115-141.
Index entries for sequences related to cacti

Column k=3 of A303694.

Cf. A052393, A054422, A082938.

with(combinat): with(numtheory): m := 3: for p from 1 to 40 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: # James Sellers, Mar 17 2000

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

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

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

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

More terms from James Sellers, Mar 17 2000

Terms a(24) and beyond from Andrew Howroyd, May 04 2018

A054368 Number of unlabeled 6-gonal cacti having n polygons.

Original entry on oeis.org

1, 1, 1, 4, 25, 187, 1772, 17880, 191967, 2141232, 24640989, 290610414, 3498042924, 42831369777, 532148952720, 6695274478834, 85166167050949, 1093843440166718, 14169564589464986, 184957445502335682, 2430876839834279341, 32147041999684759275, 427520786795342624432

Offset: 0

Simon Plouffe

nonn

Also, the number of noncrossing partitions up to rotation composed of n blocks of size 6. - 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.
Index entries for sequences related to cacti

Column k=6 of A303694.

Cf. A054366, A054367.

with(combinat): with(numtheory): m := 6: 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[6#, #]&] + DivisorSum[GCD[n - 1, 6], EulerPhi[#] Binomial[6n/#, (n-1)/#]&])/(6n) - Binomial[6n, n]/(5 n + 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, eulerphi(n/d)*binomial(6*d, d)) + sumdiv(gcd(n-1, 6), d, eulerphi(d)*binomial(6*n/d, (n-1)/d)))/(6*n) - binomial(6*n, n)/(5*n+1))} \\ Andrew Howroyd, May 04 2018

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

More terms from Zerinvary Lajos, Dec 01 2006

Terms a(21) and beyond from Andrew Howroyd, May 04 2018

A054371 Number of unlabeled 7-gonal cacti having n polygons.

Original entry on oeis.org

1, 1, 1, 4, 33, 300, 3412, 40770, 518043, 6830545, 92909684, 1295151600, 18426823044, 266696759064, 3916798516462, 58253090490630, 875948658280305, 13299481192954961, 203661940884670135, 3142707632566279222, 48829032430870168660, 763383551090733489744

Offset: 0

Simon Plouffe

nonn

Also, the number of noncrossing partitions up to rotation composed of n blocks of size 7.

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=7 of A303694.

Cf. A054369, A054370.

with(combinat): with(numtheory): m := 7: for p from 2 to 27 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[7#, #]&] + DivisorSum[GCD[n - 1, 7], EulerPhi[#] Binomial[7n/#, (n-1)/#]&])/(7n) - Binomial[7n, n]/(6 n + 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(7*d, d)) + sumdiv(gcd(n-1, 7), d, eulerphi(d)*binomial(7*n/d, (n-1)/d)))/(7*n) - binomial(7*n, n)/(6*n+1))} \\ Andrew Howroyd, May 04 2018

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

More terms from Zerinvary Lajos, Dec 01 2006

Terms a(20) and beyond from Andrew Howroyd, May 04 2018

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

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 4, 1, 1, 1, 3, 5, 9, 1, 1, 1, 3, 11, 13, 20, 1, 1, 1, 4, 13, 46, 37, 48, 1, 1, 1, 4, 22, 62, 208, 111, 115, 1, 1, 1, 5, 25, 140, 333, 1002, 345, 286, 1, 1, 1, 5, 37, 176, 985, 1894, 5012, 1105, 719, 1, 1, 1, 6, 41, 319, 1397, 7374, 11258, 25863, 3624, 1842, 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
----+-------------------------------------------------
  0 | 1   1    1     1     1      1      1       1 ...
  1 | 1   1    1     1     1      1      1       1 ...
  2 | 1   2    2     3     3      4      4       5 ...
  3 | 1   4    5    11    13     22     25      37 ...
  4 | 1   9   13    46    62    140    176     319 ...
  5 | 1  20   37   208   333    985   1397    3059 ...
  6 | 1  48  111  1002  1894   7374  11757   31195 ...
  7 | 1 115  345  5012 11258  57577 103376  331991 ...
  8 | 1 286 1105 25863 68990 463670 937179 3643790 ...
  ...

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, A000081(n+1), A003080, A287891.

Cf. A303694, A332649.

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)}
T(n)={Mat(concat([vectorv(n+1,i,1)], vector(n,k,Col(R(n,k)))))}
{ my(A=T(8)); for(n=1, #A, print(A[n,])) }

cp's OEIS Frontend

A054423 Number of unlabeled 3-gonal cacti having n triangles.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A054368 Number of unlabeled 6-gonal cacti having n polygons.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A054371 Number of unlabeled 7-gonal cacti having n polygons.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI