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