login
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

%I #30 Nov 13 2022 09:32:29

%S 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,

%T 72,50,12,1,0,1,7,120,201,222,86,16,1,0,1,8,247,522,867,480,150,20,1,

%U 0,1,9,502,1291,3123,2307,1080,230,25,1,0,1,10,1013,3084,10660,10044,6627,2000,355,30,1

%N 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.

%C Unsigned matrix inverse of A246117. Analog of the Stirling numbers of the second kind, A048993.

%C 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.

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

%C Essentially the same as A256161. - _Peter Bala_, Apr 14 2018

%C From _Peter Bala_, Feb 10 2020: (Start)

%C 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.

%C 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.

%C 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)

%H Yue Cai and Margaret Readdy, <a href="http://arxiv.org/abs/1506.03249">Negative q-Stirling numbers</a>, arXiv:1506.03249 [math.CO], 2015.

%H Emrah Kiliç and Helmut Prodinger, <a href="https://doi.org/10.2298/PIM1613243K">Identities with Squares of Binomial Coefficients: an Elementary and Explicit Approach</a>, Publications de l'Institut Mathématique (Beograd) (N.S.), Vol.99(113) (2016), 243-248. See p. 248.

%H Erich Neuwirth, <a href="https://web.archive.org/web/20200710060956/http://homepage.univie.ac.at/erich.neuwirth/papers/TechRep99-05.pdf">Recursively defined combinatorial functions: Extending Galton's board</a>, Tech Report TR 99-05, 1999.

%H E. Neuwirth, <a href="https://doi.org/10.1016/S0012-365X(00)00373-3">Recursively defined combinatorial functions: Extending Galton's board</a>, Discrete Math. 239 (2001) 33-51.

%F 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.

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

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

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

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

%F Row sums are A007476.

%e Triangle begins

%e n\k| 1 2 3 4 5 6 7 8

%e 1 | 1

%e 2 | 0 1

%e 3 | 0 1 1

%e 4 | 0 1 2 1

%e 5 | 0 1 3 4 1

%e 6 | 0 1 4 11 6 1

%e 7 | 0 1 5 26 23 9 1

%e 8 | 0 1 6 57 72 50 12 1

%e ...

%e Connection constants: Row 6 = (0, 1, 4, 11, 6, 1) so

%e 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.

%e 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:

%e = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

%e Number of Set partitions Count

%e blocks

%e = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

%e 2 {1}{2,3,4,5} 1

%e 3 {1}{2,4,5}{3}, {1}{2,3,5}{4},

%e {1}{2,3,4}{5} 3

%e 4 {1}{2,3}{4}{5}, {1}{2,4}{3}{5},

%e {1}{2,5}{3}{4}, {1}{2}{3}{4,5} 4

%e 5 {1}{2}{3}{4}{5} 1

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

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

%K nonn,easy,tabl

%O 1,9

%A _Peter Bala_, Aug 14 2014