|
%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
|
