login
Number of solid 2-trees with 2n+1 edges.
3

%I #22 Feb 19 2024 22:55:12

%S 1,1,1,2,5,13,49,201,940,4643,24037,127859,696365,3858759,21704863,

%T 123619126,711787259,4137614454,24256010068,143271593982,852001881614,

%U 5097719884665,30670572676389,185466705697057

%N Number of solid 2-trees with 2n+1 edges.

%C Also, the number of noncrossing partitions up to rotation and reflection composed of n blocks of size 3. - _Andrew Howroyd_, May 03 2018

%H Andrew Howroyd, <a href="/A082938/b082938.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 M. Bousquet and C. Lamathe, <a href="https://dx.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.

%F a(n) = (A047749(n)+A054423(n))/2. - _Vladeta Jovovic_, Sep 11 2004

%F a(n) ~ 3^(3*n - 1/2) / (sqrt(Pi) * n^(5/2) * 2^(2*n + 3)). - _Vaclav Kotesovec_, Jun 01 2022

%t u[n_, k_, r_] := (r*Binomial[k*n + r, n]/(k*n + r));

%t e[n_, k_] := Sum[ u[j, k, 1 + (n - 2*j)*k/2], {j, 0, n/2}]

%t 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 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;

%t a[n_] := T[n, 3];

%t Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Jun 14 2018, after _Andrew Howroyd_ and A303929 *)

%Y Column k=3 of A303929.

%Y Cf. A047749, A054423.

%K nonn

%O 0,4

%A _N. J. A. Sloane_, May 26 2003

%E More terms from _Vladeta Jovovic_, Sep 11 2004