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,4

Comments

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

Links

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

Formula

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

Maple

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 A. Sellers, Mar 17 2000

Mathematica

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

Prog

(PARI) 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

Crossrefs

Column k=3 of A303694.

Cf. A052393, A054422, A082938.

Sequence in context: A362097 A080873 A126162 * A137990 A056650 A182169

Adjacent sequences: A054420 A054421 A054422 * A054424 A054425 A054426

Keyword

nonn

Author

Simon Plouffe, Mar 15 2000

Extensions

More terms from James A. Sellers, Mar 17 2000

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

Status

approved