A105819 Triangle of the numbers of different forests of m rooted trees of smallest order 2, i.e., without isolated vertices, on N labeled nodes.

0, 2, 0, 9, 0, 0, 64, 12, 0, 0, 625, 180, 0, 0, 0, 7776, 2730, 120, 0, 0, 0, 117649, 46410, 3780, 0, 0, 0, 0, 2097152, 893816, 99120, 1680, 0, 0, 0, 0, 43046721, 19389384, 2600640, 90720, 0, 0, 0, 0, 0, 1000000000, 469532790, 71734320, 3654000, 30240, 0

Offset: 1

Author

Washington Bomfim, Apr 21 2005

Keywords

• nonn
• tabl

Comments

Forests of order N with m components, m > floor(N/2) must contain an isolated vertex since it is impossible to partition N vertices in floor(N/2) + 1 or more trees without giving only one vertex to a tree.

Also the Bell transform of A055860. For the definition of the Bell transform see A264428. - Peter Luschny, Jan 27 2016

Examples

			a(8) = 12 because 4 vertices can be partitioned in two trees only in one way: both trees receiving 2 vertices. Two trees on 2 vertices can be labeled in binomial(4,2) ways and to each one of the 2*binomial(4,2) = 12 possibilities there are more 2 possible trees of order 2 in a forest. But since we have 2 trees of the same order, i.e., 2, we must divide 2*binomial(4,2)*2 by 2!.
Triangle T(n,k) begins:
:       0;
:       2,      0;
:       9,      0,     0;
:      64,     12,     0,    0;
:     625,    180,     0,    0, 0;
:    7776,   2730,   120,    0, 0, 0;
:  117649,  46410,  3780,    0, 0, 0, 0;
: 2097152, 893816, 99120, 1680, 0, 0, 0, 0;
		

Links

• Alois P. Heinz, Rows n = 1..141, flattened

Crossrefs

Cf. A033185, A055860, A105599, A354794, A360193.

Row sums give A105785.

Programs

Maple

# The function BellMatrix is defined in A264428.
# Adds (1,0,0,0, ..) as column 0.
BellMatrix(n -> `if`(n=0,0,(n+1)^n), 9); # Peter Luschny, Jan 27 2016
# second Maple program:
b:= proc(n) option remember; expand(`if`(n=0, 1, add(
       binomial(n-1, j-1)*j^(j-1)*x*b(n-j), j=2..n)))
    end:
T:= (n, k)-> coeff(b(n), x, k):
seq(seq(T(n, k), k=1..n), n=1..12);  # Alois P. Heinz, Aug 13 2017

Mathematica

BellMatrix[f_, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len - 1}, {k, 0, len - 1}]];
rows = 12;
B = BellMatrix[Function[n, If[n == 0, 0, (n+1)^n]], rows];
Table[B[[n, k]], {n, 2, rows}, {k, 2, n}] // Flatten (* Jean-François Alcover, Jun 28 2018, after Peter Luschny *)

Formula

a(n)= 0, if m > floor(N/2) (see comments), or can be calculated by the sum Num/D over the partitions of N: 1K1 + 2K2 + ... + nKN, with exactly m parts and smallest part = 2, where Num = N!*Product_{i=1..N}i^((i-1)Ki) and D = Product_{i=1..N}(Ki!(i!)^Ki).

From Mélika Tebni, Apr 23 2023: (Start)

E.g.f. of column k: (-x - LambertW(-x))^k / k!, k > 0.

Sum_{k=1..n} (-1)^(n-k)*T(n+k,k) = n+1.

Sum_{k=1..n} (-1)^(k+1)*T(n,k) = A360193(n), for n > 0.

Sum_{k=1..n} (-1)^(k+1)*T(n+k,k)/(n+k-1) = 1/n, for n > 1.

T(n,k) = Sum_{j=k..n} j!*abs(Stirling1(j-k,k))*A354794(n,j)/(j-k)!. (End)