cp's OEIS Frontend

A319376 Triangle read by rows: T(n,k) is the number of lone-child-avoiding rooted trees with n leaves of exactly k colors.

%I A319376 #24 Jan 22 2021 20:26:44
%S A319376 1,1,1,2,6,4,5,30,51,26,12,146,474,576,236,33,719,3950,8572,8060,2752,
%T A319376 90,3590,31464,108416,175380,134136,39208,261,18283,245916,1262732,
%U A319376 3124650,4014348,2584568,660032,766,94648,1908858,14047288,49885320,95715728,101799712,56555904,12818912
%N A319376 Triangle read by rows: T(n,k) is the number of lone-child-avoiding rooted trees with n leaves of exactly k colors.
%C A319376 Lone-child-avoiding rooted trees are also called planted series-reduced trees in some other sequences.
%H A319376 Andrew Howroyd, <a href="/A319376/b319376.txt">Table of n, a(n) for n = 1..1275</a> (first 50 rows)
%F A319376 T(n,k) = Sum_{i=1..k} (-1)^(k-i)*binomial(k,i)*A319254(n,i).
%F A319376 Sum_{k=1..n} k * T(n,k) = A326396(n). - _Alois P. Heinz_, Sep 11 2019
%e A319376 Triangle begins:
%e A319376     1;
%e A319376     1,     1;
%e A319376     2,     6,      4;
%e A319376     5,    30,     51,      26;
%e A319376    12,   146,    474,     576,     236;
%e A319376    33,   719,   3950,    8572,    8060,   2752;
%e A319376    90,  3590,  31464,  108416,  175380,  134136,   39208;
%e A319376   261, 18283, 245916, 1262732, 3124650, 4014348, 2584568, 660032;
%e A319376   ...
%e A319376 From _Gus Wiseman_, Dec 31 2020: (Start)
%e A319376 The 12 trees counted by row n = 3:
%e A319376   (111)    (112)    (123)
%e A319376   (1(11))  (122)    (1(23))
%e A319376            (1(12))  (2(13))
%e A319376            (1(22))  (3(12))
%e A319376            (2(11))
%e A319376            (2(12))
%e A319376 (End)
%p A319376 b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
%p A319376       add(binomial(A(i, k)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))
%p A319376     end:
%p A319376 A:= (n, k)-> `if`(n<2, n*k, b(n, n-1, k)):
%p A319376 T:= (n, k)-> add(A(n, k-j)*(-1)^j*binomial(k, j), j=0..k-1):
%p A319376 seq(seq(T(n, k), k=1..n), n=1..10);  # _Alois P. Heinz_, Sep 18 2018
%t A319376 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}]]];
%t A319376 A[n_, k_] := If[n < 2, n k, b[n, n - 1, k]];
%t A319376 T[n_, k_] := Sum[(-1)^(k - i)*Binomial[k, i]*A[n, i], {i, 1, k}];
%t A319376 Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Sep 24 2019, after _Alois P. Heinz_ *)
%t A319376 sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];
%t A319376 mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
%t A319376 mtot[m_]:=Prepend[Join@@Table[Tuples[mtot/@p],{p,Select[mps[m],1<Length[#]<Length[m]&]}],m];
%t A319376 allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
%t A319376 Table[Sum[Length[Union[mtot[s]]],{s,Select[allnorm[n],Length[Union[#]]==k&]}],{n,0,5},{k,0,n}] (* _Gus Wiseman_, Dec 31 2020 *)
%o A319376 (PARI) \\ here R(n,k) is k-th column of A319254.
%o A319376 EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
%o A319376 R(n, k)={my(v=[k]); for(n=2, n, v=concat(v, EulerT(concat(v, [0]))[n])); v}
%o A319376 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])))}
%o A319376 {my(T=M(10)); for(n=1, #T~, print(T[n, ][1..n]))}
%Y A319376 Columns k=1..2 are A000669, A319377.
%Y A319376 Main diagonal is A000311.
%Y A319376 Row sums are A316651.
%Y A319376 Cf. A141610, A242249, A255517, A256064, A256068, A319254, A319541, A326396.
%Y A319376 The unlabeled version, counting inequivalent leaf-colorings of lone-child-avoiding rooted trees, is A330465.
%Y A319376 Lone-child-avoiding rooted trees are counted by A001678 (shifted left once).
%Y A319376 Labeled lone-child-avoiding rooted trees are counted by A060356.
%Y A319376 Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636.
%Y A319376 Cf. A000014, A000081, A000169, A005804, A206429, A330951.
%K A319376 nonn,tabl
%O A319376 1,4
%A A319376 _Andrew Howroyd_, Sep 17 2018