|
%I #12 Dec 11 2015 22:11:46
%S 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,
%T 94,391,415,155,22,1,0,2,190,1267,2051,1190,287,29,1,0,2,382,3991,
%U 9471,8001,2912,490,37,1,0,2,766,12355,41875,49476,25473,6342,786,46,1
%N Triangular array: Number of partitions of the vertex set of a forest of two trees on n vertices into k nonempty independent sets.
%C 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).
%C 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.
%H 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.
%H 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)
%F T(n,k) = Stirling2(n-1,k-1) + Stirling2(n-2,k-1), n,k >= 1.
%F Recurrence equation: T(n,k) = (k-1)*T(n-1,k) + T(n-1,k-1). Cf. A105794.
%F k-th column o.g.f.: x^k*(1+x)/((1-x)*(1-2*x)*...*(1-(k-1)*x)).
%F 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.
%F Column 3: A033484; Column 4: A091344; Row sums are essentially A011968.
%e Triangle begins
%e n\k | 1 2 3 4 5 6 7
%e = = = = = = = = = = = = =
%e 1 | 1
%e 2 | 1 1
%e 3 | 0 2 1
%e 4 | 0 2 4 1
%e 5 | 0 2 10 7 1
%e 6 | 0 2 22 31 11 1
%e 7 | 0 2 46 115 75 16 1
%e 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.
%Y A008277, A011968 (row sums), A033484 (col. 3), A091344 (col. 4), A105794.
%K nonn,easy,tabl
%O 1,5
%A _Peter Bala_, Jul 10 2013
|
