login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A143494
Triangle read by rows: 2-Stirling numbers of the second kind.
31
1, 2, 1, 4, 5, 1, 8, 19, 9, 1, 16, 65, 55, 14, 1, 32, 211, 285, 125, 20, 1, 64, 665, 1351, 910, 245, 27, 1, 128, 2059, 6069, 5901, 2380, 434, 35, 1, 256, 6305, 26335, 35574, 20181, 5418, 714, 44, 1, 512, 19171, 111645, 204205, 156660, 58107, 11130, 1110, 54, 1
OFFSET
2,2
COMMENTS
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.
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).
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.
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].
From Peter Bala, Sep 19 2008: (Start)
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.
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]).
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)
From Wolfdieter Lang, Sep 29 2011: (Start)
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)
LINKS
S. Alex Bradt, Jennifer Elder, Pamela E. Harris, Gordon Rojas Kirby, Eva Reutercrona, Yuxuan (Susan) Wang, and Juliet Whidden, Unit interval parking functions and the r-Fubini numbers, arXiv:2401.06937 [math.CO], 2024. See page 2.
Andrei Z. Broder, The r-Stirling numbers, Report Number: CS-TR-82-949, 1982, Stanford University, Department of Computer Science.
Andrei Z. Broder, The r-Stirling numbers, Discrete Math. 49, 241-259 (1984).
C. B. Corcino, L. C. Hsu, and E. L. Tan, Asymptotic approximations of r-Stirling numbers, Approximation Theory Appl. 15, No. 3 13-25 (1999).
A. Dzhumadildaev and D. Yeliussizov, Path decompositions of digraphs and their applications to Weyl algebra, 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]
Askar Dzhumadil’daev and Damir Yeliussizov, Walks, partitions, and normal ordering, Electronic Journal of Combinatorics, 22(4) (2015), #P4.10.
Eldar Fischer, Johann A. Makowsky, and Vsevolod Rakita, MC-finiteness of restricted set partition functions, arXiv:2302.08265 [math.CO], 2023.
Paweł Hitczenko, A class of polynomial recurrences resulting in (n/log n, n/log^2 n)-asymptotic normality, arXiv:2403.03422 [math.CO], 2024. See p. 8.
L. Liu and Y. Wang, A unified approach to polynomial sequences with only real zeros, arXiv:math/0509207 [math.CO], 2005-2006.
V. V. Mikhailov, Ordering of some boson operator functions, J. Phys A: Math. Gen. 16 (1983) 3817-3827.
V. V. Mikhailov, Normal ordering and generalised Stirling numbers, J. Phys A: Math. Gen. 18 (1985) 231-235.
Erich Neuwirth, Recursively defined combinatorial functions: Extending Galton's board, Technical Report TR 99-05, July 1999, Universität Wien.
Erich Neuwirth, Recursively defined combinatorial functions: Extending Galton's board, Discrete Math. 239 No. 1-3, 33-51 (2001).
M. d’Ocagne, Sur une classe de nombres remarquables, Amer. J. Math., Vol. 9 (1887), 353-380.
Michael J. Schlosser and Meesue Yoo, Elliptic Rook and File Numbers, Electronic Journal of Combinatorics, 24(1) (2017), #P1.31.
Mark Shattuck, Generalized r-Lah numbers, arXiv:1412.8721 [math.CO], 2014.
FORMULA
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.
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).
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.
E.g.f. column k+2 (with offset 2): 1/k!*exp(2*x)*(exp(x) - 1)^k.
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)).
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.
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).
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.
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).
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]).
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.
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
EXAMPLE
Triangle begins
n\k|...2....3....4....5....6....7
=================================
2..|...1
3..|...2....1
4..|...4....5....1
5..|...8...19....9....1
6..|..16...65...55...14....1
7..|..32..211..285..125...20....1
...
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.
MAPLE
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;
MATHEMATICA
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 *)
PROG
(Sage)
@CachedFunction
def stirling2r(n, k, r) :
if n < r: return 0
if n == r: return 1 if k == r else 0
return stirling2r(n-1, k-1, r) + k*stirling2r(n-1, k, r)
A143494 = lambda n, k: stirling2r(n, k, 2)
for n in (2..6):
[A143494(n, k) for k in (2..n)] # Peter Luschny, Nov 19 2012
CROSSREFS
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.
Sequence in context: A176667 A126182 A154342 * A124960 A137346 A264017
KEYWORD
easy,nonn,tabl
AUTHOR
Peter Bala, Aug 20 2008
STATUS
approved