4,2

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

The unsigned 4-restricted Lah numbers are related to the 4-restricted Stirling numbers: the lower triangular array of unsigned 4-restricted Lah numbers may be expressed as the matrix product St1(4) * St2(4), where St1(4) = A143493 and St2(4) = A143496 are the arrays of 4-restricted Stirling numbers of the first and second kind respectively. An alternative factorization for the array is as St1 * P^6 * 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.

Neuwirth Erich, Recursively defined combinatorial functions: Extending Galton's board, Discrete Math. 239 No. 1-3, 33-51 (2001)

T(n,k) = (n-4)!/(k-4)!*binomial(n+3,k+3), n,k >= 4. Recurrence: T(n,k) = (n+k-1)*T(n-1,k) + T(n-1,k-1) for n,k >= 4, with the boundary conditions: T(n,k) = 0 if n < 4 or k < 4; T(4,4) = 1. E.g.f. for column k: sum {n >= k} T(n,k)*t^n/(n-4)! = 1/(k-4)!*t^k/(1-t)^(k+4) for k >= 4. E.g.f: sum {n = 4..inf} sum {k = 4..n} T(n,k)*x^k*t^n/(n-4)! = (x*t)^4/(1-t)^8*exp(x*t/(1-t)) = (x*t)^4*(1 + (8+x)t +(72+18x+x^2)t^2/2! + ... ). Generalized Lah identity: (x+7)*(x+8)*...*(x+n+2) = sum {k = 4..n} T(n,k)*(x-1)*(x-2)*...*(x-k+4). The polynomials 1/n!*sum {k = 4..n+4} T(n+4,k)*(-x)^(k-4) for n >= 0 are generalized Laguerre polynomials Laguerre(n,7,x). Array = A132493* A143496 = abs(A008275) * ( A007318 )^6 * A008277 (apply Theorem 10 of [Neuwirth]). Array equals exp(D), where D is the array with the quadratic sequence (8,18,30,44, ... ) on the main subdiagonal and zeros everywhere else.

Triangle begins

n\k|......4......5......6......7......8......9

==============================================

4..|......1

5..|......8......1

6..|.....72.....18......1

7..|....720....270.....30......1

8..|...7920...3960....660.....44......1

9..|..95040..59400..13200...1320.....60......1

...

T(5,4) = 8. The partitions of {1,2,3,4,5} into 4 ordered lists, such that the elements 1, 2, 3 and 4 lie in different lists, are: {1}{2}{3}{4,5} and {1}{2}{3}{5,4}, {1}{2}{4}{3,5} and {1}{2}{4}{5,3}, {1}{3}{4}{2,5} and {1}{3}{4}{5,2}, {2}{3}{4}{1,5} and {2}{3}{4}{5,1}.

with combinat: T := (n, k) -> (n-4)!/(k-4)!*binomial(n+3, k+3): for n from 4 to 13 do seq(T(n, k), k = 4..n) end do;

Cf. A007318, A008275, A008277, A049388 (column 4), A105278 (unsigned Lah numbers), A143493, A143496, A143497, A143498.

Sequence in context: A038279 A075503 A051379 this_sequence A114152 A048786 A132056

Adjacent sequences: A143496 A143497 A143498 this_sequence A143500 A143501 A143502

easy,nonn,tabl

Peter Bala (pbala(AT)toucansurf.com), Aug 25 2008