login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 11
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 (list; table; graph; refs; listen; history; text; internal format)
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 * A213060 A272008 A054024

Adjacent sequences:  A055804 A055805 A055806 * A055808 A055809 A055810

KEYWORD

nonn,tabl

AUTHOR

Clark Kimberling, May 28 2000

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 22 22:19 EDT 2021. Contains 343197 sequences. (Running on oeis4.)