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

Offset: 1

Author

Peter Bala, Jul 10 2013

Keywords

• nonn
• easy
• tabl

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.

Examples

			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*(x-1) + 10*x*(x-1)*(x-2) + 7*x*(x-1)*(x-2)*(x-3) + x*(x-1)*(x-2)*(x-3)*(x-4) = x^2*(x-1)^3.
		

Links

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

Crossrefs

A008277, A011968 (row sums), A033484 (col. 3), A091344 (col. 4), A105794.

Formula

T(n,k) = Stirling2(n-1,k-1) + Stirling2(n-2,k-1), n,k >= 1.

Recurrence equation: T(n,k) = (k-1)*T(n-1,k) + T(n-1,k-1). Cf. A105794.

k-th column o.g.f.: x^k*(1+x)/((1-x)*(1-2*x)*...*(1-(k-1)*x)).

For n >= 2, sum {k = 0..n} T(n,k)*x_(k) = x^2*(x-1)^(n-2), where x_(k) = x*(x-1)*...*(x-k+1) is the falling factorial.

Column 3: A033484; Column 4: A091344; Row sums are essentially A011968.