A091499 Triangle read by rows, such that T(n,k) equals the k-th term of the convolution of the two prior rows indexed by (n-k) and (k-1).

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 2, 3, 3, 1, 1, 1, 2, 4, 4, 3, 1, 1, 1, 2, 4, 6, 5, 4, 1, 1, 1, 2, 4, 7, 8, 7, 4, 1, 1, 1, 2, 4, 8, 10, 12, 8, 5, 1, 1, 1, 2, 4, 9, 13, 15, 16, 10, 5, 1, 1, 1, 2, 4, 9, 15, 20, 22, 21, 12, 6, 1, 1, 1, 2, 4, 9, 17, 25, 31, 31, 27, 14, 6, 1, 1, 1, 2, 4, 9

Offset

0,9

Comments

Row sums are A091501. Convergent of rows is A091500: {1, 1, 2, 4, 9, 20, 47, 113, 275, 676, 1685, 4271, 10843, 27801, 71611, 185795, ...}.

Links

Paul D. Hanna, Table of n, a(n) for n = 0..1652

Formula

T(n, k) = Sum_{j=0..min(n-k, k)} T(n-k, j)*T(k-1, k-j-1), with T(n, 0) = 1, T(n, n) = 1 for n >= 0.

Example

T(7,3) = 4 = third term of convolution[{1,1,2,2,1},{1,1,1}] = 1*1 + 1*1 + 2*1 = T(4,0)*T(2,2) + T(4,1)*T(2,1) + T(4,2)*T(2,0).
T(14,5) = 19 = 5th term of convolution[{1,1,2,4,8,10,12,8,5,1},{1,1,2,2,1}] = 1*1 + 1*2 + 2*2 + 4*1 + 8*1 = T(9,0)*T(4,4) + T(9,1)*T(4,3) + T(9,2)*T(4,2) + T(9,3)*T(4,1) + T(9,4)*T(4,0).
Rows begin:
  1;
  1,  1;
  1,  1,  1;
  1,  1,  2,  1;
  1,  1,  2,  2,  1;
  1,  1,  2,  3,  3,  1;
  1,  1,  2,  4,  4,  3,  1;
  1,  1,  2,  4,  6,  5,  4,  1;
  1,  1,  2,  4,  7,  8,  7,  4,  1;
  1,  1,  2,  4,  8, 10, 12,  8,  5,  1;
  1,  1,  2,  4,  9, 13, 15, 16, 10,  5,  1;
  1,  1,  2,  4,  9, 15, 20, 22, 21, 12,  6,  1;
  1,  1,  2,  4,  9, 17, 25, 31, 31, 27, 14,  6,  1;
  ...

Prog

(PARI) {T(n, k)=if(k>n||n<0||k<0, 0, if(k<=1||k==n, 1, sum(j=0, min(n-k, k), T(n-k, j)*T(k-1, k-j-1))))}
(PARI) \* Faster - using N X N matrix in recursion *\
N = 30; M=matrix(N, N);
{T(n, k) = M[n+1, k+1] = if(k>n||n<0||k<0, 0, if(k<=1||k==n, 1, sum(j=0, min(n-k, k), T(n-k, j)*if(k<1||k-j<1, 0, M[k, k-j]))))}
for(n=0, N-1, for(k=0, n, print1(T(n, k), ", ")); print(""))

Crossrefs

Cf. A091500, A091501.

Sequence in context: A055215 A239550 A058398 * A284249 A137350 A334607

Adjacent sequences: A091496 A091497 A091498 * A091500 A091501 A091502

Keyword

nonn,tabl

Author

Paul D. Hanna, Jan 16 2004

Status

approved