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

%I #39 Sep 08 2022 08:45:50

%S 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 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 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 Sum the k preceding elements in the same column and add 1 every time.

%C Columns are related to Fibonacci n-step numbers. Are there closed forms for the sequences in the columns?

%C 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 Most of the paper by Dunkel (1925) is a study of the columns of this table. - _Petros Hadjicostas_, Jun 14 2019

%H O. 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 T. Langley, J. Liese, and J. 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Fibonaccin-StepNumber.html">Fibonacci n-Step Number</a>.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Fibonacci_number">Fibonacci number</a>.

%F T(n,0) = 1.

%F T(n,1) = n.

%F T(n,2) = A000071(n+1).

%F T(n,3) = A008937(n-2).

%F 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 Triangle begins:

%e n\k|....0....1....2....3....4....5....6....7....8....9...10

%e ---|-------------------------------------------------------

%e 0..|....1

%e 1..|....1....1

%e 2..|....1....2....1

%e 3..|....1....3....2....1

%e 4..|....1....4....4....2....1

%e 5..|....1....5....7....4....2....1

%e 6..|....1....6...12....8....4....2....1

%e 7..|....1....7...20...15....8....4....2....1

%e 8..|....1....8...33...28...16....8....4....2....1

%e 9..|....1....9...54...52...31...16....8....4....2....1

%e 10.|....1...10...88...96...60...32...16....8....4....2....1

%p 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 := proc(n,k)

%p option remember;

%p if k = 0 then

%p 1;

%p elif k > n then

%p 0;

%p else

%p 1+add(procname(n-k+i,k),i=0..k-1) ;

%p end if;

%p end proc:

%p seq(seq(A172119(n,k),k=0..n),n=0..12) ; # _R. J. Mathar_, Sep 16 2017

%t 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 Table[T[n, k], {n, 0, 12}, {k, 0, n}]//Flatten

%t 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 (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 for(n=1,12, for(k=0,n, print1(T(n,k), ", "))) \\ _G. C. Greubel_, Jul 27 2019

%o (Magma)

%o 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 [[T(n,k): k in [0..n]]: n in [0..12]]; // _G. C. Greubel_, Jul 27 2019

%o (Sage)

%o @CachedFunction

%o def T(n, k):

%o if (k==0 and k==n): return 1

%o elif (k<0 or k>n): return 0

%o else: return 1 + sum(T(n-j, k) for j in (1..k))

%o [[T(n, k) for k in (0..n)] for n in (0..12)] # _G. C. Greubel_, Jul 27 2019

%o (GAP)

%o T:= function(n,k)

%o if k=0 and k=n then return 1;

%o elif k<0 or k>n then return 0;

%o else return 1 + Sum([1..k], j-> T(n-j,k));

%o fi;

%o end;

%o Flat(List([0..12], n-> List([0..n], k-> T(n,k) ))); # _G. C. Greubel_, Jul 27 2019

%Y Cf. A000071, A008937, A144428.

%Y Cf. (1-((-1)^T(n, k)))/2 = A051731, see formula by _Hieronymus Fischer_ in A022003.

%K nonn,tabl

%O 0,5

%A _Mats Granvik_, Jan 26 2010