OFFSET
0,5
COMMENTS
Columns are related to Fibonacci n-step numbers. Are there closed forms for the sequences in the columns?
We denote by a(n,k) the number which is in the (n+1)-th row and (k+1)-th-column. With help of the definition, we also have the recurrence relation: a(n+k+1, k) = 2*a(n+k, k) - a(n, k). We see on the main diagonal the numbers 1,2,4, 8, ..., which is clear from the formula for the general term d(n)=2^n. - Richard Choulet, Jan 31 2010
Most of the paper by Dunkel (1925) is a study of the columns of this table. - Petros Hadjicostas, Jun 14 2019
LINKS
O. Dunkel, Solutions of a probability difference equation, Amer. Math. Monthly, 32 (1925), 354-370; see p. 356.
T. Langley, J. Liese, and J. Remmel, Generating Functions for Wilf Equivalence Under Generalized Factor Order, J. Int. Seq. 14 (2011), # 11.4.2.
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.
Wikipedia, Fibonacci number.
FORMULA
T(n,0) = 1.
T(n,1) = n.
T(n,2) = A000071(n+1).
T(n,3) = A008937(n-2).
The general term in the n-th row and k-th column is given by: a(n, k) = Sum_{j=0..floor(n/(k+1))} ((-1)^j binomial(n-k*j,n-(k+1)*j)*2^(n-(k+1)*j)). For example: a(5,3) = binomial(5,5)*2^5 - binomial(2,1)*2^1 = 28. The generating function of the (k+1)-th column satisfies: psi(k)(z)=1/(1-2*z+z^(k+1)) (for k=0 we have the known result psi(0)(z)=1/(1-z)). - Richard Choulet, Jan 31 2010 [By saying "(k+1)-th column" the author actually means "k-th column" for k = 0, 1, 2, ... - Petros Hadjicostas, Jul 26 2019]
EXAMPLE
Triangle begins:
n\k|....0....1....2....3....4....5....6....7....8....9...10
---|-------------------------------------------------------
0..|....1
1..|....1....1
2..|....1....2....1
3..|....1....3....2....1
4..|....1....4....4....2....1
5..|....1....5....7....4....2....1
6..|....1....6...12....8....4....2....1
7..|....1....7...20...15....8....4....2....1
8..|....1....8...33...28...16....8....4....2....1
9..|....1....9...54...52...31...16....8....4....2....1
10.|....1...10...88...96...60...32...16....8....4....2....1
MAPLE
for k from 0 to 20 do for n from 0 to 20 do b(n):=sum((-1)^j*binomial(n-k*j, n-(k+1)*j)*2^(n-(k+1)*j), j=0..floor(n/(k+1))):od: seq(b(n), n=0..20):od; # Richard Choulet, Jan 31 2010
A172119 := proc(n, k)
option remember;
if k = 0 then
1;
elif k > n then
0;
else
1+add(procname(n-k+i, k), i=0..k-1) ;
end if;
end proc:
seq(seq(A172119(n, k), k=0..n), n=0..12) ; # R. J. Mathar, Sep 16 2017
MATHEMATICA
T[_, 0] = 1; T[n_, n_] = 1; T[n_, k_] /; k>n = 0; T[n_, k_] := T[n, k] = Sum[T[n-k+i, k], {i, 0, k-1}] + 1;
Table[T[n, k], {n, 0, 12}, {k, 0, n}]//Flatten
Table[Sum[(-1)^j*2^(n-k-(k+1)*j)*Binomial[n-k-k*j, n-k-(k+1)*j], {j, 0, Floor[(n-k)/(k+1)]}], {n, 0, 12}, {k, 0, n}]//Flatten (* G. C. Greubel, Jul 27 2019 *)
PROG
(PARI) T(n, k) = if(k<0 || k>n, 0, k==1 && k==n, 1, 1 + sum(j=1, k, T(n-j, k)));
for(n=1, 12, for(k=0, n, print1(T(n, k), ", "))) \\ G. C. Greubel, Jul 27 2019
(Magma)
T:= func< n, k | (&+[(-1)^j*2^(n-k-(k+1)*j)*Binomial(n-k-k*j, n-k-(k+1)*j): j in [0..Floor((n-k)/(k+1))]]) >;
[[T(n, k): k in [0..n]]: n in [0..12]]; // G. C. Greubel, Jul 27 2019
(Sage)
@CachedFunction
def T(n, k):
if (k==0 and k==n): return 1
elif (k<0 or k>n): return 0
else: return 1 + sum(T(n-j, k) for j in (1..k))
[[T(n, k) for k in (0..n)] for n in (0..12)] # G. C. Greubel, Jul 27 2019
(GAP)
T:= function(n, k)
if k=0 and k=n then return 1;
elif k<0 or k>n then return 0;
else return 1 + Sum([1..k], j-> T(n-j, k));
fi;
end;
Flat(List([0..12], n-> List([0..n], k-> T(n, k) ))); # G. C. Greubel, Jul 27 2019
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Mats Granvik, Jan 26 2010
STATUS
approved