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

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*(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.

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