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

Author

Stephan Beyer, Apr 05 2016

Keywords

• nonn
• tabf

Comments

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

Examples

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

Links

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

Crossrefs

Transpose of A271205.

Cf. A000014 (row sums), A345971.

Programs

PARI

\\ 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

Formula

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