|
%I #25 Feb 12 2023 10:22:07
%S 1,0,1,0,0,1,0,0,1,2,0,0,1,2,3,0,0,1,4,5,6,0,0,1,6,9,10,11,0,0,1,11,
%T 18,21,22,23,0,0,1,18,35,42,45,46,47,0,0,1,37,75,94,101,104,105,106,0,
%U 0,1,66,159,204,223,230,233,234,235,0,0,1,135,355,473,520,539,546,549,550,551
%N Triangle read by rows: T(n,k) is the number of trees on n unlabeled nodes with all nodes of degree <= k (n>=1, 0 <= k <= n-1).
%H Andrew Howroyd, <a href="/A144528/b144528.txt">Table of n, a(n) for n = 1..1275</a>
%H Rebecca Neville, <a href="https://web.archive.org/web/20191029092609/http://gtn.kazlow.info:80/GTN54.pdf">Graphs whose vertices are forests with bounded degree</a>, Graph Theory Notes of New York, LIV (2008), 12-21. [Wayback Machine link]
%e Triangle begins:
%e 1
%e 0 1
%e 0 0 1
%e 0 0 1 2
%e 0 0 1 2 3
%e 0 0 1 4 5 6
%e 0 0 1 6 9 10 11
%e 0 0 1 11 18 21 22 23
%e 0 0 1 18 35 42 45 46 47
%e 0 0 1 37 75 94 101 104 105 106
%e ...
%e From _Andrew Howroyd_, Dec 17 2020: (Start)
%e Formatted as an array to show the full columns:
%e ================================================
%e n\k | 0 1 2 3 4 5 6 7 8 9 10
%e -----+------------------------------------------
%e 1 | 1 1 1 1 1 1 1 1 1 1 1 ...
%e 2 | 0 1 1 1 1 1 1 1 1 1 1 ...
%e 3 | 0 0 1 1 1 1 1 1 1 1 1 ...
%e 4 | 0 0 1 2 2 2 2 2 2 2 2 ...
%e 5 | 0 0 1 2 3 3 3 3 3 3 3 ...
%e 6 | 0 0 1 4 5 6 6 6 6 6 6 ...
%e 7 | 0 0 1 6 9 10 11 11 11 11 11 ...
%e 8 | 0 0 1 11 18 21 22 23 23 23 23 ...
%e 9 | 0 0 1 18 35 42 45 46 47 47 47 ...
%e 10 | 0 0 1 37 75 94 101 104 105 106 106 ...
%e 11 | 0 0 1 66 159 204 223 230 233 234 235 ...
%e 12 | 0 0 1 135 355 473 520 539 546 549 550 ...
%e ...
%e (End)
%t b[n_, i_, t_, k_] := b[n, i, t, k] = If[i<1, 0, Sum[Binomial[b[i-1, i-1,
%t k, k] + j-1, j]*b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]];
%t b[0, i_, t_, k_] = 1; a = {}; nmax = 20;
%t For[ni=2, ni < nmax-1, ni++, (* columns 3 to max-1 *)
%t gf[x_] = 1 + Sum[b[j-1, j-1, ni, ni] x^j, {j, 1, nmax}];
%t ci[x_] = SymmetricGroupIndex[ni+1, x] /. x[i_] -> gf[x^i];
%t a = Append[a, CoefficientList[Normal[Series[
%t gf[x] - (gf[x]^2 - gf[x^2])/2 + x ci[x], {x, 0, nmax}]], x]];]
%t Join[{1, 0, 1, 0, 0, 1}, Table[Join[{0, 0, 1}, Table[a[[k-3]][[n+1]],
%t {k, 4, n}]], {n, 4, nmax}]] // Flatten - _Robert A. Russell_, Feb 05 2023
%o (PARI) \\ here V(n,k) gives column k as a vector.
%o MSet(p,k)={my(n=serprec(p,x)-1); if(min(k,n)<1, 1 + O(x*x^n), polcoef(exp( sum(i=1, min(k,n), (y^i + O(y*y^k))*subst(p + O(x*x^(n\i)), x, x^i)/i ))/(1-y + O(y*y^k)), k, y))}
%o V(n,k)={my(g=1+O(x)); for(n=2, n, g=x*MSet(g, k-1)); Vec(1 + x*MSet(g, k) + (subst(g, x, x^2) - g^2)/2)}
%o M(n, m=n)={Mat(vector(m, k, V(n,k-1)[2..1+n]~))}
%o { my(T=M(12)); for(n=1, #T~, print(T[n, 1..n])) } \\ _Andrew Howroyd_, Dec 18 2020
%Y Columns k=2..7 are A000012, A000672, A000602, A036650, A036653, A359392.
%Y The last three diagonals give A144527, A144520, A000055.
%Y Cf. A144215, A238414, A299038.
%K nonn,tabl
%O 1,10
%A _N. J. A. Sloane_, Dec 20 2008
%E a(53) corrected and terms a(56) and beyond from _Andrew Howroyd_, Dec 17 2020
|
