|
%I #128 Sep 29 2021 13:08:21
%S 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,
%T 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,
%U 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
%N 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).
%C 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.
%C 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.
%C 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:
%C _|_|_|_ , _|_|_|_ , ...
%C | | |
%C 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.
%H Nima Amini, <a href="https://amininima.wordpress.com/2013/05/12/not-that-good-will-hunting/">Not That Good, Will Hunting</a>
%H R. H. Johnson, <a href="https://doi.org/10.1016/0012-365X(80)90035-7">Properties of unique realizations-a survey</a>, Discrete Mathematics, Volume 31 January, 1980 pp 185-192.
%H B. D. McKay, <a href="http://users.cecs.anu.edu.au/~bdm/data/trees.html">Lists of Trees sorted by diameter and Homeomorphically irreducible trees, with <= 22 nodes.</a>
%H Gerry Myerson, <a href="https://www.math.colostate.edu/~achter/wntc/problems/problems2004.pdf">Problems2004</a>
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%e 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:
%e .
%e * * * * * *
%e | | | | | |
%e *--0--*--* *--*--0--*
%e | | | |
%e * * * *
%e .
%e Triangle begins
%e n \ k 1 2 3 4 5 6 7 8 9 10 11 12
%e 4 1;
%e 5 1;
%e 6 1, 1;
%e 7 1, 1;
%e 8 1, 1, 1, 1;
%e 9 1, 1, 1, 2;
%e 10 1, 1, 1, 1, 2, 2, 2;
%e 11 1, 1, 1, 1, 2, 3, 1, 4;
%e 12 1, 1, 1, 1, 1, 2, 3, 2, 2, 4, 6, 2;
%e ...
%o (PARI)
%o D_Generator(n) = { my(D = vectorsmall(n), j);
%o M = Map(); \\ For each partition of n-2, "P",
%o forpart( P = n-2, \\ P without parts 1, make D =
%o for(i = 1, n-#P, D[i] = 1); j = n-#P; \\ [1..1 0..0], n-#P terms 1, and
%o for(i = 1, #P, D[j++] = P[i] + 1); \\ #p terms 0. Complete D.
%o mapput(M, D, 0) , [2, n-2] ) \\ store D.
%o };
%o EdgesList2D(n, Tr) = {my(D = vectorsmall(n), E = strsplit(Tr, " "), u_v);
%o for(j = 1, n-1, u_v = strsplit(E[j], " "); u_v = eval(u_v);
%o D[ u_v[1]+1 ]++; D[ u_v[2]+1 ]++); vecsort(D) };
%o \\ Using files hitree4.txt etc from McKay.
%o Rows(r1, r2) = {my(Trees, D, j, C); for(n = r1, r2,
%o Trees = readstr(Str("hitree", n, ".txt")); D_Generator(n);
%o for(i = 1, #Trees, D = EdgesList2D(n, Trees[i]); j = mapget(M, D); mapput(~M, D, j+1));
%o C = Mat(M)[, 2]; print1(n" "); for(i = 1, #C, print1(C[i]", ")); print() ) };
%Y Cf. A000014 (row sums), A002865 (row widths), A345970 (encoded degree sequences), A250308.
%K nonn,tabf
%O 4,14
%A _Washington Bomfim_, Jul 05 2021
|
