

A227341


Triangular array: Number of partitions of the vertex set of a forest of two trees on n vertices into k nonempty independent sets.


1



1, 1, 1, 0, 2, 1, 0, 2, 4, 1, 0, 2, 10, 7, 1, 0, 2, 22, 31, 11, 1, 0, 2, 46, 115, 75, 16, 1, 0, 2, 94, 391, 415, 155, 22, 1, 0, 2, 190, 1267, 2051, 1190, 287, 29, 1, 0, 2, 382, 3991, 9471, 8001, 2912, 490, 37, 1, 0, 2, 766, 12355, 41875, 49476, 25473, 6342, 786, 46, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,5


COMMENTS

For a graph G and a positive integer k, the graphical Stirling number S(G;k) is the number of set partitions of the vertex set of G into k nonempty independent sets (an independent set in G is a subset of the vertices, no two elements of which are adjacent).
Here we take the graph G to be a forest of two trees on n vertices. The corresponding graphical Stirling numbers S(G;k) do not depend on the choice of the trees. See Galvin and Thanh. If the graph G is a single tree on n vertices then the graphical Stirling numbers S(G;k) are the classical Stirling numbers of the second kind A008277. See also A105794.


LINKS

Table of n, a(n) for n=1..66.
B. Duncan and R. Peele, Bell and Stirling Numbers for Graphs, Journal of Integer Sequences 12 (2009), article 09.7.1.
D. Galvin and D. T. Thanh, Stirling numbers of forests and cycles, Electr. J. Comb. Vol. 20(1): P73 (2013)


FORMULA

T(n,k) = Stirling2(n1,k1) + Stirling2(n2,k1), n,k >= 1.
Recurrence equation: T(n,k) = (k1)*T(n1,k) + T(n1,k1). Cf. A105794.
kth column o.g.f.: x^k*(1+x)/((1x)*(12*x)*...*(1(k1)*x)).
For n >= 2, sum {k = 0..n} T(n,k)*x_(k) = x^2*(x1)^(n2), where x_(k) = x*(x1)*...*(xk+1) is the falling factorial.
Column 3: A033484; Column 4: A091344; Row sums are essentially A011968.


EXAMPLE

Triangle begins
n\k  1 2 3 4 5 6 7
= = = = = = = = = = = = =
1  1
2  1 1
3  0 2 1
4  0 2 4 1
5  0 2 10 7 1
6  0 2 22 31 11 1
7  0 2 46 115 75 16 1
Connection constants: Row 5: 2*x*(x1) + 10*x*(x1)*(x2) + 7*x*(x1)*(x2)*(x3) + x*(x1)*(x2)*(x3)*(x4) = x^2*(x1)^3.


CROSSREFS

A008277, A011968 (row sums), A033484 (col. 3), A091344 (col. 4), A105794.
Sequence in context: A115247 A204163 A122542 * A098542 A320019 A141343
Adjacent sequences: A227338 A227339 A227340 * A227342 A227343 A227344


KEYWORD

nonn,easy,tabl


AUTHOR

Peter Bala, Jul 10 2013


STATUS

approved



