A352682 -id:A352682 - cp's OEIS frontend

A352744 Array read by ascending antidiagonals. Generalized Fibonacci numbers F(n, k) = (psi^k(phi - n) - phi^k(psi - n)) / (phi - psi) where phi = (1 + sqrt(5))/2 and psi = (1 - sqrt(5))/2. F(n, k) for n >= 0 and k >= 0.

1, 1, 0, 1, 1, 1, 1, 2, 2, 1, 1, 3, 3, 3, 2, 1, 4, 4, 5, 5, 3, 1, 5, 5, 7, 8, 8, 5, 1, 6, 6, 9, 11, 13, 13, 8, 1, 7, 7, 11, 14, 18, 21, 21, 13, 1, 8, 8, 13, 17, 23, 29, 34, 34, 21, 1, 9, 9, 15, 20, 28, 37, 47, 55, 55, 34, 1, 10, 10, 17, 23, 33, 45, 60, 76, 89, 89, 55

Offset: 0

Peter Luschny, Apr 01 2022

The definition declares the Fibonacci numbers for all integers n and k. An alternative version is A353595.
The identity F(n, k) = (-1)^k*F(1 - n, -k) holds for all integers n, k. Proof:
     F(n, k)*(2+phi) = (phi^k*(n*phi + 1) - (-phi)^(-k)*((n-1)*phi - 1))
                     = (-1)^k*(phi^(-k)*((1-n)*phi+1) - (-phi)^k*(-n*phi-1))
                     = (-1)^k*F(1-n, -k)*(2+phi).
This identity can be seen as an extension of Cassini's theorem of 1680 and of an identity given by Graham, Knuth and Patashnik in 'Concrete Mathematics' (6.106 and 6.107). The beginning of the full array with arguments in Z x Z can be found in the linked note.
The enumeration is the result of the simple form of the chosen definition. The classical positive Fibonacci numbers starting with 1, 1, 2, 3,... are in row n = 1 with offset 0. The nonnegative Fibonacci numbers starting 0, 1, 1, 2, 3,... are in row 0 with offset 1. They prolong towards -infinity with an index shifted by 1 compared to the enumeration used by Knuth. A characteristic of our enumeration is F(n, 0) = 1 for all integer n.
Fibonacci numbers vanish only for (n,k) in {(-1,2), (0,1), (1,-1), (2,-2)}. The zeros correspond to the identities (phi + 1)*psi^2 = (psi + 1)*phi^2, psi*phi = phi*psi, (phi - 1)*phi = (psi - 1)*psi and (phi - 2)*phi^2 = (psi - 2)*psi^2.
For divisibility properties see A352747.
For any fixed k, the sequence F(n, k) is a linear function of n. In other words, an arithmetic progression. This implies that F(n+1, k) = 2*F(n, k) - F(n-1, k) for all n in Z. Special case of this is Fibonacci(n+1) = 2 *Fibonacci(n) - Fibonacci(n-2). - Michael Somos, May 08 2022

			Array starts:
n\k 0, 1,  2,  3,  4,  5,  6,   7,   8,   9, ...
---------------------------------------------------------
[0] 1, 0,  1,  1,  2,  3,  5,   8,  13,  21, ... A212804
[1] 1, 1,  2,  3,  5,  8, 13,  21,  34,  55, ... A000045 (shifted once)
[2] 1, 2,  3,  5,  8, 13, 21,  34,  55,  89, ... A000045 (shifted twice)
[3] 1, 3,  4,  7, 11, 18, 29,  47,  76, 123, ... A000032 (shifted once)
[4] 1, 4,  5,  9, 14, 23, 37,  60,  97, 157, ... A000285
[5] 1, 5,  6, 11, 17, 28, 45,  73, 118, 191, ... A022095
[6] 1, 6,  7, 13, 20, 33, 53,  86, 139, 225, ... A022096
[7] 1, 7,  8, 15, 23, 38, 61,  99, 160, 259, ... A022097
[8] 1, 8,  9, 17, 26, 43, 69, 112, 181, 293, ... A022098
[9] 1, 9, 10, 19, 29, 48, 77, 125, 202, 327, ... A022099

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, sec. 6.6.
Donald Ervin Knuth, The Art of Computer Programming, Third Edition, Vol. 1, Fundamental Algorithms. Chapter 1.2.8 Fibonacci Numbers. Addison-Wesley, Reading, MA, 1997.

Alexander Bogomolny, Cassini's Identity.
Edsger W. Dijkstra, In honour of Fibonacci, in: F. L. Bauer, M. Broy, & E. W. Dijkstra (editors), Program Construction, 1979, Lecture Notes in Computer Science, Vol. 69.
Peter Luschny, The Fibonacci Function.

Rows: A212804, A000045, A000032, A000285, A022095, A022096, A022097, A022098, A022099.
Columns: A000012, A001477, A000027, A005408, A016789, A016885, A004770.
Diagonals: A088209 (main), A007502, A066982 (antidiagonal sums).
Cf. A352747, A353595 (alternative version), A354265 (generalized Lucas numbers).
Similar arrays based on the Catalan and the Bell numbers are A352680 and A352682.

# Time complexity is O(lg n).
function fibrec(n::Int)
    n == 0 && return (BigInt(0), BigInt(1))
    a, b = fibrec(div(n, 2))
    c = a * (b * 2 - a)
    d = a * a + b * b
    iseven(n) ? (c, d) : (d, c + d)
end
function Fibonacci(n::Int, k::Int)
    k == 0 && return BigInt(1)
    k  < 0 && return (-1)^k*Fibonacci(1 - n, -k)
    a, b = fibrec(k - 1)
    a + b*n
end
for n in -6:6
    println([Fibonacci(n, k) for k in -6:6])
end

f := n -> combinat:-fibonacci(n + 1): F := (n, k) -> (n-1)*f(k-1) + f(k):
seq(seq(F(n-k, k), k = 0..n), n = 0..9);
# The next implementation is for illustration only but is not recommended
# as it relies on floating point arithmetic.
phi := (1 + sqrt(5))/2: psi := (1 - sqrt(5))/2:
F := (n, k) -> (psi^k*(phi - n) - phi^k*(psi - n)) / (phi - psi):
for n from -6 to 6 do lprint(seq(simplify(F(n, k)), k = -6..6)) od;

Table[LinearRecurrence[{1, 1}, {1, n}, 10], {n, 0, 9}] // TableForm
F[ n_, k_] := (MatrixPower[{{0, 1}, {1, 1}}, k].{{1}, {n}})[[1, 1]]; (* Michael Somos, May 08 2022 *)
c := Pi/2 - I*ArcSinh[1/2]; (* Based on a remark from Bill Gosper. *)
F[n_, k_] := 2 (I (n-1) Sin[k c] + Sin[(k+1) c]) / (I^k Sqrt[5]);
Table[Simplify[F[n, k]], {n, -6, 6}, {k, -6, 6}] // TableForm (* Peter Luschny, May 10 2022 *)

F(n, k) = ([0, 1; 1, 1]^k*[1; n])[1, 1]

{F(n, k) = n*fibonacci(k) + fibonacci(k-1)}; /* Michael Somos, May 08 2022 */

F(n, k) = F(n, k-1) + F(n, k-2) for k >= 2, otherwise 1, n for k = 0, 1.
F(n, k) = (n-1)*f(k-1) + f(k) where f(n) = A000045(n+1), the Fibonacci numbers starting with f(0) = 1.
F(n, k) = ((phi^k*(n*phi + 1) - (-phi)^(-k)*((n - 1)*phi - 1)))/(2 + phi).
F(n, k) = [x^k] (1 + (n - 1)*x)/(1 - x - x^2) for k >= 0.
F(k, n) = [x^k] (F(0, n) + F(0, n-1)*x)/(1 - x)^2 for k >= 0.
F(n, k) = (k!/sqrt(5))*[x^k] ((n-psi)*exp(phi*x) - (n-phi)*exp(psi*x)) for k >= 0.
F(n, k) - F(n-1, k) = sign(k)^(n-1)*f(k) for all n, k in Z, where A000045 is extended to negative integers by f(-n) = (-1)^(n-1)*f(n) (CMath 6.107). - Peter Luschny, May 09 2022
F(n, k) = 2*((n-1)*i*sin(k*c) + sin((k+1)*c))/(i^k*sqrt(5)) where c = Pi/2 - i*arcsinh(1/2), for all n, k in Z. Based on a remark from Bill Gosper. - Peter Luschny, May 10 2022

A352680 Array read by ascending antidiagonals. A family of Catalan-like sequences. A(n, k) = [x^k] ((n - 1)x + 1)(1 - sqrt(1 - 4x))/(2x).

Original entry on oeis.org

1, 1, 0, 1, 1, 1, 1, 2, 2, 3, 1, 3, 3, 5, 9, 1, 4, 4, 7, 14, 28, 1, 5, 5, 9, 19, 42, 90, 1, 6, 6, 11, 24, 56, 132, 297, 1, 7, 7, 13, 29, 70, 174, 429, 1001, 1, 8, 8, 15, 34, 84, 216, 561, 1430, 3432, 1, 9, 9, 17, 39, 98, 258, 693, 1859, 4862, 11934, 1, 10, 10, 19, 44, 112, 300, 825, 2288, 6292, 16796, 41990

Offset: 0

Peter Luschny, Mar 27 2022

			Array starts:
n\k 0, 1,  2,  3,  4,   5,   6,    7,    8,     9, ...
------------------------------------------------------
[0] 1, 0,  1,  3,  9,  28,  90,  297, 1001,  3432, ... A071724
[1] 1, 1,  2,  5, 14,  42, 132,  429, 1430,  4862, ... A000108
[2] 1, 2,  3,  7, 19,  56, 174,  561, 1859,  6292, ... A071716
[3] 1, 3,  4,  9, 24,  70, 216,  693, 2288,  7722, ... A038629
[4] 1, 4,  5, 11, 29,  84, 258,  825, 2717,  9152, ... A352681
[5] 1, 5,  6, 13, 34,  98, 300,  957, 3146, 10582, ...
[6] 1, 6,  7, 15, 39, 112, 342, 1089, 3575, 12012, ...
[7] 1, 7,  8, 17, 44, 126, 384, 1221, 4004, 13442, ...
[8] 1, 8,  9, 19, 49, 140, 426, 1353, 4433, 14872, ...
[9] 1, 9, 10, 21, 54, 154, 468, 1485, 4862, 16302, ...
.
Seen as a triangle:
[0] 1;
[1] 1, 0;
[1] 1, 1, 1;
[2] 1, 2, 2,  3;
[3] 1, 3, 3,  5,  9;
[4] 1, 4, 4,  7, 14, 28;
[5] 1, 5, 5,  9, 19, 42,  90;
[6] 1, 6, 6, 11, 24, 56, 132, 297;

Rows: A071724, A000108, A071716, A038629, A352681.
Diagonals: A077587 (main), A271823.
Compare A352682 for a similar array based on the Bell numbers.

# Compare with the Julia function A352686Row.
function A352680Row(n, len)
    a = BigInt(n)
    P = BigInt[1]; T = BigInt[1]
    for k in 0:len-1
        T = push!(T, a)
        P = cumsum(push!(P, a))
        a = P[end]
    end
T end
for n in 0:9 println(A352680Row(n, 9)) end

for n from 0 to 9 do
    ogf := ((n - 1)*x + 1)*(1 - sqrt(1 - 4*x))/(2*x);
    ser := series(ogf, x, 12):
    print(seq(coeff(ser, x, k), k = 0..9)); od:
# Alternative:
alias(PS = ListTools:-PartialSums):
CatalanRow := proc(n, len) local a, k, P, R;
a := n; P := [1]; R := [1];
for k from 0 to len-1 do
    R := [op(R), a]; P := PS([op(P), a]); a := P[-1] od;
R end: seq(lprint(CatalanRow(n, 9)), n = 0..9);
# Recurrence:
A := proc(n, k) option remember: if k < 3 then [1, n, n + 1][k + 1] else
A(n, k-1)*((6 - 4*k)*(n - 3 + k*(3 + n)))/((1 + k)*(6 - k*(3 + n))) fi end:
seq(print(seq(A(n, k), k = 0..9)), n = 0..9);

T[n_, 0] := 1;
T[n_, k_] := (n - 1) CatalanNumber[k - 1] + CatalanNumber[k];
Table[T[n, k], {n, 0, 9}, {k, 0, 9}] // TableForm

A(n, k) = (n-1)*CatalanNumber(k-1) + CatalanNumber(k) for n >= 0 and k >= 1, A(n, 0) = 1. (Cf. A352682.)
D-finite with recurrence: A(n, k) = A(n, k-1)*((6 - 4*k)*(n - 3 + k*(3 + n)))/((1 + k)*(6 - k*(3 + n))) for k >= 3, otherwise 1, n, n + 1 for k = 0, 1, 2.
Given a list T let PS(T) denote the list of partial sums of T. Given two list S and T let [S, T] denote the concatenation of the lists. Further let P[end] denote the last element of the list P. Row n of the array A with length k can be computed by the following procedure:
     A = [n], P = [1], R = [1];
     Repeat k times: R = [R, A], P = PS([P, A]), A = [P[end]];
     Return R.

A352686 Triangle read by rows. T(n, k) = (n-1)*Gould(k-1) + Bell(k) for n >= 0 and k >= 1, T(n, 0) = 1.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 1, 3, 4, 11, 1, 4, 5, 14, 42, 1, 5, 6, 17, 51, 176, 1, 6, 7, 20, 60, 207, 808, 1, 7, 8, 23, 69, 238, 929, 4015, 1, 8, 9, 26, 78, 269, 1050, 4538, 21423, 1, 9, 10, 29, 87, 300, 1171, 5061, 23892, 122035, 1, 10, 11, 32, 96, 331, 1292, 5584, 26361, 134646, 738424

Offset: 0

Peter Luschny, Mar 31 2022

			Triangle starts:
[0] 1;
[1] 1, 1;
[2] 1, 2,  3;
[3] 1, 3,  4, 11;
[4] 1, 4,  5, 14, 42;
[5] 1, 5,  6, 17, 51, 176;
[6] 1, 6,  7, 20, 60, 207,  808;
[7] 1, 7,  8, 23, 69, 238,  929, 4015;
[8] 1, 8,  9, 26, 78, 269, 1050, 4538, 21423;
[9] 1, 9, 10, 29, 87, 300, 1171, 5061, 23892, 122035;

Subtriangle of A352682. Main diagonal A352684.

Cf. A000110 (Bell), A040027 (Gould).

function A352686Row(n)
    a = BigInt(n == 0 ? 1 : n)
    P = BigInt[1]; T = BigInt[1]
    for k in 1:n
        T = push!(T, a)
        P = cumsum(pushfirst!(P, a))
        a = P[end]
    end
T end
for n in 0:9 println(A352686Row(n)) end

Bell := n -> combinat:-bell(n):
Gould := proc(n) option remember; ifelse(n = 0, 1,
add(binomial(n, k-1)*Gould(n-k), k = 1..n)) end:
T := (n, k) -> (n-1)*Gould(k-1) + Bell(k):
for n from 0 to 9 do seq(T(n,k), k = 0..n) od;
# Alternative:
alias(PS = ListTools:-PartialSums):
A352686Row := proc(n) local a, k, P, R; a := n; P := [1]; R := [1];
for k from 1 to n do R := [op(R), a]; P := PS([a, op(P)]); a := P[-1] od; R end:
seq(print(A352686Row(n)), n = 0..9);

gould[n_] := gould[n] = If[n == 0, 1, Sum[Binomial[n, k+1]*gould[k], {k, 0, n-1}]];
T[n_, k_] := (n-1) gould[k-1] + BellB[k];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Nov 08 2023, after first Maple program *)

Given a list T let PS(T) denote the list of partial sums of T. Given two list S and T let [S, T] denote the concatenation of the lists. Further let P[end] denote the last element of the list P. Row n of the triangle T can be computed by the following procedure:
     A = [n], P = [1], R = [1];
     Repeat n times: R = [R, A], P = PS([A, P]), A = [P[end]];
     Return R.

A352685 Array of Aitken-Bell triangles of order m (read by rows) read by ascending antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 1, 1, 2, 2, 1, 1, 3, 3, 2, 1, 1, 4, 4, 3, 3, 2, 1, 5, 5, 4, 5, 5, 2, 1, 6, 6, 5, 7, 8, 5, 3, 1, 7, 7, 6, 9, 11, 8, 7, 4, 1, 8, 8, 7, 11, 14, 11, 11, 10, 6, 1, 9, 9, 8, 13, 17, 14, 15, 16, 15, 6, 1, 10, 10, 9, 15, 20, 17, 19, 22, 24, 15, 8, 1, 11, 11, 10, 17, 23, 20, 23, 28, 33, 24, 20, 11, 1, 12, 12, 11, 19, 26, 23, 27, 34, 42, 33, 32, 27, 15

Offset: 0

Peter Luschny, Mar 29 2022

An Aitken-Bell triangle of order m is defined by T(0, 0) = 1, T(1, 0) = m, T(n, 0) = T(n-1, n-1) and T(n, k) = T(n, k-1) + T(n-1, k-1), for n >= 0 and 0 <= k <= n. The case m = 1 is Aitken's array A011971 with the first column the Bell numbers A000110, case m = 0 is the triangle A046934 with the first column A032347 and case m = 2 is the triangle A046937 with the first column A038561.

			Array starts:
[0] 1, 0,  1,  1,  1,  2,  2,  3,  4,  6,  6,   8,  11,  15, ... A046934
[1] 1, 1,  2,  2,  3,  5,  5,  7, 10, 15, 15,  20,  27,  37, ... A011971
[2] 1, 2,  3,  3,  5,  8,  8, 11, 16, 24, 24,  32,  43,  59, ... A046937
[3] 1, 3,  4,  4,  7, 11, 11, 15, 22, 33, 33,  44,  59,  81, ...
[4] 1, 4,  5,  5,  9, 14, 14, 19, 28, 42, 42,  56,  75, 103, ...
[5] 1, 5,  6,  6, 11, 17, 17, 23, 34, 51, 51,  68,  91, 125, ...
[6] 1, 6,  7,  7, 13, 20, 20, 27, 40, 60, 60,  80, 107, 147, ...
[7] 1, 7,  8,  8, 15, 23, 23, 31, 46, 69, 69,  92, 123, 169, ...
[8] 1, 8,  9,  9, 17, 26, 26, 35, 52, 78, 78, 104, 139, 191, ...
[9] 1, 9, 10, 10, 19, 29, 29, 39, 58, 87, 87, 116, 155, 213, ...

The main diagonals of the triangles are in A352682.

Cf. A000110, A046934, A011971, A046937, A032347, A038561.

function BellTriangle(m, len)
    a = m; P = [1]; T = []
    for n in 1:len
        T = vcat(T, P)
        P = cumsum(vcat(a, P))
        a = P[end]
    end
T end
for n in 0:9 BellTriangle(n, 4) |> println end

alias(PS = ListTools:-PartialSums):
BellTriangle := proc(m, len) local a, k, P, T; a := m; P := [1]; T := [];
for n from 1 to len  do T := [op(T), P]; P := PS([a, op(P)]); a := P[-1] od;
ListTools:-Flatten(T) end:
for n from 0 to 9 do print(BellTriangle(n, 5)) od; # Prints array by rows.

nmax = 13;
row[m_] := row[m] = Module[{T}, T[0, 0] = 1; T[1, 0] = m; T[n_, 0] := T[n, 0] = T[n-1, n-1]; T[n_, k_] := T[n, k] = T[n, k-1] + T[n-1, k-1]; Table[T[n, k], {n, 0, nmax}, {k, 0, n}] // Flatten];
A[n_, k_] := row[n][[k+1]];
Table[A[n-k, k], {n, 0, nmax}, {k, 0, n}] // Flatten (* Jean-François Alcover, Mar 07 2024 *)

Given a list T let PS(T) denote the list of partial sums of T. Given two list S and T let [S, T] denote the concatenation of the lists. Further let P[end] denote the last element of the list P. The Aitken-Bell triangle T of order m with n rows can be computed by the following procedure:
     A = [m], P = [1], T = [];
     Repeat n times: T = [T, P], P = PS([A, P]), A = [P[end]];
     Return T.

cp's OEIS Frontend

A352684 a(n) = A352682(n, n).

Views

Author

Keywords

Crossrefs

Programs

Julia

Formula

A352683 a(n) = A352682(4, n).

Views

Author

Keywords

Crossrefs

Programs

Julia

Formula

A352744 Array read by ascending antidiagonals. Generalized Fibonacci numbers F(n, k) = (psi^k*(phi - n) - phi^k*(psi - n)) / (phi - psi) where phi = (1 + sqrt(5))/2 and psi = (1 - sqrt(5))/2. F(n, k) for n >= 0 and k >= 0.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Julia

Maple

Mathematica

PARI

PARI

Formula

A352680 Array read by ascending antidiagonals. A family of Catalan-like sequences. A(n, k) = [x^k] ((n - 1)*x + 1)*(1 - sqrt(1 - 4*x))/(2*x).

Views

Author

Keywords

Examples

Crossrefs

Programs

Julia

Maple

Mathematica

Formula

A352686 Triangle read by rows. T(n, k) = (n-1)*Gould(k-1) + Bell(k) for n >= 0 and k >= 1, T(n, 0) = 1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Julia

Maple

Mathematica

Formula

A352685 Array of Aitken-Bell triangles of order m (read by rows) read by ascending antidiagonals.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Julia

Maple

Mathematica

Formula

A352744 Array read by ascending antidiagonals. Generalized Fibonacci numbers F(n, k) = (psi^k(phi - n) - phi^k(psi - n)) / (phi - psi) where phi = (1 + sqrt(5))/2 and psi = (1 - sqrt(5))/2. F(n, k) for n >= 0 and k >= 0.

A352680 Array read by ascending antidiagonals. A family of Catalan-like sequences. A(n, k) = [x^k] ((n - 1)x + 1)(1 - sqrt(1 - 4x))/(2x).