A211788 Triangle enumerating certain two-line arrays of positive integers.

1, 1, 1, 1, 4, 4, 1, 7, 21, 21, 1, 10, 47, 126, 126, 1, 13, 82, 324, 818, 818, 1, 16, 126, 642, 2300, 5594, 5594, 1, 19, 179, 1107, 4977, 16741, 39693, 39693, 1, 22, 241, 1746, 9335, 38642, 124383, 289510, 289510, 1, 25, 312, 2586, 15941, 77273, 301630, 939880, 2157150, 2157150

Offset: 1

Author

Peter Bala, Aug 02 2012

Keywords

• nonn
• easy
• tabl

Comments

This is the table of f(n,k) in the notation of Carlitz (p.123). The triangle enumerates two-line arrays of positive integers

............a_1 a_2 ... a_n..........

............b_1 b_2 ... b_n..........

such that

1) max(a_i, b_i) <= min(a_(i+1), b_(i+1)) for 1 <= i <= n-1

2) max(a_i, b_i) <= i for 1 <= i <= n

3) a_n = b_n = k.

See A071948 and A193091 for other two-line array enumerations.

It appears that the row reverse array is the Riordan array (f(x), g(x)), where f(x) = 1 + x + 4*x^2 + 21*x^3 + 126*x^4 + 818*x^5 + ... is the g.f. of A003168 and g(x) = x + 3*x^2 + 14*x^3 + 79*x^4 + 494*x^5 + 3294*x^6 + ... is the g.f. of A003169. - Peter Bala, Nov 26 2024

Examples

			Triangle begins
.n\k.|..1....2....3....4....5....6
= = = = = = = = = = = = = = = = = =
..1..|..1
..2..|..1....1
..3..|..1....4....4
..4..|..1....7...21...21
..5..|..1...10...47..126..126
..6..|..1...13...82..324..818..818
...
T(4,2) = 7: The 7 two-line arrays are
...1 1 1 2....1 1 2 2....1 2 2 2....1 1 1 2
...1 1 1 2....1 1 2 2....1 2 2 2....1 1 2 2
...........................................
...1 1 2 2....1 1 2 2....1 2 2 2...........
...1 1 1 2....1 2 2 2....1 1 2 2...........
		

Links

• L. Carlitz, Enumeration of two-line arrays, Fib. Quart., Vol. 11 Number 2 (1973), 113-130.

Crossrefs

Cf. A003168 (main diagonal), A211789 (row sums).

Cf. A003169, A071948, A193091.

Formula

Recurrence equation:

T(1,1) = 1; T(n,n) = T(n,n-1); T(n+1,k) = Sum_{j = 1..k} (2*k-2*j+1)*T(n,j) for 1 <= k <= n.

T(n+1,k+1) = (1/n) * ((n - k)*Sum_{i = 0..k} C(n, k-i)*C(2*n+i, i) + Sum_{i = 1..k} C(n, k-i)*C(2*n+i, i-1)).

Row reverse has production matrix

1 1

3 3 1

5 5 3 1

7 7 5 3 1

...

Main diagonal T(n,n) = A003168(n). Row sums A211789.