A339788 -id:A339788 - cp's OEIS frontend

A144215 Triangle read by rows: T(n,k) is the number of forests on n unlabeled nodes with all nodes of degree <= k (n>=1, 0 <= k <= n-1).

1, 1, 2, 1, 2, 3, 1, 3, 5, 6, 1, 3, 7, 9, 10, 1, 4, 11, 17, 19, 20, 1, 4, 15, 28, 34, 36, 37, 1, 5, 22, 52, 67, 73, 75, 76, 1, 5, 30, 90, 129, 144, 150, 152, 153, 1, 6, 42, 170, 264, 305, 320, 326, 328, 329, 1, 6, 56, 310, 542, 645, 686, 701, 707, 709, 710

Offset: 1

N. J. A. Sloane, Dec 20 2008

			Triangle begins:
  1
  1 2
  1 2  3
  1 3  5  6
  1 3  7  9 10
  1 4 11 17 19 20
  1 4 15 28 34 36 37
  ...
From _Andrew Howroyd_, Dec 18 2020: (Start)
Formatted as an array to show the full columns:
========================================================
n\k  | 0 1  2   3    4    5    6    7    8    9   10
-----+--------------------------------------------------
   1 | 1 1  1   1    1    1    1    1    1    1    1 ...
   2 | 1 2  2   2    2    2    2    2    2    2    2 ...
   3 | 1 2  3   3    3    3    3    3    3    3    3 ...
   4 | 1 3  5   6    6    6    6    6    6    6    6 ...
   5 | 1 3  7   9   10   10   10   10   10   10   10 ...
   6 | 1 4 11  17   19   20   20   20   20   20   20 ...
   7 | 1 4 15  28   34   36   37   37   37   37   37 ...
   8 | 1 5 22  52   67   73   75   76   76   76   76 ...
   9 | 1 5 30  90  129  144  150  152  153  153  153 ...
  10 | 1 6 42 170  264  305  320  326  328  329  329 ...
  11 | 1 6 56 310  542  645  686  701  707  709  710 ...
  12 | 1 7 77 600 1161 1431 1536 1577 1592 1598 1600 ...
(End)

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 rows)
Rebecca Neville, Graphs whose vertices are forests with bounded degree, Graph Theory Notes of New York, LIV (2008), 12-21. [Wayback Machine link]

The final diagonal gives A005195.
Column k=2 is A000041.
Cf. A144528, A144529, A339788.

\\ Here V(n,k) gives column k of A144528.
EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
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))}
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)}
M(n, m=n)={Mat(vector(m, k, EulerT(V(n,k-1)[2..1+n])~))}
{ my(T=M(12)); for(n=1, #T~, print(T[n, 1..n])) } \\ Andrew Howroyd, Dec 18 2020

Column k is Euler transform of column k of A144528. - Andrew Howroyd, Dec 18 2020

Terms a(29) and beyond from Andrew Howroyd, Dec 18 2020

A238414 Triangle read by rows: T(n,k) is the number of trees with n vertices having maximum vertex degree k (n>=1, 0<=k<=n-1).

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 3, 1, 1, 0, 0, 1, 5, 3, 1, 1, 0, 0, 1, 10, 7, 3, 1, 1, 0, 0, 1, 17, 17, 7, 3, 1, 1, 0, 0, 1, 36, 38, 19, 7, 3, 1, 1, 0, 0, 1, 65, 93, 45, 19, 7, 3, 1, 1, 0, 0, 1, 134, 220, 118, 47, 19, 7, 3, 1, 1, 0, 0, 1, 264, 537, 296, 125, 47, 19, 7, 3, 1, 1

Offset: 1

Emeric Deutsch, Mar 05 2014

Sum of entries in row n is A000055(n) (= number of trees with n vertices).
The author knows of no formula for T(n,k). The entries have been obtained in the following manner, explained for row n = 7. In A235111 we find that the 11 (= A000055(7)) trees with 7 vertices have M-indices 25, 27, 30, 35, 36, 40, 42, 48, 49, 56, and 64 (the M-index of a tree t is the smallest of the Matula numbers of the rooted trees isomorphic, as a tree, to t). Making use of the formula in A196046, from these Matula numbers one obtains the maximum vertex degrees: 2, 3, 3, 3, 4, 4, 3, 5, 3, 4, 6; the frequencies of 2,3,4,5,6 are 1, 5, 3, 1, 1, respectively. See the Maple program.
This sequence may be derived from A144528 which can be efficiently computed in the same manner as A000055. - Andrew Howroyd, Dec 17 2020

			Row n=4 is T(4,2)=1,T(4,3)=1; indeed, the maximum vertex degree in the path P[4] is 2, while in the star S[4] it is 3.
Triangle starts:
  1;
  0, 1;
  0, 0, 1;
  0, 0, 1,  1;
  0, 0, 1,  1,  1;
  0, 0, 1,  3,  1, 1;
  0, 0, 1,  5,  3, 1, 1;
  0, 0, 1, 10,  7, 3, 1, 1;
  0, 0, 1, 17, 17, 7, 3, 1, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 12 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Eric Weisstein's World of Mathematics, Maximum Vertex Degree

Row sums are A000055.

Cf. A144528, A196046, A235111, A332760 (connected graphs), A339788 (forests).

MI := [25, 27, 30, 35, 36, 40, 42, 48, 49, 56, 64]: with(numtheory): a := proc (n) local r, s: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: if n = 1 then 0 elif bigomega(n) = 1 then max(a(pi(n)), 1+bigomega(pi(n))) else max(a(r(n)), a(s(n)), bigomega(r(n))+bigomega(s(n))) end if end proc: g := add(x^a(MI[j]), j = 1 .. nops(MI)): seq(coeff(g, x, q), q = 2 .. 6);

\\ Here V(n, k) gives column k of A144528.
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))}
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)}
M(n, m=n)={my(v=vector(m, k, V(n,k-1)[2..1+n]~)); Mat(vector(m, k, v[k]-if(k>1, v[k-1])))}
{ my(T=M(12)); for(n=1, #T~, print(T[n, 1..n])) } \\ Andrew Howroyd, Dec 18 2020

T(n,k) = A144528(n,k) - A144528(n, k-1) for k > 0. - Andrew Howroyd, Dec 17 2020

Columns k=0..1 inserted by Andrew Howroyd, Dec 18 2020

cp's OEIS Frontend

A144215 Triangle read by rows: T(n,k) is the number of forests on n unlabeled nodes with all nodes of degree <= k (n>=1, 0 <= k <= n-1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions