|
|
A319376
|
|
Triangle read by rows: T(n,k) is the number of lone-child-avoiding rooted trees with n leaves of exactly k colors.
|
|
8
|
|
|
1, 1, 1, 2, 6, 4, 5, 30, 51, 26, 12, 146, 474, 576, 236, 33, 719, 3950, 8572, 8060, 2752, 90, 3590, 31464, 108416, 175380, 134136, 39208, 261, 18283, 245916, 1262732, 3124650, 4014348, 2584568, 660032, 766, 94648, 1908858, 14047288, 49885320, 95715728, 101799712, 56555904, 12818912
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
Lone-child-avoiding rooted trees are also called planted series-reduced trees in some other sequences.
|
|
LINKS
|
|
|
FORMULA
|
T(n,k) = Sum_{i=1..k} (-1)^(k-i)*binomial(k,i)*A319254(n,i).
|
|
EXAMPLE
|
Triangle begins:
1;
1, 1;
2, 6, 4;
5, 30, 51, 26;
12, 146, 474, 576, 236;
33, 719, 3950, 8572, 8060, 2752;
90, 3590, 31464, 108416, 175380, 134136, 39208;
261, 18283, 245916, 1262732, 3124650, 4014348, 2584568, 660032;
...
The 12 trees counted by row n = 3:
(111) (112) (123)
(1(11)) (122) (1(23))
(1(12)) (2(13))
(1(22)) (3(12))
(2(11))
(2(12))
(End)
|
|
MAPLE
|
b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
add(binomial(A(i, k)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))
end:
A:= (n, k)-> `if`(n<2, n*k, b(n, n-1, k)):
T:= (n, k)-> add(A(n, k-j)*(-1)^j*binomial(k, j), j=0..k-1):
|
|
MATHEMATICA
|
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[A[i, k] + j - 1, j] b[n - i j, i - 1, k], {j, 0, n/i}]]];
A[n_, k_] := If[n < 2, n k, b[n, n - 1, k]];
T[n_, k_] := Sum[(-1)^(k - i)*Binomial[k, i]*A[n, i], {i, 1, k}];
sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
mtot[m_]:=Prepend[Join@@Table[Tuples[mtot/@p], {p, Select[mps[m], 1<Length[#]<Length[m]&]}], m];
allnorm[n_]:=If[n<=0, {{}}, Function[s, Array[Count[s, y_/; y<=#]+1&, n]]/@Subsets[Range[n-1]+1]];
Table[Sum[Length[Union[mtot[s]]], {s, Select[allnorm[n], Length[Union[#]]==k&]}], {n, 0, 5}, {k, 0, n}] (* Gus Wiseman, Dec 31 2020 *)
|
|
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}
M(n)={my(v=vector(n, k, R(n, k)~)); Mat(vector(n, k, sum(i=1, k, (-1)^(k-i)*binomial(k, i)*v[i])))}
{my(T=M(10)); for(n=1, #T~, print(T[n, ][1..n]))}
|
|
CROSSREFS
|
The unlabeled version, counting inequivalent leaf-colorings of lone-child-avoiding rooted trees, is A330465.
Lone-child-avoiding rooted trees are counted by A001678 (shifted left once).
Labeled lone-child-avoiding rooted trees are counted by A060356.
Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|