A000014 -id:A000014 - cp's OEIS frontend

A271362 Number T(n,k) of series-reduced free trees with n nodes of which exactly k>=3 are leaves, k+1 <= n <= 2k-2.

1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 1, 2, 4, 3, 1, 4, 6, 3, 1, 2, 10, 9, 4, 1, 8, 17, 12, 4, 1, 4, 22, 30, 16, 5, 1, 15, 47, 44, 20, 5, 1, 6, 53, 91, 67, 25, 6, 1, 32, 127, 158, 91, 30, 6, 1, 11, 121, 282, 258, 126

Offset: 4

Stephan Beyer, Apr 05 2016

The length of row n is floor((n-2)/2).

			    Irregular triangle begins
    n \ k 3   4   5   6   7  8
     4     1;
     5     1;
     6     1,  1;
     7     1,  1;
     8     1,  2,  1;
     9     2,  2,  1;
    10     2,  4,  3,  1;
    11     4,  6,  3,  1;
    12     2, 10,  9,  4, 1;
    13     8, 17, 12,  4, 1;
    14     4, 22, 30, 16, 5, 1;
    15    15, 47, 44, 20, 5, 1;
    ...

Washington Bomfim, Table of n, a(n) for n = 4..199
B. D. McKay, Lists of Trees sorted by diameter and Homeomorphically irreducible trees, with <= 22 nodes.

Transpose of A271205.

Cf. A000014 (row sums), A345971.

\\ using files hitree4.txt etc from McKay.
nL(n, Tr) = { my(E = strsplit(Tr, "  "), u_v, Deg = vectorsmall(n));
for(j = 1, n-1, u_v = strsplit(E[j], " "); u_v = eval(u_v);
   Deg[ u_v[1]+1 ]++; Deg[ u_v[2]+1 ]++); sum(v = 1, n, Deg[v] == 1)
};
Rows(r1, r2) = {my(F, C, nF); for(n = r1, r2,
F = readstr(Str("hitree", n, ".txt")); C = vectorsmall(n-1);
for(i = 1, #F, nF = nL(n, F[i]); C[nF]++ );
print1(n" "); for(i=1, #C, if(C[i] > 0, print1(C[i]", "))); print() )
}; \\ Washington Bomfim, Jul 09 2021

T(n,k) = A271205(k,n).

A345971 Irregular triangle T(n,k) read by rows in which n-th row lists numbers of series-reduced trees realized by respective degree sequences in n-th row of A345970; n >= 4, 1 <= k <= A002865(n-2).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 2, 3, 1, 4, 1, 1, 1, 1, 1, 2, 3, 2, 2, 4, 6, 2, 1, 1, 1, 1, 1, 2, 3, 3, 2, 2, 4, 9, 4, 8, 1, 1, 1, 1, 1, 1, 2, 3, 3, 2, 2, 3, 1, 4, 9, 6, 9, 2, 8, 14, 4, 1, 1, 1, 1, 1, 1, 2, 3, 3, 3, 2, 3, 2, 2, 4, 9, 9, 9, 9, 4, 8, 25, 14, 15

Offset: 4

Washington Bomfim, Jul 05 2021

The first floor((n-2)/2) terms of n-th row are all 1 thus the first floor((n-2)/2) degree sequences of n-th row of A345970 have only one realization.
Let a "unigraph" be a graph which is the only realization of its degree sequence. Among all series-reduced trees on n vertices we have floor((n-2)/2) + [n>=8] * [(n-8) == 0 (mod 3)] unigraphs.
Let T be a series-reduced tree of diameter dT, with h nodes of degree >= 3, and degree sequence D. If h <= 2, dT <= 3, and T is a unigraph [R. H. Johnson Corollary 2.3]. For each degree sequence the value of h is equal to the number of parts of a unique partition [Myerson], thus the number of unigraphs would be equal to the number of partitions (without parts 1) of n-2 with at most 2 parts, which is floor((n-2)/2). Degree sequences of the form [d,d,d,1,..,1] give an additional unigraph when n >= 8 and (n-8) == 0 (mod 3). These unigraphic sequences can be depicted as:
||_| , |_|| , ...
           | | |
A250308(n) = Sum_{ k= 1 .. A002865(2*n-2) } ( T(2*n,k) * odd( Decode( A345970(2*n, k) ) ), where odd(D) is 1 if all d in D are odd, and 0 otherwize.

			Row number 9 is {1, 1, 1, 2} because the 9th row of A345970 is {4864, 8320, 9856, 11200} which can be decoded (using Decode() of A345970) to the 4-degree sequences [8,1,1,1,1,1,1,1,1], which obviously has just 1 realization, [6,3,1,1,1,1,1,1,1], [5,4,1,1,1,1,1,1,1], that also have one, and [4,3,3,1,1,1,1,1,1] which realizes the 2 trees:
.
       *  *  *            *  *  *
       |  |  |            |  |  |
    *--0--*--*         *--*--0--*
       |     |               |  |
       *     *               *  *
.
Triangle begins
   n \ k 1  2  3  4  5  6  7  8  9 10 11 12
    4    1;
    5    1;
    6    1, 1;
    7    1, 1;
    8    1, 1, 1, 1;
    9    1, 1, 1, 2;
   10    1, 1, 1, 1, 2, 2, 2;
   11    1, 1, 1, 1, 2, 3, 1, 4;
   12    1, 1, 1, 1, 1, 2, 3, 2, 2, 4, 6, 2;
   ...

Nima Amini, Not That Good, Will Hunting
R. H. Johnson, Properties of unique realizations-a survey, Discrete Mathematics, Volume 31 January, 1980 pp 185-192.
B. D. McKay, Lists of Trees sorted by diameter and Homeomorphically irreducible trees, with <= 22 nodes.
Gerry Myerson, Problems2004
Index entries for sequences related to trees

Cf. A000014 (row sums), A002865 (row widths), A345970 (encoded degree sequences), A250308.

D_Generator(n) = { my(D = vectorsmall(n), j);
M = Map();                                \\ For each partition of n-2, "P",
forpart( P = n-2,                         \\ P without parts 1, make D =
   for(i = 1, n-#P, D[i] = 1); j = n-#P;  \\ [1..1 0..0], n-#P terms 1, and
   for(i = 1,   #P, D[j++] = P[i] + 1);   \\ #p terms 0. Complete D.
   mapput(M, D, 0) , [2, n-2] )        \\ store D.
};
EdgesList2D(n, Tr) = {my(D = vectorsmall(n), E = strsplit(Tr, "  "), u_v);
for(j = 1, n-1, u_v = strsplit(E[j], " "); u_v = eval(u_v);
   D[ u_v[1]+1 ]++; D[ u_v[2]+1 ]++); vecsort(D) };
                                      \\ Using files hitree4.txt etc from McKay.
Rows(r1, r2) = {my(Trees, D, j, C); for(n = r1, r2,
Trees = readstr(Str("hitree", n, ".txt")); D_Generator(n);
for(i = 1, #Trees, D = EdgesList2D(n, Trees[i]); j = mapget(M, D); mapput(~M, D, j+1));
C = Mat(M)[, 2]; print1(n" "); for(i = 1, #C, print1(C[i]", ")); print() ) };

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.

cp's OEIS Frontend

A271362 Number T(n,k) of series-reduced free trees with n nodes of which exactly k>=3 are leaves, k+1 <= n <= 2k-2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A345971 Irregular triangle T(n,k) read by rows in which n-th row lists numbers of series-reduced trees realized by respective degree sequences in n-th row of A345970; n >= 4, 1 <= k <= A002865(n-2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

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