A172316 -id:A172316 - cp's OEIS frontend

A008937 a(n) = Sum_{k=0..n} T(k) where T(n) are the tribonacci numbers A000073.

0, 1, 2, 4, 8, 15, 28, 52, 96, 177, 326, 600, 1104, 2031, 3736, 6872, 12640, 23249, 42762, 78652, 144664, 266079, 489396, 900140, 1655616, 3045153, 5600910, 10301680, 18947744, 34850335, 64099760, 117897840, 216847936, 398845537, 733591314, 1349284788

Offset: 0

N. J. A. Sloane, Alejandro Teruel (teruel(AT)usb.ve)

a(n+1) is the number of n-bit sequences that avoid 1100. - David Callan, Jul 19 2004 [corrected by Kent E. Morrison, Jan 08 2019]. Also the number of n-bit sequences avoiding one of the patterns 1000, 0011, 1110, ... or any binary string of length 4 without overlap at beginning and end. Strings where it is not true are: 1111, 1010, 1001, ... and their bitwise complements. - Alois P. Heinz, Jan 09 2019
Row sums of Riordan array (1/(1-x), x(1+x+x^2)). - Paul Barry, Feb 16 2005
Diagonal sums of Riordan array (1/(1-x)^2, x(1+x)/(1-x)), A104698.
A shifted version of this sequence can be found in Eqs. (4) and (3) on p. 356 of Dunkel (1925) with r = 3. (Equation (3) follows equation (4) in the paper!) The whole paper is a study of the properties of this and other similar sequences indexed by the parameter r. For r = 2, we get a shifted version of A000071. For r = 4, we get a shifted version of A107066. For r = 5, we get a shifted version of A001949. For r = 6, we get a shifted version of A172316. See also the table in A172119. - Petros Hadjicostas, Jun 14 2019
Officially, to match A000073, this should start with a(0)=a(1)=0, a(2)=1. - N. J. A. Sloane, Sep 12 2020
Numbers with tribonacci representation that is a prefix of 100100100100... . - Jeffrey Shallit, Jul 10 2024

			G.f. = x + 2*x^2 + 4*x^3 + 8*x^4 + 15*x^5 + 28*x^6 + 52*x^7 + 96*x^8 + 177*x^9 + ... [edited by _Petros Hadjicostas_, Jun 12 2019]

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 41.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Isha Agarwal, Matvey Borodin, Aidan Duncan, Kaylee Ji, Tanya Khovanova, Shane Lee, Boyan Litchev, Anshul Rastogi, Garima Rastogi, and Andrew Zhao, From Unequal Chance to a Coin Game Dance: Variants of Penney's Game, arXiv:2006.13002 [math.HO], 2020.
Kassie Archer and Noel Bourne, Pattern avoidance in compositions and powers of permutations, arXiv:2505.05218 [math.CO], 2025. See pp. 6, 9.
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 pp. 356 and 369.
Jia Huang, A coin flip game and generalizations of Fibonacci numbers, arXiv:2501.07463 [math.CO], 2025. See p. 7.
Thomas Langley, Jeffrey Liese, and Jeffrey Remmel, Generating Functions for Wilf Equivalence Under Generalized Factor Order, J. Int. Seq. 14 (2011), Article # 11.4.2.
William Verreault, MacMahon Partition Analysis: a discrete approach to broken stick problems, arXiv:2107.10318 [math.CO], 2021.
Index entries for linear recurrences with constant coefficients, signature (2,0,0,-1).

Partial sums of A000073. Cf. A000213, A018921, A027084, A077908, A209972.
Row sums of A055216.
Column k = 1 of A140997 and second main diagonal of A140994.

a:=[0,1,1];; for n in [4..40] do a[n]:=a[n-1]+a[n-2]+a[n-3]; od; a; # G. C. Greubel, Sep 13 2019

a008937 n = a008937_list !! n
a008937_list = tail $ scanl1 (+) a000073_list
-- Reinhard Zumkeller, Apr 07 2012

[ n eq 1 select 0 else n eq 2 select 1 else n eq 3 select 2 else n eq 4 select 4 else 2*Self(n-1)-Self(n-4): n in [1..40] ]; // Vincenzo Librandi, Aug 21 2011

