A345971 -id:A345971 - 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).

A345970 Irregular triangle T(n,k) read by rows in which n-th row lists in colex order all series-reduced tree degree sequences D of n nodes encoded as t = Product_{d in D} prime(d); n >= 4, 1 <= k <= A002865(n-2).

Original entry on oeis.org

40, 112, 352, 400, 832, 1120, 2176, 3520, 3136, 4000, 4864, 8320, 9856, 11200, 11776, 21760, 23296, 30976, 35200, 31360, 40000, 29696, 48640, 60928, 73216, 83200, 98560, 87808, 112000, 63488, 117760, 136192, 191488, 173056, 217600, 232960, 309760, 275968, 352000, 313600, 400000

Offset: 4

Washington Bomfim, Jul 01 2021

Tree degree sequences of n nodes are in one-to-one correspondence with the partitions of n-2, as for instance set out in Myerson's collection of problems [Myerson]. For series-reduced trees, these partitions have no part 1.
Given a term t, the respective degree sequence D is determined by Decode(t). See second (PARI) entry.
A250308(n) = Sum_{k= 1 .. A002865(2*n-2) } ( A345971(2*n,k) * odd( Decode( T(2*n,k) ) ), where odd(D) is 1 if all d in D are odd, and 0 otherwize.

			Triangle begins:
  n \ k|  1    2 ...           n \ k| 1                2            ...
  -----+-------------          -----+-----------------------------------
  4    |   40;                 4    |       [3,1,1,1];
  5    |  112;                 5    |     [4,1,1,1,1];
  6    |  352,  400;    <=>    6    |   [5,1,1,1,1,1],   [3,3,1,1,1,1];
  7    |  832, 1120;           7    | [6,1,1,1,1,1,1], [4,3,1,1,1,1,1];
  ...                          ...
Row n = 7 follows from table
                                                                         .
  +---------------------+------------------+---------------------------+
  | Partitions of n-2 = |                  |                           |
  | 5 without parts 1   | Degree sequences |       Encoding            |
  +---------------------+------------------+---------------------------+
  |                 [5] |    6,1,1,1,1,1,1 |            prime(6) * 2^6 |
  |              [2, 3] |    4,3,1,1,1,1,1 | prime(4) * prime(3) * 2^5 |
  +---------------------+------------------+---------------------------+

Gerry Myerson, Problems 2004
Index entries for sequences computed from indices in prime factorization

Cf. A002865 (row widths), A265127 (column k=1), A345971 (number of trees by degree sequence), A344122 (free tree degree sequences), A250308.

Row(n) = {my(j=0, V = vector(numbpart(n-2) - numbpart(n-3)));
forpart(P=n-2, V[j++] = prod(k=1,#P, prime(P[k]+1)) << (n-#P),[2, n-2]); V};

Decode(t) = {my(V = [], i = 1, p); while(t > 1, p = prime(i); while(t % p == 0, t /= p; V = concat(V, Vec(i)) ); i++); vecsort(V, (x,y)->y-x) };

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

A345970 Irregular triangle T(n,k) read by rows in which n-th row lists in colex order all series-reduced tree degree sequences D of n nodes encoded as t = Product_{d in D} prime(d); n >= 4, 1 <= k <= A002865(n-2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI