%I #37 Feb 20 2024 02:20:46
%S 1,1,1,2,7,19,86,372,1825,9143,47801,254990,1391302,7713642,43401974,
%T 247216934,1423531255,8275108733,48511773461,286542497274,
%U 1704002332513,10195435737315,61341136938138,370933387552634,2253475545208390,13748639775492766,84211761819147696
%N Number of unlabeled 3-gonal cacti having n triangles.
%C Also, the number of noncrossing partitions up to rotation composed of n blocks of size 3. - _Andrew Howroyd_, May 04 2018
%H Andrew Howroyd, <a href="/A054423/b054423.txt">Table of n, a(n) for n = 0..200</a>
%H Allan Bickle, <a href="https://doi.org/10.20429/tag.2024.000105">A Survey of Maximal k-degenerate Graphs and k-Trees</a>, Theory and Applications of Graphs 0 1 (2024) Article 5.
%H Miklos Bona, Michel Bousquet, Gilbert Labelle, and Pierre Leroux, <a href="https://doi.org/10.1006/aama.1999.0665">Enumeration of m-ary cacti</a>, Advances in Applied Mathematics, 24 (2000), 22-56.
%H M. Bousquet and C. Lamathe, <a href="https://doi.org/10.1016/j.disc.2004.11.015">Enumeration of solid trees according to edge number and edge degree distribution</a>, Discr. Math., 298 (2005), 115-141.
%H <a href="/index/Ca#cacti">Index entries for sequences related to cacti</a>
%F 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
%F a(n) ~ 3^(3*n - 1/2) / (sqrt(Pi) * n^(5/2) * 2^(2*n + 2)). - _Vaclav Kotesovec_, Jun 01 2022
%p with(combinat): with(numtheory): m := 3: for p from 1 to 40 do s1 := 0: s2 := 0:
%p for d from 1 to p do if p mod d = 0 then s1 := s1+phi(p/d)*binomial(m*d,d) fi: od:
%p 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:
%p printf(`%d,`, (s1+s2)/(m*p)-binomial(m*p,p)/(p*(m-1)+1)) od: # _James A. Sellers_, Mar 17 2000
%t a[0] = 1;
%t a[n_] := (DivisorSum[n, EulerPhi[n/#] Binomial[3 #, #]&] + DivisorSum[GCD[n - 1, 3], EulerPhi[#] Binomial[3n/#, (n-1)/#]&])/(3n) - Binomial[3n, n]/ (2n + 1);
%t Table[a[n], {n, 0, 26}] (* _Jean-François Alcover_, Jul 02 2018, after _Andrew Howroyd_ *)
%o (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
%Y Column k=3 of A303694.
%Y Cf. A052393, A054422, A082938.
%K nonn
%O 0,4
%A _Simon Plouffe_, Mar 15 2000
%E More terms from _James A. Sellers_, Mar 17 2000
%E Terms a(24) and beyond from _Andrew Howroyd_, May 04 2018