

A143497


Triangle of unsigned 2Lah numbers.


7



1, 4, 1, 20, 10, 1, 120, 90, 18, 1, 840, 840, 252, 28, 1, 6720, 8400, 3360, 560, 40, 1, 60480, 90720, 45360, 10080, 1080, 54, 1, 604800, 1058400, 635040, 176400, 25200, 1890, 70, 1, 6652800, 13305600, 9313920, 3104640, 554400, 55440, 3080, 88, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

2,2


COMMENTS

For a signed version of this triangle see A062137. The unsigned 2Lah 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 rLah 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 rLah numbers occur as connection constants in the generalized Lah identity (x+2r1)*(x+2r)*...*(x+2r+nr2) = Sum_{k = r..n} L(r;n,k)*(x1)*(x2)*...*(xk+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 rLah numbers satisfy the same recurrence as the unsigned Lah numbers, namely, L(r;n,k) = (n+k1)*L(r;n1,k) + L(r;n1,k1), 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) = (nr)!/(kr)!*binomial(n+r1,k+r1) for n,k >= r. It follows that the unsigned rLah numbers have 'vertical' generating functions for k >= r of the form Sum_{n >= k} L(r;n,k)*t^n/(nr)! = 1/(kr)!*t^k/(1t)^(k+r). This yields the e.g.f. for the array of unsigned rrestricted Lah numbers in the form: Sum_{n,k >= r} L(r;n,k)*x^k*t^n/(nr)! = (x*t)^r * 1/(1t)^(2*r) * exp(x*t/(1t)) = (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 rLah numbers begins
1...................0..................0.............0...
2r..................1..................0.............0...
2r*(2r+1)...........2*(2r+1)...........1.............0...
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 rLah numbers are related to the rStirling numbers: the lower triangular array of unsigned rLah numbers may be expressed as the matrix product St1(r) * St2(r), where St1(r) and St2(r) denote the arrays of rStirling numbers of the first and second kind respectively. The theory of rStirling numbers is developed in [Broder]. See A143491  A143496 for tables of rStirling numbers. An alternative factorization for the array is as St1 * P^(2r2) * 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 rLah 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(nk) and B(n,k) = T(n,k)*b(nk), then A*B = C where C(n,k) = T(n,k)*[a(.)+b(.)]^(nk), umbrally. An e.g.f. for the row polynomials of A is exp(x*t) exp{x*t*[a*t/(a*t1)]}/(1a*t)^4 = exp(x*t) exp[(.)!*Laguerre(.,3,x*t)*a(.)*t)], umbrally. [From Tom Copeland, Sep 19 2008]


LINKS

A. Z. Broder, The rStirling numbers, Report CSTR82949, Stanford University, Department of Computer Science, 1982.


FORMULA

T(n,k) = (n2)!/(k2)!*C(n+1,k+1), n,k >= 2.
Recurrence: T(n,k) = (n+k1)*T(n1,k) + T(n1,k1) for n,k >= 2, with the boundary conditions: T(n,k) = 0 if n < 2 or k < 2; T(2,2) = 1.
E.g.f. for column k: Sum_{n >= k} T(n,k)*t^n/(n2)! = 1/(k2)!*t^k/(1t)^(k+2) for k >= 2.
E.g.f: Sum_{n = 2..inf} Sum_{k = 2..n} T(n,k)*x^k*t^n/(n2)! = (x*t)^2/(1t)^4*exp(x*t/(1t)) = (x*t)^2*(1 + (4+x)*t +(20+10*x+x^2)*t^2/2! + ... ).
Generalized Lah identity: (x+3)*(x+4)*...*(x+n) = Sum_{k = 2..n} T(n,k)*(x1)*(x2)*...*(xk+2).
The polynomials 1/n!*Sum_{k = 2..n+2} T(n+2,k)*(x)^(k2) for n >= 0 are the generalized Laguerre polynomials Laguerre(n,3,x). See A062137.
Array = A143491 * A143494 = abs(A008275) * ( A007318 )^2 * A008277 (apply Theorem 10 of [Neuwirth]). Array equals exp(D), where D is the array with the quadratic sequence (4,10,18,28, ... ) on the main subdiagonal and zeros elsewhere.
After adding 1 to the head of the main diagonal and a zero to each of the subdiagonals, the nth diagonal may be generated as coefficients of (1/n!) [D^(1) tDt t^(3)D t^3]^n exp(x t), where D is the derivative w.r.t. t and D^(1) t^j/j! = t^(j+1)/(j+1)!. E.g., n=2 generates 20 x t^3/3! + 90 x^2 t^4/4! + 252 x^3 t^5/5! + ... . For the general unsigned rLah number array, replace the threes by (2r1) in the operator. The e.g.f. of the row polynomials is then exp[D^(1) tDt t^((2r1))D t^(2r1)] exp(x t), with offset n=0. [From Tom Copeland, Sep 21 2008]


EXAMPLE

Triangle begins
n\k.....2.....3.....4.....5.....6.....7
========================================
2.......1
3.......4.....1
4......20....10.....1
5.....120....90....18.....1
6.....840...840...252....28.....1
7....6720..8400..3360...560....40.....1
...
T(4,3) = 10. The ten partitions of {1,2,3,4} into 3 ordered lists such that the elements 1 and 2 lie in different lists are: {1}{2}{3,4} and {1}{2}{4,3}, {1}{3}{2,4} and {1}{3}{4,2}, {1}{4}{2,3} and {1}{4}{3,2}, {2}{3}{1,4} and {2}{3}{4,1}, {2}{4}{1,3} and {2}{4}{3,1}. The remaining two partitions {3}{4}{1,2} and {3}{4}{2,1} are not allowed because the elements 1 and 2 belong to the same block.


MAPLE

with combinat: T := (n, k) > (n2)!/(k2)!*binomial(n+1, k+1): for n from 2 to 11 do seq(T(n, k), k = 2..n) end do;


MATHEMATICA

T[n_, k_] := (n2)!/(k2)!*Binomial[n+1, k+1]; Table[T[n, k], {n, 2, 10}, {k, 2, n}] // Flatten (* Amiram Eldar, Nov 27 2018 *)


PROG

(GAP) T:=Flat(List([2..10], n>List([2..n], k>(Factorial(n2)/Factorial(k2))*Binomial(n+1, k+1)))); # Muniru A Asiru, Nov 27 2018


CROSSREFS

Cf. A001715 (column 2), A007318, A008275, A008277, A061206 (column 3), A062137, A062141  A062144 ( column 4 to column 7), A062146 (alt. row sums), A062147 (row sums), A105278 (unsigned Lah numbers), A143491, A143494, A143498, A143499.


KEYWORD



AUTHOR



STATUS

approved



