cp's OEIS Frontend

A172119 Sum the k preceding elements in the same column and add 1 every time.

%I A172119 #46 Mar 28 2025 11:28:59
%S A172119 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,
%T A172119 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,
%U A172119 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
%N A172119 Sum the k preceding elements in the same column and add 1 every time.
%C A172119 Columns are related to Fibonacci n-step numbers. Are there closed forms for the sequences in the columns?
%C A172119 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
%C A172119 Most of the paper by Dunkel (1925) is a study of the columns of this table. - _Petros Hadjicostas_, Jun 14 2019
%H A172119 Erik Bates, Blan Morrison, Mason Rogers, Arianna Serafini, and Anav Sood, <a href="https://arxiv.org/abs/2503.11055">A new combinatorial interpretation of partial sums of m-step Fibonacci numbers</a>, arXiv:2503.11055 [math.CO], 2025. See p. 3.
%H A172119 Otto Dunkel, <a href="http://www.jstor.org/stable/2298801">Solutions of a probability difference equation</a>, Amer. Math. Monthly, 32 (1925), 354-370; see p. 356.
%H A172119 Thomas Langley, Jeffrey Liese, and Jeffrey Remmel, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Langley/langley2.html">Generating Functions for Wilf Equivalence Under Generalized Factor Order</a>, J. Int. Seq. 14 (2011), # 11.4.2.
%H A172119 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Fibonaccin-StepNumber.html">Fibonacci n-Step Number</a>.
%H A172119 Wikipedia, <a href="http://en.wikipedia.org/wiki/Fibonacci_number">Fibonacci number</a>.
%F A172119 T(n,0) = 1.
%F A172119 T(n,1) = n.
%F A172119 T(n,2) = A000071(n+1).
%F A172119 T(n,3) = A008937(n-2).
%F A172119 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]
%e A172119 Triangle begins:
%e A172119 n\k|....0....1....2....3....4....5....6....7....8....9...10
%e A172119 ---|-------------------------------------------------------
%e A172119 0..|....1
%e A172119 1..|....1....1
%e A172119 2..|....1....2....1
%e A172119 3..|....1....3....2....1
%e A172119 4..|....1....4....4....2....1
%e A172119 5..|....1....5....7....4....2....1
%e A172119 6..|....1....6...12....8....4....2....1
%e A172119 7..|....1....7...20...15....8....4....2....1
%e A172119 8..|....1....8...33...28...16....8....4....2....1
%e A172119 9..|....1....9...54...52...31...16....8....4....2....1
%e A172119 10.|....1...10...88...96...60...32...16....8....4....2....1
%p A172119 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
%p A172119 A172119 := proc(n,k)
%p A172119     option remember;
%p A172119     if k = 0 then
%p A172119         1;
%p A172119     elif k > n then
%p A172119         0;
%p A172119     else
%p A172119         1+add(procname(n-k+i,k),i=0..k-1) ;
%p A172119     end if;
%p A172119 end proc:
%p A172119 seq(seq(A172119(n,k),k=0..n),n=0..12) ; # _R. J. Mathar_, Sep 16 2017
%t A172119 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;
%t A172119 Table[T[n, k], {n, 0, 12}, {k, 0, n}]//Flatten
%t A172119 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 *)
%o A172119 (PARI) T(n,k) = if(k<0 || k>n, 0, k==1 && k==n, 1, 1 + sum(j=1,k, T(n-j,k)));
%o A172119 for(n=1,12, for(k=0,n, print1(T(n,k), ", "))) \\ _G. C. Greubel_, Jul 27 2019
%o A172119 (Magma)
%o A172119 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))]]) >;
%o A172119 [[T(n,k): k in [0..n]]: n in [0..12]]; // _G. C. Greubel_, Jul 27 2019
%o A172119 (Sage)
%o A172119 @CachedFunction
%o A172119 def T(n, k):
%o A172119     if (k==0 and k==n): return 1
%o A172119     elif (k<0 or k>n): return 0
%o A172119     else: return 1 + sum(T(n-j, k) for j in (1..k))
%o A172119 [[T(n, k) for k in (0..n)] for n in (0..12)] # _G. C. Greubel_, Jul 27 2019
%o A172119 (GAP)
%o A172119 T:= function(n,k)
%o A172119     if k=0 and k=n then return 1;
%o A172119     elif k<0 or k>n then return 0;
%o A172119     else return 1 + Sum([1..k], j-> T(n-j,k));
%o A172119     fi;
%o A172119   end;
%o A172119 Flat(List([0..12], n-> List([0..n], k-> T(n,k) ))); # _G. C. Greubel_, Jul 27 2019
%Y A172119 Cf. A000071 (col. 3), A008937 (col. 4), A107066 (col. 5), A001949 (col. 6), A172316 (col. 7), A172317 (col. 8), A172318 (col. 9), A172319 (col. 10), A172320 (col. 11), A144428.
%Y A172119 Cf. (1-((-1)^T(n, k)))/2 = A051731, see formula by _Hieronymus Fischer_ in A022003.
%K A172119 nonn,tabl
%O A172119 0,5
%A A172119 _Mats Granvik_, Jan 26 2010