A143495 Triangle read by rows: 3-Stirling numbers of the second kind.

1, 3, 1, 9, 7, 1, 27, 37, 12, 1, 81, 175, 97, 18, 1, 243, 781, 660, 205, 25, 1, 729, 3367, 4081, 1890, 380, 33, 1, 2187, 14197, 23772, 15421, 4550, 644, 42, 1, 6561, 58975, 133057, 116298, 47271, 9702, 1022, 52, 1, 19683, 242461, 724260, 830845, 447195

Offset: 3

Author

Peter Bala, Aug 20 2008

Keywords

• nonn
• easy
• tabl

Comments

This is the case r = 3 of the r-Stirling numbers of the second kind. The 3-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, 2 and 3 belong to distinct subsets. For remarks on the general case see A143494 (r = 2). The corresponding array of 3-Stirling numbers of the first kind is A143492. The theory of r-Stirling numbers of both kinds is developed in [Broder]. For 3-Lah numbers refer to A143498.

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^(-3)*E^n*x^3 = Sum_{k = 0..n} T(n+3,k+3)*x^k*D^k.

The row generating polynomials R_n(x) := Sum_{k= 3..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_3(x) = x^3. It follows that the polynomials R_n(x) have only real zeros (apply Corollary 1.2. of [Liu and Wang]).

Relation with the 3-Eulerian numbers E_3(n,j) := A144697(n,j): T(n,k) = (3!/k!)*Sum_{j = n-k..n-3} E_3(n,j)*binomial(j,n-k) for n >= k >= 3.

(End)

T(n,k) = S(n,k,3), n>=k>=3, in Mikhailov's first paper, eq.(28) or (A3). E.g.f. column k from (A20) with k->3, r->k. Therefore, with offset [0,0], this triangle is the Sheffer triangle (exp(3*x),exp(x)-1) with e.g.f. of column no. m>=0: exp(3*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. - Wolfdieter Lang, Sep 29 2011

Examples

			Triangle begins
  n\k|....3....4....5....6....7....8
  ==================================
  3..|....1
  4..|....3....1
  5..|....9....7....1
  6..|...27...37...12....1
  7..|...81..175...97...18....1
  8..|..243..781..660..205...25....1
  ...
T(5,4) = 7. The set {1,2,3,4,5} can be partitioned into four subsets such that 1, 2 and 3 belong to different subsets in 7 ways: {{1}{2}{3}{4,5}}, {{1}{2}{5}{3,4}}, {{1}{2}{4}{3,5}}, {{1}{3}{4}{2,5}}, {{1}{3}{5}{2,4}}, {{2}{3}{4}{1,5}} and {{2}{3}{5}{1,4}}.
From _Peter Bala_, Feb 23 2025: (Start)
The array factorizes as
/ 1               \       /1             \ /1             \ /1            \
| 3    1           |     | 3   1          ||0  1           ||0  1          |
| 9    7   1       |  =  | 9   4   1      ||0  3   1       ||0  0  1       | ...
|27   37  12   1   |     |27  13   5  1   ||0  9   4  1    ||0  0  3  1    |
|81  175  97  18  1|     |81  40  18  6  1||0 27  13  5  1 ||0  0  9  4  1 |
|...               |     |...             ||...            ||...           |
where, in the infinite product on the right-hand side, the first array is the Riordan array (1/(1 - 3*x), x/(1 - x)). See A106516. (End)
		

Links

• Peter Bala, Factorising (r,b)-Stirling arrays
• Andrei Z. Broder, The r-Stirling numbers, Report Number: CS-TR-82-949, Stanford University, Department of Computer Science; see also, Discrete Math. 49, 241-259 (1984).
• A. Dzhumadildaev and D. Yeliussizov, Path decompositions of digraphs and their applications to Weyl algebra, 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]
• Askar Dzhumadil’daev and Damir Yeliussizov, Walks, partitions, and normal ordering, Electronic Journal of Combinatorics, 22(4) (2015), #P4.10.
• 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, Discrete Math. 239 No. 1-3, 33-51 (2001).
• L. Liu and Y. Wang, A unified approach to polynomial sequences with only real zeros, arXiv:math/0509207 [math.CO], 2005-2006.
• Michael J. Schlosser and Meesue Yoo, Elliptic Rook and File Numbers, Electronic Journal of Combinatorics, 24(1) (2017), #P1.31.

Crossrefs

Cf. A005061 (column 4), A005494 (row sums), A008277, A016753 (column 5), A028025 (column 6), A049458 (matrix inverse), A106516, A143492, A143494, A143496, A143498.

Programs

Maple

A143495 := (n, k) -> (1/(k-3)!)*add((-1)^(k-i-1)*binomial(k-3,i)*(i+3)^(n-3), i = 0..k-3): for n from 3 to 12 do seq(A143495(n, k), k = 3..n) end do;

Mathematica

nmax = 12; t[n_, k_] := 1/(k-3)!* Sum[ (-1)^(k-j-1)*Binomial[k-3, j]*(j+3)^(n-3), {j, 0, k-3}]; Flatten[ Table[ t[n, k], {n, 3, nmax}, {k, 3, n}]] (* Jean-François Alcover, Dec 07 2011, after Maple *)

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)
A143495 = lambda n, k: stirling2r(n, k, 3)
for n in (3..8): [A143495(n, k) for k in (3..n)] # Peter Luschny, Nov 19 2012

Formula

T(n+3,k+3) = (1/k!)*Sum_{i = 0..k} (-1)^(k-i)*binomial(k,i)*(i+3)^n, n,k >= 0.

T(n,k) = Stirling2(n,k) - 3*Stirling2(n-1,k) + 2*Stirling2(n-2,k), n,k >= 3.

Recurrence relation: T(n,k) = T(n-1,k-1) + k*T(n-1,k) for n > 3, with boundary conditions: T(n,2) = T(2,n) = 0 for all n; T(3,3) = 1; T(3,k) = 0 for k > 3.

Special cases: T(n,3) = 3^(n-3); T(n,4) = 4^(n-3) - 3^(n-3).

E.g.f. (k+3) column (with offset 3): (1/k!)*exp(3x)*(exp(x)-1)^k.

O.g.f. k-th column: Sum_{n >= k} T(n,k)*x^n = x^k/((1-3*x)*(1-4*x)*...*(1-k*x)).

E.g.f.: exp(3*t + x*(exp(t)-1)) = Sum_{n >= 0} Sum_{k = 0..n} T(n+3,k+3)*x^k*t^n/n! = Sum_{n >= 0} B_n(3;x)*t^n/n! = 1 + (3+x)*t/1! + (9+7*x+x^2)*t^2/2! + ..., where the row polynomials, B_n(3;x) := Sum_{k = 0..n} T(n+3,k+3)*x^k, may be called the 3-Bell polynomials.

Dobinski-type identities: Row polynomial B_n(3;x) = exp(-x)*Sum_{i >= 0} (i+3)^n*x^i/i!; Sum_{k = 0..n} k!*T(n+3,k+3)*x^k = Sum_{i >= 0} (i+3)^n*x^i/(1+x)^(i+1).

The T(n,k) are the connection coefficients between the falling factorials and the shifted monomials (x+3)^(n-3). For example, 9 + 7*x + x*(x-1) = (x+3)^2 and 27 + 37*x + 12x*(x-1) + x*(x-1)*(x-2) = (x+3)^3.

This array is the matrix product P^2 * 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]). The inverse array is A049458, the signed 3-Stirling numbers of the first kind.