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.

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

Offset: 1

Author

Peter Bala, Aug 14 2014

Keywords

• nonn
• easy
• tabl

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).

Essentially the same as A256161. - Peter Bala, Apr 14 2018

From Peter Bala, Feb 10 2020: (Start)

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)

Examples

			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
		

Links

• Yue Cai and Margaret Readdy, Negative q-Stirling numbers, arXiv:1506.03249 [math.CO], 2015.
• Emrah Kiliç and Helmut Prodinger, Identities with Squares of Binomial Coefficients: an Elementary and Explicit Approach, Publications de l'Institut Mathématique (Beograd) (N.S.), Vol.99(113) (2016), 243-248. See p. 248.
• Erich Neuwirth, Recursively defined combinatorial functions: Extending Galton's board, Tech Report TR 99-05, 1999.
• E. Neuwirth, Recursively defined combinatorial functions: Extending Galton's board, Discrete Math. 239 (2001) 33-51.

Crossrefs

Cf. A000295 (column 4), A007476 (row sums), A008277, A045618 (column 5), A048993, A246117 (unsigned matrix inverse), A256161, A000994, A000995, A086880.

Programs

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 *)

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).

Row sums are A007476.