cp's OEIS Frontend

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.

From Wolfdieter Lang, Sep 29 2011: (Start)

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.

(End)

For a signed version of this triangle see A062137. The unsigned 2-Lah number L(2; n,k) gives the number of partitions of the set {1, 2, ..., n} into k ordered lists with the restriction that the elements 1 and 2 must belong to different lists. More generally, the unsigned r-Lah number L(r; n, k) gives the number of partitions of the set {1, 2, ..., n} into k ordered lists with the restriction that the elements 1, 2, ..., r belong to different lists. If r = 1 there is no restriction and we obtain the unsigned Lah numbers A105278. For other cases see A143498 (r=3) and A143499 (r=4). We make some remarks on the general case.

The unsigned r-Lah numbers occur as connection constants in the generalized Lah identity (x + 2*r - 1)*(x + 2*r)*...*(x + 2*r + n - r - 2) = Sum_{k=r..n} L(r; n, k)*(x - 1)*(x - 2)*...*(x - k + r) for n >= r and where any empty products are taken equal to 1 (for a bijective proof of the identity, follow the proof of [Petkovsek and Pisanski] but restrict the first r of the Argonauts to different paths).

The unsigned r-Lah numbers satisfy the same recurrence as the unsigned Lah numbers, namely, L(r; n, k) = (n + k - 1)*L(r; n - 1,k) + L(r; n - 1,k - 1), but with the boundary conditions: L(r; n, k) = 0 if n < r or if k < r; L(r; r, r) = 1. The recurrence has the explicit solution L(r; n, k) = ((n - r)!/(k - r)!)*binomial(n + r - 1, k + r - 1) for n, k >= r. It follows that the unsigned r-Lah numbers have 'vertical' generating functions for k >= r of the form Sum_{n>=k} L(r; n, k)*t^n/(n -r)! = 1/(k - r)!*t^k/(1 - t)^(k + r). This yields the e.g.f. for the array of unsigned r-restricted Lah numbers in the form: Sum_{n,k>=r} L(r; n, k)*x^k*t^n/(n-r)! = (x*t)^r * 1/(1 - t)^(2*r) * exp(x*t/(1 - t)) = (x*t)^r (1 + (2*r + x)*t + (2r*(2*r + 1) + 2*(2*r + 1)*x + x^2)*t^2/2! + ...).

The array of unsigned r-Lah numbers begins

1

2r 1

2r*(2r+1) 2*(2r+1) 1

2r*(2r+1)*(2r+2) 3*(2r+1)*(2r+2) 3*(2r+2) 1

...

and equals exp(D(r)), where D(r) is the array with the sequence (2*r, 2*(2*r + 1), 3*(2*r + 2), 4*(2*r + 3), ...) on the main subdiagonal and zeros everywhere else.

The unsigned r-Lah numbers are related to the r-Stirling numbers: the lower triangular array of unsigned r-Lah numbers may be expressed as the matrix product St1(r) * St2(r), where St1(r) and St2(r) denote the arrays of r-Stirling numbers of the first and second kind respectively. The theory of r-Stirling numbers is developed in [Broder]. See A143491 - A143496 for tables of r-Stirling numbers. An alternative factorization for the array is as St1 * P^(2r - 2) * St2, where P denotes Pascal's triangle, A007318, St1 is the triangle of unsigned Stirling numbers of the first kind, abs(A008275) and St2 denotes the triangle of Stirling numbers of the second kind, A008277 (apply Theorem 10 of [Neuwirth]).

The array of unsigned r-Lah numbers is an example of the fundamental matrices sketched in A133314. So redefining the offset as n=0, given matrices A and B with A(n, k) = T(n, k)*a(n - k) and B(n, k) = T(n, k)*b(n - k), then A*B = C where C(n, k) = T(n,k)*[a(.) + b(.)]^(n - k), umbrally. An e.g.f. for the row polynomials of A is exp(x*t) exp{-x*t*[a*t/(a*t - 1)]}/(1 - a*t)^4 = exp(x*t) exp[(.)!*Laguerre(., 3, -x*t)* a(.)*t)], umbrally. - Tom Copeland, Sep 19 2008

For a signed version of this triangle see A062138. This is the case r = 3 of the unsigned r-Lah numbers L(r;n,k). The unsigned 3-Lah numbers count the partitions of the set {1,2,...,n} into k ordered lists with the restriction that the elements 1, 2 and 3 belong to different lists. For other cases see A105278 (r = 1), A143497 (r = 2 and comments on the general case) and A143499 (r = 4).

The unsigned 3-Lah numbers are related to the 3-Stirling numbers: the lower triangular array of unsigned 3-Lah numbers may be expressed as the matrix product St1(3) * St2(3), where St1(3) = A143492 and St2(3) = A143495 are the arrays of 3-Stirling numbers of the first and second kind respectively. An alternative factorization for the array is as St1 * P^4 * St2, where P denotes Pascal's triangle, A007318, St1 is the triangle of unsigned Stirling numbers of the first kind, abs(A008275) and St2 denotes the triangle of Stirling numbers of the second kind, A008277.

See A049459 for a signed version of the array. The unsigned 4-Stirling numbers of the first kind count the permutations of the set {1,2,...,n} into k disjoint cycles, with the restriction that the elements 1, 2, 3 and 4 belong to distinct cycles. This is the case r = 4 of the unsigned r-Stirling numbers of the first kind. For other cases see abs(A008275) (r = 1), A143491 (r = 2) and A143492 (r = 3). See A143496 for the corresponding triangle of 4-Stirling numbers of the second kind.

The theory of r-Stirling numbers of both kinds is developed in [Broder]. For details of the related 4-Lah numbers see A143499.

With offset n=0 and k=0, this is the Sheffer triangle (1/(1-x)^4,-log(1-x)) (in the umbral notation of S. Roman's book this would be called Sheffer for (exp(-4*t),1-exp(-t))). See the e.g.f given below. Compare also with the e.g.f. for the signed version A049459. - Wolfdieter Lang, Oct 10 2011

With offset n=0 and k=0: triangle T(n,k), read by rows, given by (4,1,5,2,6,3,7,4,8,5,9,6,...) DELTA (1,0,1,0,1,0,1,0,1,0,1,0,...) where DELTA is the operator defined in A084938. - Philippe Deléham, Oct 31 2011

This is the case r = 4 of the r-Eulerian numbers, denoted by A(r;n,k), defined as follows. Let [n] denote the ordered set {1,2,...,n} and let r be a nonnegative integer. Let Permute(n,n-r) denote the set of injective maps p:[n-r] -> [n], which we think of as permutations of n numbers taken n-r at a time. Clearly, |Permute(n,n-r)| = n!/r!. We say that the permutation p has an excedance at position i, 1 <= i <= n-r, if p(i) > i. Then the r-Eulerian number A(r;n,k) is defined as the number of permutations in Permute(n,n-r) with k excedances. Thus the 4-Eulerian numbers are the number of permutations in Permute(n,n-4) with k excedances. For other cases see A008292 (r = 0 and r = 1), A144696 (r = 2), A144697 (r = 3) and A144699 (r = 5).

An alternative interpretation of the current array due to [Strosser] involves the 4-excedance statistic of a permutation (see also [Foata & Schutzenberger, Chapter 4, Section 3]). We define a permutation p in Permute(n,n-4) to have a 4-excedance at position i (1 <= i <= n-4) if p(i) >= i + 4.

Given a permutation p in Permute(n,n-4), define ~p to be the permutation in Permute(n,n-4) that takes i to n+1 - p(n-i-3). The map ~ is a bijection of Permute(n,n-4) with the property that if p has (resp. does not have) an excedance in position i then ~p does not have (resp. has) a 4-excedance at position n-i-3. Hence ~ gives a bijection between the set of permutations with k excedances and the set of permutations with (n-k) 4-excedances. Thus reading the rows of this array in reverse order gives a triangle whose entries are the number of permutations in Permute(n,n-4) with k 4-excedances.

Example: Represent a permutation p:[n-4] -> [n] in Permute(n,n-4) by its image vector (p(1),...,p(n-4)). In Permute(10,6) the permutation p = (1,2,4,10,3,6) does not have an excedance in the first two positions (i = 1 and 2) or in the final two positions (i = 5 and 6). The permutation ~p = (5,8,1,7,9,10) has 4-excedances only in the first two positions and the final two positions.