proposed

approved

editing

proposed

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

approved

editing

editing

approved

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 non-emptynonempty independent sets (an independent set in G is a subset of the vertices, no two elements of which are adjacent).

approved

editing

reviewed

approved

proposed

reviewed

editing

proposed

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

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 non-empty independent sets (an independent set in G is a subset of the vertices, no two of elements of which are adjacent).

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

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.

allocated Triangular array: Number of partitions of the vertex set of a forest of two trees on n vertices into k fornon-empty Peterindependent Balasets.

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

1,5

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 non-empty independent sets (an independent set in G is a subset of the vertices, no two of 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.

B. Duncan and R. Peele, <a href="https://cs.uwaterloo.ca/journals/JIS/">Bell and Stirling Numbers for Graphs</a>, Journal of Integer Sequences 12 (2009), article 09.7.1.

D. Galvin and D. T. Thanh, <a href="http://www.combinatorics.org/ojs/index.php/eljc/issue/view/Volume20-1">Stirling numbers of forests and cycles</a>, Electr. J. Comb. Vol. 20(1): P73 (2013)

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.

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.

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

allocated

nonn,easy,tabl

Peter Bala, Jul 10 2013

approved

editing