A235111 -id:A235111 - cp's OEIS frontend

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).

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

A238415 Triangle read by rows: T(n,k) is the number of trees with n vertices having k branching vertices (n>=2, 0<=k<=floor(n/2) - 1).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 4, 1, 1, 7, 3, 1, 11, 10, 1, 1, 17, 24, 5, 1, 25, 56, 22, 2, 1, 36, 114, 74, 10, 1, 50, 224, 219, 55, 2, 1, 70, 411, 576, 224, 19, 1, 94, 733, 1394, 807, 126, 4, 1, 127, 1252, 3150, 2536, 637, 38, 1, 168, 2091, 6733, 7305, 2711, 305, 6

Offset: 2

Emeric Deutsch, Mar 05 2014

A branching node of a tree is a vertex of degree at least 3.
Sum of entries in row n is A000055(n) (number of trees with n vertices).
Row n has floor(n/2) entries.
T(n,1) = A004250(n-1).

			Row n=4 is T(4,0)=1,T(4,1)=1; indeed, the path P[4] has no branching vertex and the star S[4] has 1 branching vertex.
Triangle starts:
1;
1;
1, 1;
1, 2;
1, 4, 1;
1, 7, 3;
1, 11, 10, 1;
1, 17, 24, 5;

Andrew Howroyd, Table of n, a(n) for n = 2..1226

Cf. A000055, A235111, A196049, A004250.

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 and bigomega(pi(n)) <> 2 then a(pi(n)) elif bigomega(n) = 1 then a(pi(n))+1 elif bigomega(s(n)) <> 2 then a(r(n))+a(s(n)) else a(r(n))+a(s(n))+1 end if end proc: g := add(x^a(MI[j]), j = 1 .. nops(MI)): seq(coeff(g, x, q), q = 0 .. 2);

EulerMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1)}
R(n)={my(v=[1]); for(i=2, n, v=concat([1], y*EulerMT(v) + (1-y)*v)); v}
seq(n)={my(p=x*Ser(R(n))); Vec(p + (((1-y)*x-1)*p^2 + ((1-y)*x+1)*substvec(p,[x,y],[x^2,y^2]))/2)}
{ my(A=Vec(seq(20))); for(n=2, #A, print(Vecrev(A[n]))) } \\ Andrew Howroyd, May 21 2018

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 A196049, from these Matula numbers one obtains that these trees have 0, 1, 1, 1, 1, 1, 2, 1, 2, 2, and 1 branching vertices, respectively; the frequencies of 0, 1, and 2 are 1, 7, and 3, respectively. See the Maple program.

Terms a(51) and beyond from Andrew Howroyd, May 21 2018

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

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 1, 2, 0, 1, 2, 3, 2, 3, 0, 1, 4, 4, 7, 3, 4, 0, 1, 5, 9, 10, 12, 5, 5, 0, 1, 10, 15, 25, 20, 22, 6, 7, 0, 1, 14, 31, 46, 54, 38, 34, 9, 8, 0, 1, 26, 57, 103, 111, 114, 65, 53, 11, 10, 0, 1, 42, 114, 204, 267, 250, 212, 108, 76, 15, 12, 0, 1, 78, 219, 440, 583, 644, 502, 383, 167, 110, 18, 14, 0, 1

Offset: 2

Emeric Deutsch, Mar 05 2014

Sum of entries in row n is A000055(n) (number of trees with n vertices).
T(n,0) = A000014(n) (= number of series-reduced 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 A182907 for the degree sequence polynomial, from these Matula numbers one obtains that these trees have 5, 3, 3, 3, 2, 2, 1, 1, 1, 0, and 0 degree-2 vertices, respectively; the frequencies of 0, 1, 2, 3, 4, and 5 are 2, 3, 2, 3, 0, and 1, respectively. See the Maple program.

			Row n=4 is T(4,0)=1,T(4,1)=0; T(4,2)=1; indeed, the star S[4] has no degree-2 vertex and the path P[4] has 2 degree-2 vertices.
Triangle starts:
1;
0, 1;
1, 0, 1;
1, 1, 0, 1;
2, 1, 2, 0, 1;
2, 3, 2, 3, 0, 1;
4, 4, 7, 3, 4, 0, 1;
5, 9, 10, 12, 5, 5, 0, 1.

Andrew Howroyd, Table of n, a(n) for n = 2..1226 (rows 2..50)

Cf. A000055, A000014, A182907.

MI := [25, 27, 30, 35, 36, 40, 42, 48, 49, 56, 64]: with(numtheory): g := 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 1 elif bigomega(n) = 1 then sort(expand(g(pi(n))+x^bigomega(pi(n))*(x-1)+x)) else sort(expand(g(r(n))+g(s(n))-x^bigomega(r(n))-x^bigomega(s(n))+x^bigomega(n))) end if end proc: a := proc (n) options operator, arrow: coeff(g(n), x, 2) end proc: G := add(x^a(MI[q]), q = 1 .. 11): seq(coeff(G, x, j), j = 0 .. 5);

EulerMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1)}
T(n)={my(u=[1]); for(n=2, n, u=concat([1], EulerMT(u) + (y-1)*u)); my(r=x*Ser(u), v=Vec(-x + r*(1 + x*(1-y)) + (substvec(r,[x,y],[x^2,y^2])*(1 - x*(1-y)) - r^2*(1 + x*(1-y)))/2)); [Vecrev(p) | p<-v]}
{ my(A=T(10)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Dec 20 2020

G.f.: -x + R(x,y)*(1 + x*(1-y)) + (R(x^2,y^2)*(1 - x*(1-y)) - R(x,y)^2*(1 + x*(1-y)))/2 where R(x,y) satisfies R(x,y) = x*(R(x,y)*(y-1) + exp(Sum_{k>0} R(x^k,y^k)/k)). - Andrew Howroyd, Dec 20 2020

A235112 a(n) = the largest of the M-indices of the trees with n vertices.

Original entry on oeis.org

1, 2, 3, 7, 16, 32, 64, 152, 361, 1273, 4489, 22177, 109561, 735151

Offset: 1

Emeric Deutsch, Jan 03 2014

We define the M-index of a tree T to be the smallest of the Matula numbers of the rooted trees isomorphic (as a tree) to T. Example. The path tree P[5] = ABCDE has M-index 9. Indeed, there are 3 rooted trees isomorphic to P[5]: rooted at A, B, and C, respectively. Their Matula numbers are 11, 10, and 9, respectively. Consequently, the M-index of P[5] is 9.
a(n) = largest (= last) entry in row n of A235111.
It is conjectured that for n>=7 one has a(n) = A235120(n-6).
These numbers can be useful, for example, in the following situation. We intend to identify all trees that have 10 vertices and satisfy a certain property. Instead of scanning all rooted trees with Matula numbers from A005517(10)=125 to A005518(10)=219613, we do the scanning only for Matula numbers between 125 and a(10)=1273.

			a(4)=7. Indeed, there are 2 trees with 4 vertices: the path P[4] and the star S[3] with 3 edges. There are two rooted trees isomorphic to P[4]; they have Matula numbers 5 and 6; so the M-index is 5. There are two rooted trees isomorphic to S[3]; they have Matula numbers 7 and 8; so the M-index is 7. Max(5,7) = 7.

E. Deutsch, Tree statistics from Matula numbers, arXiv preprint arXiv:1111.4288, 2011.
E. Deutsch, Rooted tree statistics from Matula numbers, Discrete Appl. Math., 160, 2012, 2314-2322.
F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.
I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131-142.
I. Gutman and Yeong-Nan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 17-22.
I. Gutman, W. Linert, I. Lukovits, and Z. Tomovic, The multiplicative version of the Wiener index, J. Chem. Inf. Comput. Sci., 40, 2000, 113-116.
I. Gutman, W. Linert, I. Lukovits, and Z. Tomovic, On the multiplicative Wiener index and its possible chemical applications, Monatshefte f. Chemie, 131, 2000, 421-427.
D. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
Index entries for sequences related to Matula-Goebel numbers

Cf. A235111, A005518.

a(n) = A235111(n,A000055(n)).

a(13) from Emeric Deutsch, Feb 16 2014

a(14) from Emeric Deutsch, Mar 12 2014

A240159 Triangle read by rows: T(n,k) = number of trees with n vertices and k segments (n >= 2; 1 <= k <= n-1).

Original entry on oeis.org

1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 2, 1, 2, 1, 0, 3, 2, 3, 2, 1, 0, 4, 3, 7, 4, 4, 1, 0, 5, 5, 12, 10, 9, 5, 1, 0, 7, 6, 22, 20, 25, 15, 10, 1, 0, 8, 9, 34, 38, 54, 46, 31, 14, 1, 0, 10, 11, 53, 65, 114, 111, 103, 57, 26, 1, 0, 12, 15, 76, 108, 212, 250, 267, 204, 114, 42, 1, 0, 14, 18, 110, 167, 383, 502, 644, 583, 440, 219, 78

Offset: 2

Emeric Deutsch, Apr 02 2014

A segment of a tree is a path-subtree whose terminal vertices are branching or pendent vertices of the tree. A pendent vertex is a vertex of degree 1; a branching vertex is a vertex of degree >=3.

The author has no formula for obtaining the terms of the sequence. The first Maple program yields the number of segments of a tree identified by the Matula number of any of its associated rooted trees. The second program, making use of the set M of M-indices of the trees with n vertices (given in A235111 for n<=12), yields row n of the triangle. The M-index of a tree is the smallest of the Matula numbers of its associated rooted trees. In the Maple program given below we have n=7.

			Row 4 is 1, 0, 1. Indeed, there are 2 trees with 4 vertices: the path P_4 having 1 segment and the star S_4 having 3 segments.
Triangle begins:
  1;
  1,0;
  1,0,1;
  1,0,2,1,2;
  1,0,3,2,3,2;

Cf. A000014, A000055, A235111.

with(numtheory): seg := 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 and bigomega(pi(n)) = 1 then seg(pi(n)) elif bigomega(n) = 1 and bigomega(pi(n)) = 2 then seg(pi(n))+2 elif bigomega(n) = 1 then seg(pi(n))+1 elif bigomega(r(n)) = 1 and bigomega(s(n)) = 1 then seg(r(n))+seg(s(n))-1 elif bigomega(r(n)) = 1 and bigomega(s(n)) = 2 then seg(r(n))+seg(s(n))+1 elif bigomega(r(n)) = 2 and bigomega(s(n)) = 1 then seg(r(n))+seg(s(n))+1 elif bigomega(r(n)) = 2 and bigomega(s(n)) = 2 then seg(r(n))+seg(s(n))+2 elif bigomega(r(n)) = 1 and 2 < bigomega(s(n)) then seg(r(n))+seg(s(n)) elif 2 < bigomega(r(n)) and bigomega(s(n)) = 1 then seg(r(n))+seg(s(n)) elif bigomega(r(n)) = 2 and 2 < bigomega(s(n)) then seg(r(n))+seg(s(n))+1 elif 2 < bigomega(r(n)) and bigomega(s(n)) = 2 then seg(r(n))+seg(s(n))+1 else seg(r(n))+seg(s(n)) end if end proc:
M := {25, 27, 30, 35, 36, 40, 42, 48, 49, 56, 64}: P := sort(add(x^seg(M[i]), i = 1 .. nops(M))): seq(coeff(P, x, j), j = 1 .. 6);

r[n_] := FactorInteger[n][[1, 1]];
s[n_] := n/r[n];
seg[n_] := Which[n == 1, 0,
  PrimeOmega[n] == 1 && PrimeOmega[PrimePi[n]] == 1, seg[PrimePi[n]],
  PrimeOmega[n] == 1 && PrimeOmega[PrimePi[n]] == 2, seg[PrimePi[n]]+2,
  PrimeOmega[n] == 1, seg[PrimePi[n]]+1,
  PrimeOmega[r[n]] == 1 && PrimeOmega[s[n]] == 1, seg[r[n]] + seg[s[n]]-1,
  PrimeOmega[r[n]] == 1 && PrimeOmega[s[n]] == 2, seg[r[n]] + seg[s[n]]+1,
  PrimeOmega[r[n]] == 2 && PrimeOmega[s[n]] == 1, seg[r[n]] + seg[s[n]]+1,
  PrimeOmega[r[n]] == 2 && PrimeOmega[s[n]] == 2, seg[r[n]] + seg[s[n]]+2,
  PrimeOmega[r[n]] == 1 && 2 < PrimeOmega[s[n]], seg[r[n]] + seg[s[n]],
  2 < PrimeOmega[r[n]] && PrimeOmega[s[n]] == 1, seg[r[n]] + seg[s[n]],
  PrimeOmega[r[n]] == 2 && 2 < PrimeOmega[s[n]], seg[r[n]] + seg[s[n]]+1,
  2 < PrimeOmega[r[n]] && PrimeOmega[s[n]] == 2, seg[r[n]] + seg[s[n]]+1,
  True, seg[r[n]] + seg[s[n]]];
M = {25, 27, 30, 35, 36, 40, 42, 48, 49, 56, 64};
(* M is row[7] in A235111 *)
P = Sort[Sum[x^seg[M[[i]]], {i, 1, Length[M]}]];
Table[Coefficient[P, x, j], {j, 1, 6}] (* Jean-François Alcover, Sep 10 2024, after Maple program *)

Sum of entries in row n = A000055(n) = number of trees with n vertices.

T(n,n-1) = A000014(n) = number of reduced trees with n vertices.

A258123 Irregular triangle read by rows: T(n,k) is the number of trees with n vertices that have k vertices of maximum degree (n, k>=1).

Original entry on oeis.org

1, 0, 1, 1, 1, 1, 2, 0, 1, 4, 1, 0, 1, 8, 2, 0, 0, 1, 15, 6, 1, 0, 0, 1, 32, 11, 3, 0, 0, 0, 1, 68, 25, 10, 2, 0, 0, 0, 1, 156, 47, 25, 6, 0, 0, 0, 0, 1, 361, 105, 58, 24, 2, 0, 0, 0, 0, 1, 869, 227, 124, 69, 11, 0, 0, 0, 0, 0, 1, 2105, 556, 256, 185, 52, 4, 0, 0, 0, 0, 0, 1

Offset: 1

Emeric Deutsch, Aug 19 2015

Sum of entries in row n = A000055(n) = number of trees with n vertices.

			Triangle starts:
1;
0,1;
1;
1,1;
2,0,1;
4,1,0,1;
8,2,0,0,1;
Row 4 is 1,1; indeed, the star S(4) has degree sequence (0,0,0,1) and the path P(4) has degree sequence (1,1,2,2).

Cf. A000055, A235111, A182907.

No formula for T(n,k) or generating function is known to the author. Row 5, for example, has been obtained in the following manner. The 3 trees with 5 vertices have M-indices 9,12,16 (the M-index of a tree T is the smallest of the Matula numbers of the rooted trees isomorphic (as a tree) to T; see A235111). In A182907 one finds the degree sequence (and the degree sequence polynomial) of a rooted tree with known Matula number. To the Matula numbers 9, 12, 16, there correspond the degree sequence polynomials 3x^2 + 2x, x^3 + x^2 + 3x, x^4 + 4x, respectively. From here, number of vertices of maximum degree are 3, 1, and 1, respectively. In other words, 2 trees have 1 vertex of maximum degree, 0 trees have 2 vertices of maximum degree, and 1 tree has 3 vertices of maximum degree; this leads us to row 5: 2, 0, 1.

cp's OEIS Frontend

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).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

Extensions

A238415 Triangle read by rows: T(n,k) is the number of trees with n vertices having k branching vertices (n>=2, 0<=k<=floor(n/2) - 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

A235112 a(n) = the largest of the M-indices of the trees with n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A240159 Triangle read by rows: T(n,k) = number of trees with n vertices and k segments (n >= 2; 1 <= k <= n-1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

A258123 Irregular triangle read by rows: T(n,k) is the number of trees with n vertices that have k vertices of maximum degree (n, k>=1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula