login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
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
KEYWORD
nonn,easy,tabl
AUTHOR
Peter Bala, Jul 10 2013
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 11:14 EDT 2024. Contains 371278 sequences. (Running on oeis4.)