login
A211788
Triangle enumerating certain two-line arrays of positive integers.
3
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,5
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.
LINKS
L. Carlitz, Enumeration of two-line arrays, Fib. Quart., Vol. 11 Number 2 (1973), 113-130.
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.
EXAMPLE
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...........
CROSSREFS
A003168 (main diagonal), A071948, A193091, A211789 (row sums).
Sequence in context: A047213 A128213 A171716 * A318732 A016706 A358204
KEYWORD
nonn,easy,tabl
AUTHOR
Peter Bala, Aug 02 2012
STATUS
approved