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
Keywords
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
Programs
-
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 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 *) -
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
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
Extensions
More terms from James Sellers, Mar 17 2000
Terms a(24) and beyond from Andrew Howroyd, May 04 2018
Comments