|
| |
|
|
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).
|
|
2
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
4,14
|
|
|
COMMENTS
|
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.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
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;
...
|
|
|
PROG
|
(PARI)
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() ) };
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
