OFFSET
0,3
COMMENTS
Suppose that P is an infinite triangular array of numbers:
p(0,0)
p(1,0)...p(1,1)
p(2,0)...p(2,1)...p(2,2)
p(3,0)...p(3,1)...p(3,2)...p(3,3)...
...
Let w(0,0)=1, w(1,0)=p(1,0), w(1,1)=p(1,1), and define
W(n)=(w(n,0), w(n,1), w(n,2),...w(n,n-1), w(n,n)) recursively by W(n)=W(n-1)*PP(n), where PP(n) is the n X (n+1) matrix given by
...
row 0 ... p(n,0) ... p(n,1) ...... p(n,n-1) ... p(n,n)
row 1 ... 0 ..... p(n-1,0) ..... p(n-1,n-2) .. p(n-1,n-1)
row 2 ... 0 ..... 0 ............ p(n-2,n-3) .. p(n-2,n-2)
...
row n-1 . 0 ..... 0 ............. p(2,1) ..... p(2,2)
row n ... 0 ..... 0 ............. p(1,0) ..... p(1,1)
...
The augmentation of P is here introduced as the triangular array whose n-th row is W(n), for n>=0. The array P may be represented as a sequence of polynomials; viz., row n is then the vector of coefficients: p(n,0), p(n,1),...,p(n,n), from p(n,0)*x^n+p(n,1)*x^(n-1)+...+p(n,n). For example, (C(n,k)) is represented by ((x+1)^n); using this choice of P (that is, Pascal's triangle), the augmentation of P is calculated one row at a time, either by the above matrix products or by polynomial substitutions in the following manner:
...
row 0 of W: 1, by decree
row 1 of W: 1 augments to 1,1
...polynomial version: 1 -> x+1
row 2 of W: 1,1 augments to 1,3,2
...polynomial version: x+1 -> (x^2+2x+1)+(x+1)=x^2+3x+2
row 3 to W: 1,3,2 augments to 1,6,11,6
...polynomial version:
x^2+3x+2 -> (x+1)^3+3(x+1)^2+2(x+1)=(x+1)(x+2)(x+3)
...
Examples of augmented triangular arrays:
(p(n,k)=1) augments to A009766, Catalan triangle.
Catalan triangle augments to A193560.
Pascal triangle augments to A094638, Stirling triangle.
((k!)) augments to A193092.
...
From Peter Bala, Aug 02 2012: (Start)
This is the table of g(n,k) in the notation of Carlitz (p. 124). 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) max(a_n, b_n) = k.
(End)
LINKS
L. Carlitz, Enumeration of two-line arrays, Fib. Quart., Vol. 11 Number 2 (1973), 113-130.
FORMULA
From Peter Bala, Aug 02 2012: (Start)
T(n,k) = (n-k+1)/n*Sum_{i=0..k} C(n+1,n-k+i+1)*C(2*n+i+1,i) for 0 <= k <= n.
Recurrence equation: T(n,k) = Sum_{i=0..k} (2*k-2*i+1)*T(n-1,i).
(End)
EXAMPLE
The triangle P, at A158405, is given by rows
1
1...3
1...3...5
1...3...5...7
1...3...5...7...9...
The augmentation of P is the array W starts with w(0,0)=1, by definition of W. Successive polynomials (rows of W) arise from P as shown here:
...
1->x+3, so that W has (row 1)=(1,3);
...
x+3->(x^2+3x+5)+3*(x+3), so that W has (row 2)=(1,6,14);
...
x^2+6x+14->(x^3+3x^2+5x+7)+6(x^2+3x+5)+14(x+3), so that (row 3)=(1,9,37,79).
...
First 7 rows of W:
1
1 3
1 6 14
1 9 37 79
1 12 69 242 494
1 15 110 516 1658 3294
1 18 160 928 3870 11764 22952
MATHEMATICA
p[n_, k_] := 2 k + 1
Table[p[n, k], {n, 0, 5}, {k, 0, n}] (* A158405 *)
m[n_] := Table[If[i <= j, p[n + 1 - i, j - i], 0], {i, n}, {j, n + 1}]
TableForm[m[4]]
w[0, 0] = 1; w[1, 0] = p[1, 0]; w[1, 1] = p[1, 1];
v[0] = w[0, 0]; v[1] = {w[1, 0], w[1, 1]};
v[n_] := v[n - 1].m[n]
TableForm[Table[v[n], {n, 0, 6}]] (* A193091 *)
Flatten[Table[v[n], {n, 0, 9}]]
KEYWORD
AUTHOR
Clark Kimberling, Jul 30 2011
STATUS
approved