|
%I #92 Mar 14 2024 15:31:35
%S 1,2,1,4,5,1,8,19,9,1,16,65,55,14,1,32,211,285,125,20,1,64,665,1351,
%T 910,245,27,1,128,2059,6069,5901,2380,434,35,1,256,6305,26335,35574,
%U 20181,5418,714,44,1,512,19171,111645,204205,156660,58107,11130,1110,54,1
%N Triangle read by rows: 2-Stirling numbers of the second kind.
%C This is the case r = 2 of the r-Stirling numbers of the second kind. The 2-Stirling numbers of the second kind give the number of ways of partitioning the set {1,2,...,n} into k nonempty disjoint subsets with the restriction that the elements 1 and 2 belong to distinct subsets.
%C More generally, the r-Stirling numbers of the second kind give the number of ways of partitioning the set {1,2,...,n} into k nonempty disjoint subsets with the restriction that the numbers 1, 2, ..., r belong to distinct subsets. The case r = 1 gives the usual Stirling numbers of the second kind A008277; for other cases see A143495 (r = 3) and A143496 (r = 4).
%C The lower unitriangular array of r-Stirling numbers of the second kind equals the matrix product P^(r-1) * S (with suitable offsets in the row and column indexing), where P is Pascal's triangle, A007318 and S is the array of Stirling numbers of the second kind, A008277.
%C For the definition of and entries relating to the corresponding r-Stirling numbers of the first kind see A143491. For entries on r-Lah numbers refer to A143497. The theory of r-Stirling numbers of both kinds is developed in [Broder].
%C From _Peter Bala_, Sep 19 2008: (Start)
%C Let D be the derivative operator d/dx and E the Euler operator x*d/dx. Then x^(-2)*E^n*x^2 = Sum_{k = 0..n} T(n+2,k+2)*x^k*D^k.
%C The row generating polynomials R_n(x) := Sum_{k= 2..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_2(x) = x^2. It follows that the polynomials R_n(x) have only real zeros (apply Corollary 1.2. of [Liu and Wang]).
%C Relation with the 2-Eulerian numbers E_2(n,j) := A144696(n,j): T(n,k) = 2!/k!*Sum_ {j = n-k..n-2} E_2(n,j)*binomial(j,n-k) for n >= k >= 2. (End)
%C From _Wolfdieter Lang_, Sep 29 2011: (Start)
%C T(n,k)=S(n,k,2), n>=k>=2, in Mikhailov's first paper, eq.(28) or (A3). E.g.f. column no. k from (A20) with k->2, r->k. Therefore, with offset [0,0], this triangle is the Sheffer triangle (exp(2*x),exp(x)-1) with e.g.f. of column no. m>=0: exp(2*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. (End)
%H S. Alex Bradt, Jennifer Elder, Pamela E. Harris, Gordon Rojas Kirby, Eva Reutercrona, Yuxuan (Susan) Wang, and Juliet Whidden, <a href="https://arxiv.org/abs/2401.06937">Unit interval parking functions and the r-Fubini numbers</a>, arXiv:2401.06937 [math.CO], 2024. See page 2.
%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, 1982, Stanford University, Department of Computer Science.
%H Andrei Z. Broder, <a href="https://doi.org/10.1016/0012-365X(84)90161-4">The r-Stirling numbers</a>, Discrete Math. 49, 241-259 (1984).
%H C. B. Corcino, L. C. Hsu, and E. L. Tan, <a href="http://dx.doi.org/10.1007/BF02837121">Asymptotic approximations of r-Stirling numbers</a>, Approximation Theory Appl. 15, No. 3 13-25 (1999).
%H A. Dzhumadildaev and D. Yeliussizov, <a href="http://arxiv.org/abs/1408.6764">Path decompositions of digraphs and their applications to Weyl algebra</a>, arXiv preprint arXiv:1408.6764 [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 Eldar Fischer, Johann A. Makowsky, and Vsevolod Rakita, <a href="https://arxiv.org/abs/2302.08265">MC-finiteness of restricted set partition functions</a>, arXiv:2302.08265 [math.CO], 2023.
%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 L. Liu and Y. 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 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="https://web.archive.org/web/20070707064322/https://homepage.univie.ac.at/erich.neuwirth/papers/TechRep99-05.pdf">Recursively defined combinatorial functions: Extending Galton's board</a>, Technical Report TR 99-05, July 1999, Universität Wien.
%H Erich Neuwirth, <a href="https://doi.org/10.1016/S0012-365X(00)00373-3f">Recursively defined combinatorial functions: Extending Galton's board</a>, Discrete Math. 239 No. 1-3, 33-51 (2001).
%H M. d’Ocagne, <a href="https://archive.org/details/jstor-2369478">Sur une classe de nombres remarquables</a>, Amer. J. Math., Vol. 9 (1887), 353-380.
%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.
%H Mark Shattuck, <a href="https://arxiv.org/abs/1412.8721">Generalized r-Lah numbers</a>, arXiv:1412.8721 [math.CO], 2014.
%F T(n+2,k+2) = (1/k!)*Sum_{i = 0..k} (-1)^(k-i)*C(k,i)*(i+2)^n, n,k >= 0. T(n,k) = Stirling2(n,k) - Stirling2(n-1,k) for n, k >= 2.
%F Recurrence relation: T(n,k) = T(n-1,k-1) + k*T(n-1,k) for n > 2, with boundary conditions T(n,1) = T(1,n) = 0 for all n, T(2,2) = 1 and T(2,k) = 0 for k > 2. Special cases: T(n,2) = 2^(n-2); T(n,3) = 3^(n-2) - 2^(n-2).
%F As a sum of monomial functions of degree m: T(n+m,n) = Sum_{2 <= i_1 <= ... <= i_m <= n} (i_1*i_2*...*i_m). For example, T(6,4) = Sum_{2 <= i <= j <= 4} (i*j) = 2*2 + 2*3 + 2*4 + 3*3 + 3*4 + 4*4 = 55.
%F E.g.f. column k+2 (with offset 2): 1/k!*exp(2*x)*(exp(x) - 1)^k.
%F O.g.f. k-th column: Sum_{n = k..oo} T(n,k)*x^n = x^k/((1-2*x)*(1-3*x)*...*(1-k*x)).
%F E.g.f.: exp(2*t + x*(exp(t) - 1)) = Sum_{n = 0..oo} Sum_{k = 0..n} T(n+2,k+2) *x^k*t^n/n! = Sum_{n = 0..oo} B_n(2;x)*t^n/n! = 1 + (2 + x)*t/1! + (4 + 5*x + x^2)*t^2/2! + ..., where the row polynomial B_n(2;x) := Sum_{k = 0..n} T(n+2,k+2)*x^k denotes the 2-Bell polynomial.
%F Dobinski-type identities: Row polynomial B_n(2;x) = exp(-x)*Sum_{i = 0..oo} (i + 2)^n*x^i/i!. Sum_{k = 0..n} k!*T(n+2,k+2)*x^k = Sum_{i = 0..oo} (i + 2)^n*x^i/(1 + x)^(i+1).
%F The T(n,k) are the connection coefficients between falling factorials and the shifted monomials (x + 2)^(n-2). For example, from row 4 we have 4 + 5*x + x*(x - 1) = (x + 2)^2, while from row 5 we have 8 + 19*x + 9*x*(x - 1) + x*(x - 1)*(x - 2) = (x + 2)^3.
%F The row sums of the array are the 2-Bell numbers, B_n(2;1), equal to A005493(n-2). The alternating row sums are the complementary 2-Bell numbers, B_n(2;-1), equal to (-1)^n*A074051(n-2).
%F This array is the matrix product P * S, where P denotes the Pascal triangle, A007318 and S denotes the lower triangular array of Stirling numbers of the second kind, A008277 (apply Theorem 10 of [Neuwirth]).
%F Also, this array equals the transpose of the upper triangular array A126351. The inverse array is A049444, the signed 2-Stirling numbers of the first kind. See A143491 for the unsigned version of the inverse.
%F Let f(x) = exp(exp(x)). Then for n >= 1, the row polynomials R(n,x) are given by R(n+2,exp(x)) = 1/f(x)*(d/dx)^n(exp(2*x)*f(x)). Similar formulas hold for A008277, A039755, A105794, A111577 and A154537. - _Peter Bala_, Mar 01 2012
%e Triangle begins
%e n\k|...2....3....4....5....6....7
%e =================================
%e 2..|...1
%e 3..|...2....1
%e 4..|...4....5....1
%e 5..|...8...19....9....1
%e 6..|..16...65...55...14....1
%e 7..|..32..211..285..125...20....1
%e ...
%e T(4,3) = 5. The set {1,2,3,4} can be partitioned into three subsets such that 1 and 2 belong to different subsets in 5 ways: {{1}{2}{3,4}}, {{1}{3}{2,4}}, {{1}{4}{2,3}}, {{2}{3}{1,4}} and {{2}{4}{1,3}}; the remaining possibility {{1,2}{3}{4}} is not allowed.
%p with combinat: T := (n, k) -> (1/(k-2)!)*add ((-1)^(k-i)*binomial(k-2,i)*(i+2)^(n-2),i = 0..k-2): for n from 2 to 11 do seq(T(n, k), k = 2..n) end do;
%t t[n_, k_] := StirlingS2[n, k] - StirlingS2[n-1, k]; Flatten[ Table[ t[n, k], {n, 2, 11}, {k, 2, n}]] (* _Jean-François Alcover_, Dec 02 2011 *)
%o (Sage)
%o @CachedFunction
%o def stirling2r(n, k, r) :
%o if n < r: return 0
%o if n == r: return 1 if k == r else 0
%o return stirling2r(n-1,k-1,r) + k*stirling2r(n-1,k,r)
%o A143494 = lambda n,k: stirling2r(n, k, 2)
%o for n in (2..6):
%o [A143494(n, k) for k in (2..n)] # _Peter Luschny_, Nov 19 2012
%Y Cf. A001047 (column 3), A005493 (row sums), A008277, A016269 (column 4), A025211 (column 5), A049444 (matrix inverse), A074051 (alt. row sums), A143491, A143495, A143496, A143497.
%K easy,nonn,tabl
%O 2,2
%A _Peter Bala_, Aug 20 2008
|
