A193091 - OEIS

%I #20 Dec 16 2016 03:05:57

%S 1,1,3,1,6,14,1,9,37,79,1,12,69,242,494,1,15,110,516,1658,3294,1,18,

%T 160,928,3870,11764,22952,1,21,219,1505,7589,29307,85741,165127,1,24,

%U 287,2274,13355,61332,224357,638250,1217270,1,27,364,3262,21789,115003

%N Augmentation of the triangular array A158405. See Comments.

%C Suppose that P is an infinite triangular array of numbers:

%C p(0,0)

%C p(1,0)...p(1,1)

%C p(2,0)...p(2,1)...p(2,2)

%C p(3,0)...p(3,1)...p(3,2)...p(3,3)...

%C ...

%C Let w(0,0)=1, w(1,0)=p(1,0), w(1,1)=p(1,1), and define

%C     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

%C ...

%C row 0 ... p(n,0) ... p(n,1) ...... p(n,n-1) ... p(n,n)

%C row 1 ... 0 ..... p(n-1,0) ..... p(n-1,n-2) .. p(n-1,n-1)

%C row 2 ... 0 ..... 0 ............ p(n-2,n-3) .. p(n-2,n-2)

%C ...

%C row n-1 . 0 ..... 0 ............. p(2,1) ..... p(2,2)

%C row n ... 0 ..... 0 ............. p(1,0) ..... p(1,1)

%C ...

%C 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:

%C ...

%C row 0 of W:  1, by decree

%C row 1 of W:  1 augments to 1,1

%C ...polynomial version:  1 -> x+1

%C row 2 of W:  1,1 augments to 1,3,2

%C ...polynomial version:  x+1 -> (x^2+2x+1)+(x+1)=x^2+3x+2

%C row 3 to W:  1,3,2 augments to 1,6,11,6

%C ...polynomial version:

%C     x^2+3x+2 -> (x+1)^3+3(x+1)^2+2(x+1)=(x+1)(x+2)(x+3)

%C ...

%C Examples of augmented triangular arrays:

%C (p(n,k)=1) augments to A009766, Catalan triangle.

%C Catalan triangle augments to A193560.

%C Pascal triangle augments to A094638, Stirling triangle.

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

%C A154325 augments to A033878.

%C A158405 augments to A193091.

%C ((k!)) augments to A193092.

%C A094727 augments to A193093.

%C A130296 augments to A193094.

%C A004736 augments to A193561.

%C ...

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

%C From _Peter Bala_, Aug 02 2012: (Start)

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

%C ............a_1 a_2 ... a_n..........

%C ............b_1 b_2 ... b_n..........

%C such that

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

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

%C 3) max(a_n, b_n) = k.

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

%C (End)

%H L. Carlitz, <a href="http://www.fq.math.ca/11-2.html">Enumeration of two-line arrays</a>, Fib. Quart., Vol. 11 Number 2 (1973), 113-130.

%F From _Peter Bala_, Aug 02 2012: (Start)

%F 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.

%F Recurrence equation: T(n,k) = Sum_{i=0..k} (2*k-2*i+1)*T(n-1,i).

%F (End)

%e The triangle P, at A158405, is given by rows

%e 1

%e 1...3

%e 1...3...5

%e 1...3...5...7

%e 1...3...5...7...9...

%e 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:

%e ...

%e 1->x+3, so that W has (row 1)=(1,3);

%e ...

%e x+3->(x^2+3x+5)+3*(x+3), so that W has (row 2)=(1,6,14);

%e ...

%e 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).

%e ...

%e First 7 rows of W:

%e 1

%e 1    3

%e 1    6    14

%e 1    9    37    79

%e 1   12    69   242    494

%e 1   15   110   516   1658    3294

%e 1   18   160   928   3870   11764   22952

%t p[n_, k_] := 2 k + 1

%t Table[p[n, k], {n, 0, 5}, {k, 0, n}] (* A158405 *)

%t m[n_] := Table[If[i <= j, p[n + 1 - i, j - i], 0], {i, n}, {j, n + 1}]

%t TableForm[m[4]]

%t w[0, 0] = 1; w[1, 0] = p[1, 0]; w[1, 1] = p[1, 1];

%t v[0] = w[0, 0]; v[1] = {w[1, 0], w[1, 1]};

%t v[n_] := v[n - 1].m[n]

%t TableForm[Table[v[n], {n, 0, 6}]] (* A193091 *)

%t Flatten[Table[v[n], {n, 0, 9}]]

%Y Cf. A003169, A193092, A193093, A193094.

%Y Cf. A071948, A211788.

%K nonn,tabl,easy

%O 0,3

%A _Clark Kimberling_, Jul 30 2011