A172317 -id:A172317 - cp's OEIS frontend

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

Mats Granvik, Jan 26 2010

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

			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

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.

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.

Cf. (1-((-1)^T(n, k)))/2 = A051731, see formula by Hieronymus Fischer in A022003.

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

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

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

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 *)

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

@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

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]

A172318 9th column of the array A172119.

Original entry on oeis.org

1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1020, 2036, 4064, 8112, 16192, 32320, 64512, 128768, 257025, 513030, 1024024, 2043984, 4079856, 8143520, 16254720, 32444928, 64761088, 129265151, 258017272, 515010520, 1027977056

Offset: 0

Richard Choulet, Jan 31 2010

			a(7)=C(7,7)*2^7=128. a(10)=C(10,10)*2^10-C(2,1)*2^1=1020.

Index entries for linear recurrences with constant coefficients, signature (2,0,0,0,0,0,0,0,-1).

Cf. A172317, A172316, A172119, A001949, A107066.

Partial sums of A079262.

for k from 0 to 20 do for n from 0 to 30 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:k: seq(b(n),n=0..30):od; k:=8:taylor(1/(1-2*z+z^(k+1)),z=0,30);

G.f.: 1/(1-2*z+z^9).
a(n) = sum((-1)^j*binomial(n-k*j,n-(k+1)*j)*2^(n-(k+1)*j),j=0..floor(n/(k+1))) with k=8.
Recurrence relation: a(n+9) = 2*a(8) - a(n).

A172319 10th column of A172119.

Original entry on oeis.org

1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1023, 2044, 4084, 8160, 16304, 32576, 65088, 130048, 259840, 519168, 1037313, 2072582, 4141080, 8274000, 16531696, 33030816, 65996544, 131863040, 263466240, 526413312, 1051789311

Offset: 0

Richard Choulet, Jan 31 2010

Index entries for linear recurrences with constant coefficients, signature (2,0,0,0,0,0,0,0,0,-1).

Cf. A172318, A172317, A172316, A172119, A001949, A107066.

Partial sums of A104144.

for k from 0 to 20 do for n from 0 to 30 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:k: seq(b(n),n=0..30):od;

LinearRecurrence[{2,0,0,0,0,0,0,0,0,-1},{1,2,4,8,16,32,64,128,256,512},40] (* Harvey P. Dale, Sep 22 2020 *)

G.f.: 1/(1-2*z+z^10).

a(n)=sum((-1)^j*binomial(n-k*j,n-(k+1)*j)*2^(n-(k+1)*j),j=0..floor(n/(k+1))). a(n+10)=2*a(n+9)-a(n).

A172320 11th column of A172119.

Original entry on oeis.org

1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2047, 4092, 8180, 16352, 32688, 65344, 130624, 261120, 521984, 1043456, 2085888, 4169729, 8335366, 16662552, 33308752, 66584816, 133104288, 266077952, 531894784, 1063267584

Offset: 0

Richard Choulet, Jan 31 2010

			a(12)=C(12,12)*2^12-C(2,1)*2^1=4092.

Index entries for linear recurrences with constant coefficients, signature (2,0,0,0,0,0,0,0,0,0,-1).

Cf. A172319, A172318, A172317, A172316, A172119, A001949, A107066.

Partial sums of A122265.

k:=10:taylor(1/(1-2*z+z^(k+1)),z=0,30); for k from 0 to 20 do for n from 0 to 30 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:k: seq(b(n),n=0..30):od;

a(n)=sum((-1)^j*binomial(n-k*j,n-(k+1)*j)*2^(n-(k+1)*j),j=0..floor(n/(k+1))) with k=10.
G.f: f(z)=1/(1-2*z+z^(11)).
a(n+11)=2*a(n+10)-a(n).

A234589 Expansion of g.f.: (1+x^6+x^7)/(1-2*x+x^6-x^7-x^8).

Original entry on oeis.org

1, 2, 4, 8, 16, 32, 64, 128, 255, 508, 1012, 2016, 4016, 8000, 15937, 31749, 63249, 126002, 251016, 500064, 996207, 1984602, 3953641, 7876278, 15690791, 31258536, 62271945, 124055559, 247138286, 492338537, 980816202, 1953940937, 3892559256, 7754593434, 15448376086, 30775607480, 61309875581, 122138964964

Offset: 0

N. J. A. Sloane, Jan 01 2014

a(n) is the number of binary words of length n which have no 00010100-matches.

G. C. Greubel, Table of n, a(n) for n = 0..1000
B. K. Miceli, J, Remmel, Minimal Overlapping Embeddings and Exact Matches in Words, PU. M. A., Vol. 23 (2012), No. 3, pp. 291-315.
Index entries for linear recurrences with constant coefficients, signature (2,0,0,0,0,-1,1,1).

Similar to but different from A172317.

Cf. A234590, A234591, A234592.

a:=[1,2,4,8,16,32,64,128];; for n in [9..40] do a[n]:=2*a[n-1]-a[n-6]+a[n-7]+a[n-8]; od; a; # G. C. Greubel, Sep 13 2019

R:=PowerSeriesRing(Integers(), 40); Coefficients(R!( (1+x^6+x^7)/(1-2*x+x^6-x^7-x^8) )); // G. C. Greubel, Sep 13 2019

seq(coeff(series((1+x^6+x^7)/(1-2*x+x^6-x^7-x^8), x, n+1), x, n), n = 0..40); # G. C. Greubel, Sep 13 2019

CoefficientList[Series[(1+x^6+x^7)/(1-2*x+x^6-x^7-x^8), {x,0,40}], x] (* G. C. Greubel, Sep 13 2019 *)
LinearRecurrence[{2,0,0,0,0,-1,1,1},{1,2,4,8,16,32,64,128},40] (* Harvey P. Dale, Aug 31 2023 *)

my(x='x+O('x^40)); Vec((1+x^6+x^7)/(1-2*x+x^6-x^7-x^8)) \\ G. C. Greubel, Sep 13 2019

def A234589_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P((1+x^6+x^7)/(1-2*x+x^6-x^7-x^8)).list()
A234589_list(40) # G. C. Greubel, Sep 13 2019

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A172318 9th column of the array A172119.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A172319 10th column of A172119.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A172320 11th column of A172119.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A234589 Expansion of g.f.: (1+x^6+x^7)/(1-2*x+x^6-x^7-x^8).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage