A038792 Rectangular array defined by T(i,1) = T(1,j) = 1 for i >= 1 and j >= 1; T(i,j) = max(T(i-1,j) + T(i-1,j-1), T(i-1,j-1) + T(i,j-1)) for i >= 2, j >= 2, read by antidiagonals.

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 5, 4, 1, 1, 5, 8, 8, 5, 1, 1, 6, 12, 13, 12, 6, 1, 1, 7, 17, 21, 21, 17, 7, 1, 1, 8, 23, 33, 34, 33, 23, 8, 1, 1, 9, 30, 50, 55, 55, 50, 30, 9, 1, 1, 10, 38, 73, 88, 89, 88, 73, 38, 10, 1, 1, 11, 47, 103, 138, 144, 144, 138, 103, 47, 11, 1

Offset

1,5

Comments

Antidiagonal sums: A029907.

Main diagonal: A001519 (odd-indexed Fibonacci numbers).

Next diagonal: A001906 (even-indexed Fibonacci numbers).

Links

G. C. Greubel, Antidiagonals n = 1..50, flattened

H. Belbachir and A. Belkhir, Combinatorial Expressions Involving Fibonacci, Hyperfibonacci, and Incomplete Fibonacci Numbers, Journal of Integer Sequences, Vol. 17 (2014), Article 14.4.3.

A. Dil and I. Mezo, A symmetric algorithm for hyperharmonic and Fibonacci numbers, Appl. Math. Comp. 206 (2008), 942-951; in Eqs. (11), see the incomplete Fibonacci numbers.

Piero Filipponi, Incomplete Fibonacci and Lucas numbers, P. Rend. Circ. Mat. Palermo (Serie II) 45(1) (1996), 37-56; see Table 1 that contains the incomplete Fibonacci numbers.

Clark Kimberling, Path-counting and Fibonacci numbers, Fib. Quart. 40 (4) (2002), 328-338; see Example 4 (appears as a triangular array).

A. Pintér and H.M. Srivastava, Generating functions of the incomplete Fibonacci and Lucas numbers, Rend. Circ. Mat. Palermo (Serie II) 48(3) (1999), 591-596.

Formula

G.f.: x*y*(1-x*y)/((x*y+x-1)*(x*y+y-1)). - Mark van Hoeij, Nov 09 2011

From Petros Hadjicostas, Sep 02 2019: (Start)

Following Dil and Mezo (2008), define the incomplete Fibonacci numbers by F(n,k) = Sum_{s = 0..k} binomial(n-1-s, s) for n >= 1 and 0 <= k <= floor((n-1)/2).

Then T(i, j) = F(i+j-1, min(i-1, j-1)) for i,j >= 1.

(End)

Example

From Clark Kimberling, Jun 20 2011: (Start)
Northwest corner begins at (i,j) = (1,1):
  1,   1,   1,   1,   1,   1,   1,   1, ...
  1,   2,   3,   4,   5,   6,   7,   8, ...
  1,   3,   5,   8,  12,  17,  23,  30, ...
  1,   4,   8,  13,  21,  33,  50,  73, ...
  1,   5,  12,  21,  34,  55,  88, 138, ...
  1,   6,  17,  33,  55,  89, 144, 232, ...
  1,   7,  23,  50,  88, 144, 233, 377, ...
(End)
Antidiagonal triangle begins as:
  1;
  1, 1;
  1, 2,  1;
  1, 3,  3,  1;
  1, 4,  5,  4,  1;
  1, 5,  8,  8,  5,  1;
  1, 6, 12, 13, 12,  6,  1;
  1, 7, 17, 21, 21, 17,  7,  1;
  1, 8, 23, 33, 34, 33, 23,  8, 1;
  1, 9, 30, 50, 55, 55, 50, 30, 9, 1;

Maple

G := x*y*(1-x*y)/((x*y+x-1)*(x*y+y-1)); G := convert(series(G, x=0, 11), polynom):
for i from 1 to 10 do series(coeff(G, x, i), y=0, 11) od; # Mark van Hoeij, Nov 09 2011
# second Maple program:
G:= x*y*(1-x*y)/((x*y+x-1)*(x*y+y-1)):
T:= (i, j)-> coeff(series(coeff(series(G, y, j+1), y, j), x, i+1), x, i):
seq(seq(T(i, 1+d-i), i=1..d), d=1..12); # Alois P. Heinz, Sep 02 2019
# third Maple program:
T:= proc(i, j) option remember; `if`(i=1 or j=1, 1,
      max(T(i-1, j) + T(i-1, j-1), T(i-1, j-1) + T(i, j-1)))
    end:
seq(seq(T(i, 1+d-i), i=1..d), d=1..12); # Alois P. Heinz, Sep 02 2019

Mathematica

f[i_, 0]:= 1; f[0, i_]:= 1
f[i_, j_]:= f[i, j]= Max[f[i-1, j] +f[i-1, j-1], f[i-1, j-1] +f[i, j-1]];
T[i_, j_]:= f[i-j, j-1];
TableForm[Table[f[i, j], {i, 0, 7}, {j, 0, 7}]]
Table[T[i, j], {i, 10}, {j, i}]//Flatten (* modified by G. C. Greubel, Apr 05 2022 *)

Prog

(Magma)
function t(n, k)
  if k eq 0 or n eq 0 then return 1;
  else return Max(t(n-1, k-1) + t(n-1, k), t(n-1, k-1) + t(n, k-1));
  end if; return t;
end function;
T:= func< n, k | t(n-k, k-1) >;
[T(n, k): k in [1..n], n in [1..12]]; // G. C. Greubel, Apr 05 2022
(SageMath)
def t(n, k):
    if (k==0 or n==0): return 1
    else: return max(t(n-1, k-1) + t(n-1, k), t(n-1, k-1) + t(n, k-1))
def A038792(n, k): return t(n-k, k-1)
flatten([[A038792(n, k) for k in (1..n)] for n in (1..12)]) # G. C. Greubel, Apr 05 2022

Crossrefs

Cf. A001519, A001906, A029907.

Cf. A000045, A038730, A134511, A324242.

Main diagonal gives A001519.

Sequence in context: A259874 A256141 A072704 * A196416 A329329 A306697

Adjacent sequences: A038789 A038790 A038791 * A038793 A038794 A038795

Keyword

nonn,tabl,easy

Author

Clark Kimberling, May 02 2000

Extensions

New description from Benoit Cloitre, Aug 05 2003

Updated from pre-2003 triangular format to present rectangular, from Clark Kimberling, Jun 20 2011

Status

approved