A008937 := proc(n) option remember; if n <= 3 then 2^n else 2*procname(n-1)-procname(n-4) fi; end;
a:= n-> (Matrix([[1,1,0,0], [1,0,1,0], [1,0,0,0], [1,0,0,1]])^n)[4,1]: seq(a(n), n=0..50); # Alois P. Heinz, Jul 24 2008

CoefficientList[Series[x/(1-2x+x^4), {x, 0, 40}], x]
Accumulate[LinearRecurrence[{1,1,1},{0,1,1},40]] (* Harvey P. Dale, Dec 04 2017 *)
LinearRecurrence[{2, 0, 0, -1},{0, 1, 2, 4},40] (* Ray Chandler, Mar 01 2024 *)

{a(n) = if( n<0, polcoeff( - x^3 / (1 - 2*x^3 + x^4) + x * O(x^-n), -n), polcoeff( x / (1 - 2*x + x^4) + x * O(x^n), n))}; /* Michael Somos, Aug 23 2014 */

a(n) = sum(j=0, n\2, sum(k=0, j, binomial(n-2*j,k+1)*binomial(j,k)*2^k)); \\ Michel Marcus, Sep 08 2017

def A008937_list(prec):
    P = PowerSeriesRing(ZZ, 'x', prec)
    x = P.gen().O(prec)
    return (x/(1-2*x+x^4)).list()
A008937_list(40) # G. C. Greubel, Sep 13 2019

a(n) = A018921(n-2) = A027084(n+1) + 1.
a(n) = (A000073(n+2) + A000073(n+4) - 1)/2.
From Mario Catalani (mario.catalani(AT)unito.it), Aug 09 2002: (Start)
G.f.: x/((1-x)*(1-x-x^2-x^3)).
a(n) = 2*a(n-1) - a(n-4), a(0) = 0, a(1) = 1, a(2) = 2, a(3) = 4. (End)
a(n) = 1 + a(n-1) + a(n-2) + a(n-3). E.g., a(11) = 1 + 600 + 326 + 177 = 1104. - Philippe LALLOUET (philip.lallouet(AT)orange.fr), Oct 29 2007
a(n) = term (4,1) in the 4 X 4 matrix [1,1,0,0; 1,0,1,0; 1,0,0,0; 1,0,0,1]^n. - Alois P. Heinz, Jul 24 2008
a(n) = -A077908(-n-3). - Alois P. Heinz, Jul 24 2008
a(n) = (A000213(n+2) - 1) / 2. - Reinhard Zumkeller, Apr 07 2012
a(n) = Sum_{j=0..floor(n/2)} Sum_{k=0..j} binomial(n-2j,k+1) *binomial(j,k)*2^k. - Tony Foster III, Sep 08 2017
a(n) = Sum_{k=0..floor(n/2)} (n-2*k)*hypergeom([-k,-n+2*k+1], [2], 2). - Peter Luschny, Nov 09 2017
a(n) = 2^(n-1)*hypergeom([1-n/4, 1/4-n/4, 3/4-n/4, 1/2-n/4], [1-n/3, 1/3-n/3, 2/3-n/3], 16/27) for n > 0. - Peter Luschny, Aug 20 2020
a(n-1) = T(n) + T(n-3) + T(n-6) + ... + T(2+((n-2) mod 3)), for n >= 4, where T is A000073(n+1). - Jeffrey Shallit, Dec 24 2020

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

Original entry on oeis.org

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]

A001949 Solutions of a fifth-order probability difference equation.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 2, 4, 8, 16, 32, 63, 124, 244, 480, 944, 1856, 3649, 7174, 14104, 27728, 54512, 107168, 210687, 414200, 814296, 1600864, 3147216, 6187264, 12163841, 23913482, 47012668, 92424472, 181701728, 357216192, 702268543, 1380623604, 2714234540

Offset: 0

N. J. A. Sloane

