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, 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

Author

Washington Bomfim, May 19 2005

Keywords

• easy
• nonn
• tabl

Comments

Row sums equal A101313 (Number of painted forests - exactly one of its trees is painted - on labeled vertex set [n].).

Examples

			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;
		

Links

• Alois P. Heinz, Rows n = 1..141, flattened
• Washington Bomfim, Illustration Of This Sequence. [Broken link?]

Crossrefs

Cf. A101313, A105599, A106240.

Programs

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 *)

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