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

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

Links

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

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)

Example

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;

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

Crossrefs

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

Row sums give A105785.

Sequence in context: A193247 A091041 A140415 * A153616 A190258 A161119

Adjacent sequences: A105816 A105817 A105818 * A105820 A105821 A105822

Keyword

nonn,tabl

Author

Washington Bomfim, Apr 21 2005

Status

approved