A055807 Triangle T read by rows: T(i,j) = R(i-j,j), where R(i,0) = 1 for i >= 0, R(0,j) = 0 for j >= 1, and R(i,j) = Sum_{h=0..i-1, k=0..j} R(h,k) for i >= 1 and j >= 1.

1, 1, 0, 1, 1, 0, 1, 3, 1, 0, 1, 7, 4, 1, 0, 1, 15, 12, 5, 1, 0, 1, 31, 32, 18, 6, 1, 0, 1, 63, 80, 56, 25, 7, 1, 0, 1, 127, 192, 160, 88, 33, 8, 1, 0, 1, 255, 448, 432, 280, 129, 42, 9, 1, 0, 1, 511, 1024, 1120, 832, 450, 180, 52, 10, 1, 0, 1, 1023

Offset

0,8

Comments

Formatted as a triangular array, it is [1, 0, 1, 1, 0, 0, 0, 0, 0, ...] DELTA [0, 1, 0, -1, 1, 0, 0, 0, 0, ...] where DELTA is the operator defined in A084938. - Philippe Deléham, Nov 05 2006

The square array (R(n,k): n,k >= 0) referred to in the name of the sequence is actually A050143. - Petros Hadjicostas, Feb 13 2021

Links

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

Rigoberto Flórez, Leandro Junes, and José L. Ramírez, Enumerating several aspects of non-decreasing Dyck paths, Discrete Mathematics Vol. 342, Issue 11 (2019), 3079-3097. See page 3091. Gives the triangle in a slightly different form (see the Examples section).

Clark Kimberling, Path-counting and Fibonacci numbers, Fib. Quart. 40(4) (2002) 328-338, Example 3A.

Formula

T(2*n,n) = A050146(n).

G.f.: (1-2*x)*(1-x*y)/((1-x)*(1-x*y-2*x+x^2*y)). - R. J. Mathar, Aug 11 2015

From Petros Hadjicostas, Feb 13 2021: (Start)

T(n,k) = A050143(n-k, k) for 0 <= k <= n.

T(n,k) = (n-k)*hypergeom([-n + k + 1, k], [2], -1) = Sum_{s=1..n-k} binomial(n-k,s)*binomial(s+k-2,k-1) for 1 <= k <= n.

T(n,k) = 2*T(n-1,k) + T(n-1,k-1) - T(n-2,k-1) for 2 <= k <= n-1 with initial conditions T(n,0) = 1 for n >= 0, T(n,n) = 0 for n >= 1, and T(n,1) = 2^(n-1) - 1 for n >= 2. (End)

Example

Triangle T(n,k) (with rows n >= 0 and columns k = 0..n) begins:
  1;
  1,   0;
  1,   1,   0;
  1,   3,   1,   0;
  1,   7,   4,   1,   0;
  1,  15,  12,   5,   1,   0;
  1,  31,  32,  18,   6,   1,  0;
  1,  63,  80,  56,  25,   7,  1, 0;
  1, 127, 192, 160,  88,  33,  8, 1, 0;
  1, 255, 448, 432, 280, 129, 42, 9, 1, 0;
  ...
Florez et al. (2019) give the triangle in this form:
    1,    0,    0,   0,   0,   0,  0,  0, 0, ...
    3,    1,    0,   0,   0,   0,  0,  0, 0, ...
    7,    4,    1,   0,   0,   0,  0,  0, 0, ...
   15,   12,    5,   1,   0,   0,  0,  0, 0, ...
   31,   32,   18,   6,   1,   0,  0,  0, 0, ...
   63,   80,   56,  25,   7,   1,  0,  0, 0, ...
  127,  192,  160,  88,  33,   8,  1,  0, 0, ...
  255,  448,  432, 280, 129,  42,  9,  1, 0, ...
  511, 1024, 1120, 832, 450, 180, 52, 10, 1, ...
  ...

Maple

T:= proc(i, j) option remember;
      if j=0 then 1
    elif i=0 then 0
    else add(add(T(h, m), m=0..j), h=0..i-1)
      fi; end:
seq(seq(T(n-k, k), k=0..n), n=0..12); # G. C. Greubel, Jan 23 2020

Mathematica

T[i_, j_]:= T[i, j]= If[j==0, 1, If[i==0, 0, Sum[T[h, m], {h, 0, i-1}, {m, 0, j}]]]; Table[T[n-k, k], {n, 0, 12}, {k, 0, n}]//Flatten (* G. C. Greubel, Jan 23 2020 *)

Prog

(PARI) T(i, j) = if(j==0, 1, if(i==0, 0, sum(h=0, i-1, sum(m=0, j, T(h, m) ))));
for(n=0, 12, for(k=0, n, print1(T(n-k, k), ", "))) \\ G. C. Greubel, Jan 23 2020
(Magma)
function T(i, j)
  if j eq 0 then return 1;
  elif i eq 0 then return 0;
  else return (&+[(&+[T(h, m): m in [0..j]]): h in [0..i-1]]);
  end if; return T; end function;
[T(n-k, k): k in [0..n], n in [0..12]]; // G. C. Greubel, Jan 23 2020
(Sage)
@CachedFunction
def T(i, j):
    if j==0: return 1
    elif i==0: return 0
    else: return sum(sum(T(h, m) for m in (0..j)) for h in (0..i-1))
[[T(n-k, k) for k in (0..n)] for n in (0..12)] # G. C. Greubel, Jan 23 2020
(GAP)
T:= function(i, j)
    if j=0 then return 1;
    elif i=0 then return 0;
    else return Sum([0..i-1], h-> Sum([0..j], m-> T(h, m) ));
    fi; end;
Flat(List([0..12], n-> List([0..n], k-> T(n-k, k) ))); # G. C. Greubel, Jan 23 2020

Crossrefs

Rows sums: A001519 (odd-indexed Fibonacci numbers).

Cf. A050143, A050147, A050148, A111516.

Cf. A055809, A055810, A055811, A055815, A055816, A055817.

Sequence in context: A308484 A227320 A318507 * A364285 A213060 A272008

Adjacent sequences: A055804 A055805 A055806 * A055808 A055809 A055810

Keyword

nonn,tabl

Author

Clark Kimberling, May 28 2000

Status

approved