A172119 Sum the k preceding elements in the same column and add 1 every time.
1, 1, 1, 1, 2, 1, 1, 3, 2, 1, 1, 4, 4, 2, 1, 1, 5, 7, 4, 2, 1, 1, 6, 12, 8, 4, 2, 1, 1, 7, 20, 15, 8, 4, 2, 1, 1, 8, 33, 28, 16, 8, 4, 2, 1, 1, 9, 54, 52, 31, 16, 8, 4, 2, 1, 1, 10, 88, 96, 60, 32, 16, 8, 4, 2, 1, 1, 11, 143, 177, 116, 63, 32, 16, 8, 4, 2, 1, 1, 12, 232, 326, 224, 124, 64, 32, 16
Offset: 0
Examples
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
Links
- Erik Bates, Blan Morrison, Mason Rogers, Arianna Serafini, and Anav Sood, A new combinatorial interpretation of partial sums of m-step Fibonacci numbers, arXiv:2503.11055 [math.CO], 2025. See p. 3.
- Otto Dunkel, Solutions of a probability difference equation, Amer. Math. Monthly, 32 (1925), 354-370; see p. 356.
- Thomas Langley, Jeffrey Liese, and Jeffrey 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.
Crossrefs
Programs
-
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 -
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
-
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 *)
-
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
-
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
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]
Comments