This sequence is the case r = 5 in the solution to an r-th order probability difference equation that can be found in Eqs. (4) and (3) on p. 356 of Dunkel (1925). (Equation (3) follows equation (4) in the paper!) For r = 2, we get a shifted version of A000071. For r = 3, we get a shifted version of A008937. For r = 4, we get a shifted version of A107066. For r = 6, we get a shifted version of A172316. See also the table in A172119. - Petros Hadjicostas, Jun 15 2019

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
O. Dunkel, Solutions of a probability difference equation, Amer. Math. Monthly, 32 (1925), 354-370; see pp. 356 and 369.
T. Langley, J. Liese, and J. Remmel, Generating Functions for Wilf Equivalence Under Generalized Factor Order, J. Int. Seq. 14 (2011), Article #11.4.2.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Index entries for linear recurrences with constant coefficients, signature (2,0,0,0,0,-1)

Column k = 1 of A141020 (with a different offset) and second main diagonal of A141021 (with no zeros).
Column k = 5 of A172119.
Partial sums of A001591.

A001949:=1/(z-1)/(z**5+z**4+z**3+z**2+z-1); # Simon Plouffe in his 1992 dissertation

t={0,0,0,0,0};Do[AppendTo[t,t[[-5]]+t[[-4]]+t[[-3]]+t[[-2]]+t[[-1]]+1],{n,40}];t (* Vladimir Joseph Stephan Orlovsky, Jan 21 2012 *)
LinearRecurrence[{2,0,0,0,0,-1},{0,0,0,0,0,1},40] (* Harvey P. Dale, Jan 17 2015 *)

a(n):=sum(sum((-1)^j*binomial(n-5*j-5,k-1)*binomial(n-k-5*j-4,j),j,0,(n-k-4)/5),k,1,n-4); /* Vladimir Kruchinin, Oct 19 2011 */

x='x+O('x^99); concat(vector(5), Vec(x^5/((x-1)*(x^5+x^4+x^3+x^2+x-1)))) \\ Altug Alkan, Oct 04 2017

For n >= 6, a(n+1) = 2*a(n) - a(n-5).
G.f.: x^5 / ( (x-1)*(x^5 + x^4 + x^3 + x^2 + x - 1) ).
a(n) = Sum_{k=1..n-4} Sum_{j=0..floor((n-k-4)/5)} (-1)^j*binomial(n-5*j-5, k-1)*binomial(n-k-5*j-4, j). - Vladimir Kruchinin, Oct 19 2011
4*a(n) = A000322(n+1) - 1. - R. J. Mathar, Aug 16 2017
From Petros Hadjicostas, Jun 15 2019: (Start)
a(n) = 1 + a(n-1) + a(n-2) + a(n-3) + a(n-4) + a(n-5) for n >= 5. (See Eq. (4) and the Theorem with r = 5 on p. 356 of Dunkel (1925).)
a(n) = T(n - 5, 5) for n >= 5, where T(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 0 <= k <= n. This is Richard Choulet's formula in A172119.
(End)

Name edited by Petros Hadjicostas, Jun 15 2019

A172317 8th column of A172119.

Original entry on oeis.org

1, 2, 4, 8, 16, 32, 64, 128, 255, 508, 1012, 2016, 4016, 8000, 15936, 31744, 63233, 125958, 250904, 499792, 995568, 1983136, 3950336, 7868928, 15674623, 31223288, 62195672, 123891552, 246787536, 491591936, 979233536

Offset: 0

Richard Choulet, Jan 31 2010

			a(4) = binomial(4,4)*2^4 = 16.
a(9) = binomial(9,9)*2^9 - binomial(2,1)*2^1 = 512 - 4 = 508.

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

Cf. A172316, A001949, A107066, A008937, A172119.

Partial sums of A066178.

k:=7: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;

The generating function is f such that: f(z)=1/(1-2*z+z^8). Recurrence relation: a(n+8)=2*a(n+7)-a(n). General term: a(n) = Sum_{j=0..floor(n/(k+1))} ((-1)^j*binomial(n-k*j,n-(k+1)*j)*2^(n-(k+1)*j)) with k=7.

cp's OEIS Frontend

A008937 a(n) = Sum_{k=0..n} T(k) where T(n) are the tribonacci numbers A000073.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

SageMath

Formula

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

A001949 Solutions of a fifth-order probability difference equation.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Formula

Extensions

A172317 8th column of A172119.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

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