A371081 Triangle read by rows, (2, 2)-Lah numbers.

1, 16, 1, 400, 52, 1, 14400, 2948, 116, 1, 705600, 203072, 12344, 216, 1, 45158400, 17154432, 1437472, 38480, 360, 1, 3657830400, 1760601600, 191088544, 6978592, 99320, 556, 1, 365783040000, 216690624000, 29277351936, 1370470592, 26445312, 224420, 812, 1

Offset

2,2

Comments

The (2, 2)-Lah numbers T(n, k) count ordered 2-tuples (pi(1), pi(2)) of partitions of the set {1, ..., n} into k linearly ordered blocks (lists, for short) such that the numbers 1, 2 are in distinct lists, and bl(pi(1)) = bl(pi(2)) where for i = {1, 2} and pi(i) = b(1)^i, b(2)^i, ..., b(k)^i, where b(1)^i, b(2)^i, ..., b(k)^i are the blocks of partition pi(i), bl(pi(i)) = {min(b(1))^i, min(b(2))^i, ..., min(b(k))^i} is the set of block leaders, i.e., of minima of the lists in partition pi(i).

The (2, 2)-Lah numbers T(n, k) are the (m, r)-Lah numbers for m=r=2. More generally, the (m, r)-Lah numbers count ordered m-tuples (pi(1), pi(2), ..., pi(m)) of partitions of the set {1, 2, ..., n} into k linearly ordered blocks (lists, for short) such that the numbers 1, 2, ..., r are in distinct lists, and bl(pi(1)) = bl(pi(2)) = ... = bl(pi(m)) where for i = {1, 2, ..., m} and pi(i) = {b(1)^i, b(2)^i, ..., b(k)^i}, where b(1)^i, b(2)^i,..., b(k)^i are the blocks of partition pi(i), bl(pi(i)) = {min(b(1))^i, min(b(2))^i, ..., min (b(k))^i} is the set of block leaders, i.e., of minima of the lists in partition pi(i).

Links

Table of n, a(n) for n=2..37.

A. Žigon Tankosič, The (l, r)-Lah Numbers, Journal of Integer Sequences, Article 23.2.6, vol. 26 (2023).

Formula

Recurrence relation: T(n, k) = T(n-1, k-1) + (n+k-1)^2*T(n-1, k).

Explicit formula: T(n, k) = Sum_{3 <= j(1) < j(2) < ... < j(n-k) <= n} (2j(1)-2)^2 * (2j(2)-3)^2 * ... * (2j(n-k)-(n-k+1))^2.

Special cases:

T(n, k) = 0 for n < k or k < 2,

T(n, n) = 1,

T(n, 2) = (A143497(n,2))^2 = A001715(n+1)^2 = ((n+1)!)^2/36,

T(n, n-1) = 2^2 * Sum_{j=2..n-1} j^2.

Example

Triangle begins:
         1;
        16,          1;
       400,         52,         1;
     14400,       2984,       116,       1;
    705600,     203072,     12344,     216,     1;
  45158400,    1715443,   1437472,   38480,   360,    1;
3657830400, 1760601600, 191088544,  6978592, 99320, 556, 1.
  ...
An example for T(4, 3). The corresponding partitions are
pi(1) = {(1),(2),(3,4)},
pi(2) = {(1),(2),(4,3)},
pi(3) = {(1),(2,3),(4)},
pi(4) = {(1),(3,2),(4)},
pi(5) = {(1),(2,4),(3)},
pi(6) = {(1),(4,2),(3)},
pi(7) = {(1,3),(2),(4)},
pi(8) = {(3,1),(2),(4)},
pi(9) = {(1,4),(2),(3)},
pi(10) = {(4,1),(2),(3)}, since A143497 for n=4, k=3 equals 10. Sets of their block leaders are bl(pi(1)) = bl(pi(2)) = bl(pi(5)) = bl(pi(6)) = bl(pi(9)) = bl(pi(10)) = {1,2,3} and
 bl(pi(3)) = bl(pi(4)) = bl(pi(7)) = bl(pi(8)) = {1,2,4}.
Compute the number of ordered 2-tuples (i.e., ordered pairs) of partitions pi(1), pi(2), ..., pi(10) such that partitions in the same pair share the same set of block leaders. As there are six partitions with the set of block leaders equal to {1,2,3}, and four partitions with the set of block leaders equal to {1,2,4}, T(4, 3) = 6^2 + 4^2 = 52.

Maple

T:= proc(n, k) option remember; `if`(k<2 or k>n, 0,
      `if`(n=k, 1, T(n-1, k-1)+(n+k-1)^2*T(n-1, k)))
    end:
seq(seq(T(n, k), k=2..n), n=2..10);  # Alois P. Heinz, Mar 11 2024

Prog

(Python)
def T_Lah(n, k):
    if k < 2 or k > n:
        return 0
    elif n == k == 2:
        return 1
    else:
        return T_Lah(n-1, k-1) + ((n+k-1)**2) * T_Lah(n-1, k)
def print_triangle(rows):
    for n in range(rows):
        row_values = [T_Lah(n, k) for k in range(n+1)]
        print(' '.join(map(str, row_values)).center(rows*10))
rows = 10
print_triangle(rows)

Crossrefs

Column k=2 gives A001715(n+1)^2.

Cf. A143497.

Sequence in context: A105671 A145828 A369913 * A223518 A095876 A360062

Adjacent sequences: A371078 A371079 A371080 * A371082 A371083 A371084

Keyword

nonn,tabl

Author

Aleks Zigon Tankosic, Mar 10 2024

Status

approved