login
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).
4
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
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
Sequence in context: A055215 A239550 A058398 * A284249 A137350 A334607
KEYWORD
nonn,tabl
AUTHOR
Paul D. Hanna, Jan 16 2004
STATUS
approved