login
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

%I #56 Sep 08 2022 08:45:01

%S 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,

%T 56,25,7,1,0,1,127,192,160,88,33,8,1,0,1,255,448,432,280,129,42,9,1,0,

%U 1,511,1024,1120,832,450,180,52,10,1,0,1,1023

%N 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.

%C 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

%C 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

%H G. C. Greubel, <a href="/A055807/b055807.txt">Rows n = 0..100 of triangle, flattened</a>

%H Rigoberto Flórez, Leandro Junes, and José L. Ramírez, <a href="https://doi.org/10.1016/j.disc.2019.06.018">Enumerating several aspects of non-decreasing Dyck paths</a>, Discrete Mathematics Vol. 342, Issue 11 (2019), 3079-3097. See page 3091. Gives the triangle in a slightly different form (see the Examples section).

%H Clark Kimberling, <a href="https://www.fq.math.ca/Scanned/40-4/kimberling.pdf">Path-counting and Fibonacci numbers</a>, Fib. Quart. 40(4) (2002) 328-338, Example 3A.

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

%F G.f.: (1-2*x)*(1-x*y)/((1-x)*(1-x*y-2*x+x^2*y)). - _R. J. Mathar_, Aug 11 2015

%F From _Petros Hadjicostas_, Feb 13 2021: (Start)

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

%F 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.

%F 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)

%e Triangle T(n,k) (with rows n >= 0 and columns k = 0..n) begins:

%e 1;

%e 1, 0;

%e 1, 1, 0;

%e 1, 3, 1, 0;

%e 1, 7, 4, 1, 0;

%e 1, 15, 12, 5, 1, 0;

%e 1, 31, 32, 18, 6, 1, 0;

%e 1, 63, 80, 56, 25, 7, 1, 0;

%e 1, 127, 192, 160, 88, 33, 8, 1, 0;

%e 1, 255, 448, 432, 280, 129, 42, 9, 1, 0;

%e ...

%e Florez et al. (2019) give the triangle in this form:

%e 1, 0, 0, 0, 0, 0, 0, 0, 0, ...

%e 3, 1, 0, 0, 0, 0, 0, 0, 0, ...

%e 7, 4, 1, 0, 0, 0, 0, 0, 0, ...

%e 15, 12, 5, 1, 0, 0, 0, 0, 0, ...

%e 31, 32, 18, 6, 1, 0, 0, 0, 0, ...

%e 63, 80, 56, 25, 7, 1, 0, 0, 0, ...

%e 127, 192, 160, 88, 33, 8, 1, 0, 0, ...

%e 255, 448, 432, 280, 129, 42, 9, 1, 0, ...

%e 511, 1024, 1120, 832, 450, 180, 52, 10, 1, ...

%e ...

%p T:= proc(i, j) option remember;

%p if j=0 then 1

%p elif i=0 then 0

%p else add(add(T(h,m), m=0..j), h=0..i-1)

%p fi; end:

%p seq(seq(T(n-k, k), k=0..n), n=0..12); # _G. C. Greubel_, Jan 23 2020

%t 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 *)

%o (PARI) T(i,j) = if(j==0, 1, if(i==0, 0, sum(h=0,i-1, sum(m=0,j, T(h,m) ))));

%o for(n=0,12, for(k=0, n, print1(T(n-k,k), ", "))) \\ _G. C. Greubel_, Jan 23 2020

%o (Magma)

%o function T(i,j)

%o if j eq 0 then return 1;

%o elif i eq 0 then return 0;

%o else return (&+[(&+[T(h,m): m in [0..j]]): h in [0..i-1]]);

%o end if; return T; end function;

%o [T(n-k,k): k in [0..n], n in [0..12]]; // _G. C. Greubel_, Jan 23 2020

%o (Sage)

%o @CachedFunction

%o def T(i, j):

%o if j==0: return 1

%o elif i==0: return 0

%o else: return sum(sum(T(h,m) for m in (0..j)) for h in (0..i-1))

%o [[T(n-k, k) for k in (0..n)] for n in (0..12)] # _G. C. Greubel_, Jan 23 2020

%o (GAP)

%o T:= function(i,j)

%o if j=0 then return 1;

%o elif i=0 then return 0;

%o else return Sum([0..i-1], h-> Sum([0..j], m-> T(h,m) ));

%o fi; end;

%o Flat(List([0..12], n-> List([0..n], k-> T(n-k,k) ))); # _G. C. Greubel_, Jan 23 2020

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

%Y Cf. A050143, A050147, A050148, A111516.

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

%K nonn,tabl

%O 0,8

%A _Clark Kimberling_, May 28 2000