A117418 Triangle T, read by rows, such that column 2k+1 of T equals column k of T^2 and column 2k of T equals column k of T*R: [T^2](n+k,k) = T(n+2k+1,2k+1) and [T*R](n+k,k) = T(n+2k,2k) for n>=0, k>=0, where R = SHIFT_RIGHT(T).

1, 1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 9, 8, 4, 1, 1, 23, 22, 14, 5, 1, 1, 66, 65, 50, 20, 6, 1, 1, 209, 208, 191, 79, 28, 7, 1, 1, 724, 723, 780, 322, 126, 37, 8, 1, 1, 2722, 2721, 3415, 1385, 572, 180, 48, 9, 1, 1, 11054, 11053, 15924, 6293, 2692, 871, 264, 58, 10, 1

Offset

0,5

Comments

Here SHIFT_RIGHT(T) shifts the columns of T one place to the right and fills column 0 with [1,0,0,0,...].

Links

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Formula

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

Example

Triangle T begins:
  1;
  1,     1;
  1,     2,     1;
  1,     4,     3,     1;
  1,     9,     8,     4,    1;
  1,    23,    22,    14,    5,    1;
  1,    66,    65,    50,   20,    6,   1;
  1,   209,   208,   191,   79,   28,   7,   1;
  1,   724,   723,   780,  322,  126,  37,   8,  1;
  1,  2722,  2721,  3415, 1385,  572, 180,  48,  9,  1;
  1, 11054, 11053, 15924, 6293, 2692, 871, 264, 58, 10, 1;
The matrix square T^2 = A117427:
    1;
    2,   1;
    4,   4,   1;
    9,  14,   6,   1;
   23,  50,  28,   8,  1;
   66, 191, 126,  48, 10,  1;
  209, 780, 572, 264, 70, 12, 1;
where column k of T^2 equals column 2k+1 of T.
Let matrix R = SHIFT_RIGHT(T):
  1;
  0, 1;
  0, 1,  1;
  0, 1,  2,  1;
  0, 1,  4,  3,  1;
  0, 1,  9,  8,  4, 1;
  0, 1, 23, 22, 14, 5, 1;
then matrix product T*R = A117425:
  1;
  1,   1;
  1,   3,   1;
  1,   8,   5,   1;
  1,  22,  20,   7,  1;
  1,  65,  79,  37,  9,  1;
  1, 208, 322, 180, 58, 11, 1;
where column k of T*R equals column 2k of T.

Mathematica

A117418[n_, k_]:= T[n, k]= If[k<0 || k>n, 0, If[k==0 || k==n, 1, If[k==n-1, n, Sum[A117418[n -Floor[(k+1)/2], Floor[k/2] +j]*A117418[Floor[(k-1)/2] +j, Floor[(k-1)/2]], {j, 0, n-k}] ]]];
Table[A117418[n, k], {n, 0, 12}, {k, 0, n}]//Flatten (* G. C. Greubel, May 31 2021 *)

Prog

(PARI) T(n, k)=if(n<k || k<0, 0, if(n==k || k==0, 1, if(n==k+1, n, sum(j=0, n-k, T(n-((k+1)\2), k\2+j)*T((k-1)\2+j, (k-1)\2)))))
(Sage)
@CachedFunction
def A117418(n, k):
    if (k<0 or k>n): return 0
    elif (k==0 or k==n): return 1
    elif (k==n-1): return n
    else: return sum( A117418(n -(k+1)//2, k//2 +j)*A117418((k-1)//2 +j, (k-1)//2) for j in (0..n-k))
flatten([[A117418(n, k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, May 31 2021

Crossrefs

Cf. A117419, A117420, A117421, A117422, A117423, A117424, A117425 (T*SHIFT_RIGHT(T)), A117427 (T^2), A117428.

Sequence in context: A204849 A105632 A091491 * A101494 A125781 A091150

Adjacent sequences: A117415 A117416 A117417 * A117419 A117420 A117421

Keyword

nonn,tabl

Author

Paul D. Hanna, Mar 14 2006

Status

approved