login
Triangle T(n,k) = number of forests of labeled rooted trees of height at most 1, with n labels, k of which are used for root nodes and any root may contain >= 1 labels, n >= 0, 0<=k<=n.
12

%I #39 Jan 14 2021 17:35:32

%S 1,0,1,0,2,2,0,3,9,5,0,4,30,40,15,0,5,90,220,185,52,0,6,255,1040,1485,

%T 906,203,0,7,693,4550,9905,9891,4718,877,0,8,1820,19040,59850,87416,

%U 66808,26104,4140,0,9,4644,77448,341082,686826,750120,463212,153063,21147

%N Triangle T(n,k) = number of forests of labeled rooted trees of height at most 1, with n labels, k of which are used for root nodes and any root may contain >= 1 labels, n >= 0, 0<=k<=n.

%H Alois P. Heinz, <a href="/A143396/b143396.txt">Rows n = 0..140, flattened</a>

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

%F T(n,k) = C(n,k) * Sum_{t=0..k} Stirling2(k,t) * t^(n-k).

%F E.g.f.: exp(exp(x)*(exp(x*y)-1)). - _Vladeta Jovovic_, Dec 08 2008

%e T(3,2) = 9: {1,2}<-3, {1,3}<-2, {2,3}<-1, {1}<-3{2}, {1}{2}<-3, {1}<-2{3}, {1}{3}<-2, {2}<-1{3}, {2}{3}<-1.

%e Triangle begins:

%e 1;

%e 0, 1;

%e 0, 2, 2;

%e 0, 3, 9, 5;

%e 0, 4, 30, 40, 15;

%e 0, 5, 90, 220, 185, 52;

%e ...

%p T:= (n, k)-> binomial(n, k)*add(Stirling2(k, t)*t^(n-k), t=0..k):

%p seq(seq(T(n, k), k=0..n), n=0..11);

%t T[n_, k_] := T[n, k] = Binomial[n, k]*Sum[StirlingS2[k, t]*If[n == k, 1, t^(n - k)], {t, 0, k}];

%t Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, May 27 2016, translated from Maple, updated Jan 01 2021 *)

%Y Columns k=0-10 give: A000007, A000027, A273652, A273653, A273654, A273655, A273656, A273657, A273658, A273659, A273660.

%Y Diagonal gives A000110.

%Y Row sums give A143405.

%Y T(2n,n) gives A273661.

%Y Cf. A048993, A008277, A007318.

%K nonn,tabl

%O 0,5

%A _Alois P. Heinz_, Aug 12 2008