login
A106834
Triangle read by rows: T(n, m) = number of painted forests on labeled vertex set [n] with m trees. Also number of painted forests with exactly n - m edges.
1
1, 1, 2, 3, 6, 3, 16, 30, 18, 4, 125, 220, 135, 40, 5, 1296, 2160, 1305, 420, 75, 6, 16807, 26754, 15750, 5180, 1050, 126, 7, 262144, 401408, 229824, 75460, 16100, 2268, 196, 8, 4782969, 7085880, 3949722, 1282176, 278775, 42336, 4410, 288, 9
OFFSET
1,3
COMMENTS
Row sums equal A101313 (Number of painted forests - exactly one of its trees is painted - on labeled vertex set [n].).
LINKS
Washington Bomfim, Illustration Of This Sequence. [Broken link?]
FORMULA
T(n, m)= m * f(n, m), where f(n, m) = number of forests with n nodes and m labeled trees, A105599.
E.g.f.: y*B(x)*exp(y*B(x)), where B(x) is e.g.f. for A000272. - Vladeta Jovovic, May 24 2005
EXAMPLE
T(4,3) = 18 because there are 18 such forests with 4 nodes and 3 trees. (See the illustration of this sequence).
Triangle begins:
1;
1, 2;
3, 6, 3;
16, 30, 18, 4;
125, 220, 135, 40, 5;
1296, 2160, 1305, 420, 75, 6;
16807, 26754, 15750, 5180, 1050, 126, 7;
MAPLE
f:= proc(n, m) option remember;
if n<0 then 0
elif n=m then 1
elif m<1 or m>n then 0
else add(binomial(n-1, j-1) *j^(j-2) *f(n-j, m-1), j=1..n-m+1)
fi
end:
T:= (n, m)-> m*f(n, m):
seq(seq(T(n, m), m=1..n), n=1..12); # Alois P. Heinz, Sep 10 2008
MATHEMATICA
f[n_, m_] := f[n, m] = Which[n<0, 0, n == m, 1, m<1 || m>n, 0, True, Sum[ Binomial[n-1, j-1]*j^(j-2)*f[n-j, m-1], {j, 1, n-m+1}]]; T[n_, m_] := m*f[n, m]; Table[Table[T[n, m], {m, 1, n}], {n, 1, 12}] // Flatten (* Jean-François Alcover, Feb 25 2015, after Alois P. Heinz *)
CROSSREFS
KEYWORD
easy,nonn,tabl
AUTHOR
Washington Bomfim, May 19 2005
STATUS
approved