A193091 Augmentation of the triangular array A158405. See Comments.

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, 1, 21, 219, 1505, 7589, 29307, 85741, 165127, 1, 24, 287, 2274, 13355, 61332, 224357, 638250, 1217270, 1, 27, 364, 3262, 21789, 115003

Offset: 0

Author

Clark Kimberling, Jul 30 2011

Keywords

• nonn
• tabl
• easy

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.

A002260=((k+1)) augments to A023531.

A154325 augments to A033878.

A158405 augments to A193091.

((k!)) augments to A193092.

A094727 augments to A193093.

A130296 augments to A193094.

A004736 augments to A193561.

...

Regarding the specific augmentation W=A193091: w(n,n)=A003169.

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.

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

(End)

Examples

			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
		

Links

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

Crossrefs

Cf. A003169, A193092, A193093, A193094.

Cf. A071948, A211788.

Programs

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}]]

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)