%I #49 Mar 14 2024 11:03:40
%S 1,4,1,16,9,1,64,61,15,1,256,369,151,22,1,1024,2101,1275,305,30,1,
%T 4096,11529,9751,3410,545,39,1,16384,61741,70035,33621,7770,896,49,1,
%U 65536,325089,481951,305382,95781,15834,1386,60,1,262144,1690981,3216795
%N 4-Stirling numbers of the second kind.
%C This is the case r = 4 of the r-Stirling numbers of the second kind. The 4-Stirling numbers of the second kind count the ways of partitioning the set {1,2,...,n} into k nonempty disjoint subsets with the restriction that the elements 1, 2, 3 and 4 belong to distinct subsets. For remarks on the general case see A143494 (r = 2). The corresponding array of 4-Stirling numbers of the first kind is A143493. The theory of r-Stirling numbers of both kinds is developed in [Broder]. For 4-Lah numbers refer to A143499.
%C From _Wolfdieter Lang_, Sep 29 2011: (Start)
%C T(n,k) = S(n,k,4), n >= k >= 4, in Mikhailov's first paper, eq.(28) or (A3). E.g.f. column k from (A20) with k->4, r->k. Therefore, with offset [0,0], this triangle is the Sheffer triangle (exp(4*x),exp(x)-1) with e.g.f. of column no. m >= 0: exp(4*x)*((exp(x)-1)^m)/m!. See one of the formulas given below. For Sheffer matrices see the W. Lang link under A006232 with the S. Roman reference, also found in A132393.
%C (End)
%H Andrei Z. Broder, <a href="http://infolab.stanford.edu/TR/CS-TR-82-949.html">The r-Stirling numbers</a>, Report Number: CS-TR-82-949, Stanford University, Department of Computer Science; see <a href="https://doi.org/10.1016/0012-365X(84)90161-4">also</a>, Discrete Math. 49, 241-259 (1984).
%H Askar Dzhumadil'daev and Damir Yeliussizov, <a href="https://arxiv.org/abs/1408.6764v1">Path decompositions of digraphs and their applications to Weyl algebra</a>, arXiv preprint arXiv:1408.6764v1 [math.CO], 2014. [Version 1 contained many references to the OEIS, which were removed in Version 2. - _N. J. A. Sloane_, Mar 28 2015]
%H Askar Dzhumadil'daev and Damir Yeliussizov, <a href="https://doi.org/10.37236/5181">Walks, partitions, and normal ordering</a>, Electronic Journal of Combinatorics, 22(4) (2015), #P4.10.
%H Paweł Hitczenko, <a href="https://arxiv.org/abs/2403.03422">A class of polynomial recurrences resulting in (n/log n, n/log^2 n)-asymptotic normality</a>, arXiv:2403.03422 [math.CO], 2024. See p. 8.
%H V. V. Mikhailov, <a href="http://dx.doi.org/10.1088/0305-4470/16/16/019">Ordering of some boson operator functions</a>, J. Phys A: Math. Gen. 16 (1983) 3817-3827.
%H V. V. Mikhailov, <a href="http://dx.doi.org/10.1088/0305-4470/18/2/012">Normal ordering and generalised Stirling numbers</a>, J. Phys A: Math. Gen. 18 (1985) 231-235.
%H Erich Neuwirth, <a href="http://homepage.univie.ac.at/erich.neuwirth/papers/TechRep99-05.pdf">Recursively defined combinatorial functions: Extending Galton's board</a>, Discrete Math. 239 No. 1-3, 33-51 (2001)
%H Lily L. Liu and Yi Wang, <a href="https://arxiv.org/abs/math/0509207">A unified approach to polynomial sequences with only real zeros</a>, arXiv:math/0509207 [math.CO], 2005-2006.
%H Michael J. Schlosser and Meesue Yoo, <a href="https://doi.org/10.37236/6121">Elliptic Rook and File Numbers</a>, Electronic Journal of Combinatorics, 24(1) (2017), #P1.31.
%F T(n+4,k+4) = (1/k!)*Sum_{i = 0..k} (-1)^(k-i)*C(k,i)*(i+4)^n, n,k >= 0.
%F T(n,k) = Stirling2(n,k) - 6*Stirling2(n-1,k) + 11*Stirling2(n-2,k) - 6*Stirling2(n-3,k) for n,k >= 4.
%F Recurrence relation: T(n,k) = T(n-1,k-1) + k*T(n-1,k) for n > 4 with boundary conditions: T(n,3) = T(3,n) = 0 for all n; T(4,4) = 1; T(4,k) = 0 for k > 4. Special cases: T(n,4) = 4^(n-4); T(n,5) = 5^(n-4) - 4^(n-4).
%F E.g.f. (k+4)-th column (with offset 4): (1/k!)*exp(4*x)*(exp(x)-1)^k.
%F O.g.f. k-th column: Sum_{n>=k} T(n,k)*x^n = x^k/((1-4*x)*(1-5*x)*...*(1-k*x)).
%F E.g.f.: exp(4*t + x*(exp(t)-1)) = Sum_{n = 0..infinity} Sum_(k = 0..n) T(n+4,k+4)*x^k*t^n/n! = Sum_{n = 0..infinity} B_n(4;x)*t^n/n! = 1 + (4+x)*t/1! + (16+9*x+x^2)*t^2/2! + ..., where the row polynomials, B_n(4;x) := Sum_{k = 0..n} T(n+4,k+4)*x^k, may be called the 4-Bell polynomials.
%F Dobinski-type identities: Row polynomial B_n(4;x) = exp(-x)*Sum_{i = 0..infinity} (i+4)^n*x^i/i!; Sum_{k = 0..n} k!*T(n+4,k+4)*x^k = Sum_{i = 0..infinity} (i+4)^n*x^i/(1+x)^(i+1).
%F The T(n,k) are the connection coefficients between the falling factorials and the shifted monomials (x+4)^(n-4). For example, 16 + 9*x + x*(x-1) = (x+4)^2; 64 + 61*x + 15*x*(x-1) + x*(x-1)*(x-2) = (x+4)^3.
%F This array is the matrix product P^3 * S, where P denotes Pascal's triangle, A007318 and S denotes the lower triangular array of Stirling numbers of the second kind, A008277 (apply Theorem 10 of [Neuwirth]).
%F The inverse array is A049459, the signed 4-Stirling numbers of the first kind.
%F From _Peter Bala_, Sep 19 2008: (Start)
%F Let D be the derivative operator d/dx and E the Euler operator x*d/dx. Then x^(-4)*E^n*x^4 = Sum_{k = 0..n} T(n+4,k+4)*x^k*D^k.
%F The row generating polynomials R_n(x) := Sum_{k=4..n} T(n,k)*x^k satisfy the recurrence R_(n+1)(x) = x*R_n(x) + x*d/dx(R_n(x)) with R_4(x) = x^4. It follows that the polynomials R_n(x) have only real zeros (apply Corollary 1.2. of [Liu and Wang]).
%F Relation with the 4-Eulerian numbers E_4(n,j) := A144698(n,j): T(n,k) = 4!/k!*Sum_{j = n-k..n-4} E_4(n,j)*binomial(j,n-k) for n >= k >= 4.
%F (End)
%e Triangle begins
%e n\k|.....4.....5.....6.....7.....8.....9
%e ========================================
%e 4..|.....1
%e 5..|.....4.....1
%e 6..|....16.....9.....1
%e 7..|....64....61....15.....1
%e 8..|...256...369...151....22.....1
%e 9..|..1024..2101..1275...305....30.....1
%e ...
%e T(6,5) = 9. The set {1,2,3,4,5,6} can be partitioned into five subsets such that 1, 2, 3 and 4 belong to different subsets in 9 ways: {{1,5}{2}{3}{4}{6}}, {{1,6}{2}{3}{4}{5}}, {{2,5}{1}{3}{4}{6}}, {{2,6}{1}{3}{4}{5}}, {{3,5}{1}{2}{4}{6}}, {{3,6}{1}{2}{4}{5}}, {{4,5}{1}{2}{3}{6}}, {{4,6}{1}{2}{3}{5}} and {{5,6}{1}{2}{3}{4}}.
%p with combinat: T := (n, k) -> 1/(k-4)!*add ((-1)^(k-i)*binomial(k-4,i)*(i+4)^(n-4),i = 0..k-4): for n from 4 to 13 do seq(T(n, k), k = 4..n) end do;
%t t[n_, k_] := StirlingS2[n, k] - 6*StirlingS2[n-1, k] + 11*StirlingS2[n-2, k] - 6*StirlingS2[n-3, k]; Flatten[ Table[ t[n, k], {n, 4, 13}, {k, 4, n}]] (* _Jean-François Alcover_, Dec 02 2011 *)
%Y Cf. A003468 (column 7), A005060 (column 5), A008277, A016103 (column 6), A045379 (row sums), A049459 (matrix inverse), A143493, A143494, A143495, A143499.
%K easy,nonn,tabl
%O 4,2
%A _Peter Bala_, Aug 20 2008