|
| |
|
|
A339779
|
|
Array read by antidiagonals: T(n,k) is the number of homeomorphically irreducible leaf colored trees with n leaves of k colors.
|
|
6
|
|
|
|
1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 3, 1, 0, 1, 4, 6, 4, 2, 0, 1, 5, 10, 10, 11, 3, 0, 1, 6, 15, 20, 36, 30, 7, 0, 1, 7, 21, 35, 90, 144, 105, 13, 0, 1, 8, 28, 56, 190, 476, 706, 380, 32, 0, 1, 9, 36, 84, 357, 1251, 3034, 3774, 1555, 73, 0, 1, 10, 45, 120, 616, 2814, 9845, 21380, 22140, 6650, 190, 0
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,8
|
|
|
COMMENTS
|
Homeomorphically irreducible trees are trees without vertices of degree 2. All non-leaf nodes then have degree >= 3.
Not all colors need to be used.
The Johnson reference has a mistake in formula 4.3. In particular, the final term should be subtracted rather than added. Compare with the first formula given here. The table of results given in the reference is consequently also incorrect.
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n,k) = k*g(n-1,k) + g(n,k) - Sum_{j=1..n-1} g(j,k)*g(n-j,k) for n > 1 where g(n,k) is A319254(n,k).
G.f. of k-th column: 1 + k*x*r(x) + r(x) - r(x)^2 where r(x) is the g.f. of the k-th column of A319254.
|
|
|
EXAMPLE
|
Array begins:
============================================================
n\k| 0 1 2 3 4 5 6 7
---+--------------------------------------------------------
0 | 1 1 1 1 1 1 1 1 ...
1 | 0 1 2 3 4 5 6 7 ...
2 | 0 1 3 6 10 15 21 28 ...
3 | 0 1 4 10 20 35 56 84 ...
4 | 0 2 11 36 90 190 357 616 ...
5 | 0 3 30 144 476 1251 2814 5656 ...
6 | 0 7 105 706 3034 9845 26383 61572 ...
7 | 0 13 380 3774 21380 85995 274800 744556 ...
8 | 0 32 1555 22140 163670 812160 3086481 9692480 ...
9 | 0 73 6650 137096 1322960 8092945 36550458 132954360 ...
...
|
|
|
PROG
|
(PARI) \\ here R(n, k) is k-th column of A319254.
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
R(n, k)={my(v=[k]); for(n=2, n, v=concat(v, EulerT(concat(v, [0]))[n])); v}
U(n, k)={my(g=x*Ser(R(n, k))); Vec(1 + g + k*x*g - g^2)}
{my(T=Mat(vector(9, k, U(8, k-1)~))); for(n=1, #T~, print(T[n, ]))}
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
