|
| |
|
|
A246118
|
|
T(n,k), for n,k >= 1, is the number of partitions of the set [n] into k blocks, where, if the blocks are arranged in order of their minimal element, the odd-indexed blocks are all singletons.
|
|
3
|
|
|
|
1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 4, 1, 0, 1, 4, 11, 6, 1, 0, 1, 5, 26, 23, 9, 1, 0, 1, 6, 57, 72, 50, 12, 1, 0, 1, 7, 120, 201, 222, 86, 16, 1, 0, 1, 8, 247, 522, 867, 480, 150, 20, 1, 0, 1, 9, 502, 1291, 3123, 2307, 1080, 230, 25, 1, 0, 1, 10, 1013, 3084, 10660, 10044, 6627, 2000, 355, 30, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,9
|
|
|
COMMENTS
|
Unsigned matrix inverse of A246117. Analog of the Stirling numbers of the second kind, A048993.
This is the triangle of connection constants between the monomial polynomials x^n and the polynomial sequence [x, x^2, x^2*(x - 1), x^2*(x - 1)^2, x^2*(x - 1)^2*(x - 2), x^2*(x - 1)^2*(x - 2)^2, ...]. An example is given below.
Except for differences in offset, this triangle is the Galton array G(floor(k/2),1) in the notation of Neuwirth with inverse array G(-floor(n/2),1).
The sums S(n):= Sum_{k >= 0} k^n*(x^k/k!)^2, n = 2,3,4,..., can be expressed as a linear combination of the sums S(0) and S(1) with polynomial coefficients, namely, S(n) = E(n,x)*S(0) + (1/x)*O(n,x)* S(1,x), where E(n,x) = Sum_{k >= 1} T(n,2*k)*x^(2*k) and O(n,x) = Sum_{k >= 0} T(n,2*k+1)*x^(2*k+1) are the even and odd parts of the n-th row polynomial of this array. This result is the analog of the Dobinski formula Sum_{k >= 0} (k^n)*x^k/k! = exp(x)*Bell(n,x), where Bell(n,x) is the n-th row polynomial of A048993.
For example, for n = 6 we have S(6) = Sum_{k >= 1} k^6*(x^k/k!)^2 = (x^2 + 11*x^4 + x^6) * Sum_{k >= 0} (x^k/k!)^2 + (1/x)*(4*x^3 + 6*x^5) * Sum_{k >= 1} k*(x^k/k!)^2.
Setting x = 1 in the above result gives Sum_{k >= 0} k^n*/k!^2 = A000994(n)*Sum_{k >= 0} 1/k!^2 + A000995(n)*Sum_{k >= 1} k/k!^2. See A086880. (End)
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n,k) = Sum_{i = 0..n-1} Stirling2(i, floor(k/2))*Stirling2(n-i-1, floor((k - 1)/2)) for n,k >= 1.
Recurrence equation: T(1,1) = 1, T(n,1) = 0 for n >= 2; T(n,k) = 0 for k > n; otherwise T(n,k) = floor(k/2)*T(n-1,k) + T(n-1,k-1).
O.g.f. (with an extra 1): A(z) = 1 + Sum_{k >= 1} (x*z)^k/( ( Product_{i = 1..floor((k-1)/2)} (1 - i*z) ) * ( Product_{i = 1..floor(k/2)} (1 - i*z) ) ) = 1 + x*z + x^2*z^2 + (x^2 + x^3)*z^3 + (x^2 + 2*x^3 + x^4)*z^4 + .... satisfies A(z) = 1 + x*z + x^2*z^2/(1 - z)*A(z/(1 - z)).
k-th column generating function z^k/( ( Product_{i = 1..floor((k-1)/2)} (1 - i*z) ) * ( Product_{i = 1..floor(k/2)} (1 - i*z) ) ).
Recurrence for row polynomials: R(n,x) = x^2*Sum_{k = 0..n-2} binomial(n-2,k)*R(k,x) with initial conditions R(0,x) = 1 and R(1,x) = x. Compare with the recurrence satisfied by the Bell polynomials: Bell(n,x) = x*Sum_{k = 0..n-1} binomial(n-1,k) * Bell(k,x).
|
|
|
EXAMPLE
|
Triangle begins
n\k| 1 2 3 4 5 6 7 8
1 | 1
2 | 0 1
3 | 0 1 1
4 | 0 1 2 1
5 | 0 1 3 4 1
6 | 0 1 4 11 6 1
7 | 0 1 5 26 23 9 1
8 | 0 1 6 57 72 50 12 1
...
Connection constants: Row 6 = (0, 1, 4, 11, 6, 1) so
x^6 = x^2 + 4*x^2*(x - 1) + 11*x^2*(x - 1)^2 + 6*x^2*(x - 1)^2*(x - 2) + x^2*(x - 1)^2*(x - 2)^2.
Row 5 = [0, 1, 3, 4, 1]. There are 9 set partitions of {1,2,3,4,5} of the type described in the Name section:
= = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Number of Set partitions Count
blocks
= = = = = = = = = = = = = = = = = = = = = = = = = = = = =
2 {1}{2,3,4,5} 1
3 {1}{2,4,5}{3}, {1}{2,3,5}{4},
{1}{2,3,4}{5} 3
4 {1}{2,3}{4}{5}, {1}{2,4}{3}{5},
{1}{2,5}{3}{4}, {1}{2}{3}{4,5} 4
5 {1}{2}{3}{4}{5} 1
|
|
|
MATHEMATICA
|
Flatten[Table[Table[Sum[StirlingS2[j, Floor[k/2]] * StirlingS2[n-j-1, Floor[(k-1)/2]], {j, 0, n-1}], {k, 1, n}], {n, 1, 12}]] (* Vaclav Kotesovec, Feb 09 2015 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
