A005711 -id:A005711 - cp's OEIS frontend

A003269 a(n) = a(n-1) + a(n-4) with a(0) = 0, a(1) = a(2) = a(3) = 1.

0, 1, 1, 1, 1, 2, 3, 4, 5, 7, 10, 14, 19, 26, 36, 50, 69, 95, 131, 181, 250, 345, 476, 657, 907, 1252, 1728, 2385, 3292, 4544, 6272, 8657, 11949, 16493, 22765, 31422, 43371, 59864, 82629, 114051, 157422, 217286, 299915, 413966, 571388, 788674, 1088589, 1502555, 2073943

Offset: 0

N. J. A. Sloane

This comment covers a family of sequences which satisfy a recurrence of the form a(n) = a(n-1) + a(n-m), with a(n) = 1 for n = 0..m-1. The generating function is 1/(1-x-x^m). Also a(n) = Sum_{i=0..n/m} binomial(n-(m-1)*i, i). This family of binomial summations or recurrences gives the number of ways to cover (without overlapping) a linear lattice of n sites with molecules that are m sites wide. Special case: m=1: A000079; m=4: A003269; m=5: A003520; m=6: A005708; m=7: A005709; m=8: A005710.
For this family of sequences, a(n+1) is the number of compositions of n+1 into parts 1 and m. For n>=m, a(n-m+1)is the number of compositions of n in which each part is greater than m or equivalently, in which parts 1 through m are excluded. - Gregory L. Simay, Jul 14 2016
For this family of sequences, let a(m,n) = a(n-1) + a(n-m). Then the number of compositions of n having m as a least summand is a(m, n-m) - a(m+1, n-m-1). - Gregory L. Simay, Jul 14 2016
For n>=3, a(n-3) = number of compositions of n in which each part is >=4. - Milan Janjic, Jun 28 2010
For n>=1, number of compositions of n into parts == 1 (mod 4). Example: a(8)=5 because there are 5 compositions of 8 into parts 1 or 5: (1,1,1,1,1,1,1,1), (1,1,1,5), (1,1,5,1), (1,5,1,1), (5,1,1,1). - Adi Dani, Jun 16 2011
a(n+1) is the number of compositions of n into parts 1 and 4. - Joerg Arndt, Jun 25 2011
The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n>=4, 2*a(n-3) equals the number of 2-colored compositions of n with all parts >= 4, such that no adjacent parts have the same color. - Milan Janjic, Nov 27 2011
Number of permutations satisfying -k<=p(i)-i<=r and p(i)-i not in I, i=1..n, with k=1, r=3, I={1,2}. - Vladimir Baltic, Mar 07 2012
a(n+4) equals the number of binary words of length n having at least 3 zeros between every two successive ones. - Milan Janjic, Feb 07 2015
From Clark Kimberling, Jun 13 2016: (Start)
Let T* be the infinite tree with root 0 generated by these rules: if p is in T*, then p+1 is in T* and x*p is in T*.
Let g(n) be the set of nodes in the n-th generation, so that g(0) = {0}, g(1) = {1}, g(2) = {2,x}, g(3) = {3, 2*x, x+1, x^2}, etc.
Let T(r) be the tree obtained by substituting r for x.
If N is a positive integer such that r = N^(1/4) is not an integer, then the number of (not necessarily distinct) integers in g(n) is A003269(n), for n > = 1. See A274142. (End)

			G.f.: x + x^2 + x^3 + x^4 + 2*x^5 + 3*x^6 + 4*x^7 + 5*x^8 + 7*x^9 + 10*x^10 + ...
The number of compositions of 12 having 4 as a least summand is a(4, 12 -4 + 1) - a(5, 12 - 5 + 1) = A003269(9) - A003520(8) = 7-4 = 3. The compositions are (84), (48) and (444). - _Gregory L. Simay_, Jul 14 2016

A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 120.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..501
Jarib R. Acosta, Yadira Caicedo, Juan P. Poveda, José L. Ramírez, and Mark Shattuck, Some New Restricted n-Color Composition Functions, J. Int. Seq., Vol. 22 (2019), Article 19.6.4.
Mudit Aggarwal and Samrith Ram, Generating Functions for Straight Polyomino Tilings of Narrow Rectangles, J. Int. Seq., Vol. 26 (2023), Article 23.1.4.
Michael A. Allen, On a Two-Parameter Family of Generalizations of Pascal's Triangle, arXiv:2209.01377 [math.CO], 2022.
Michael A. Allen, Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings, arXiv:2409.00624 [math.CO], 2024. See pp. 18, 22.
J.-P. Allouche and T. Johnson, Narayana's cows and delayed morphisms, in G. Assayag, M. Chemillier, and C. Eloy, Troisièmes Journées d'Informatique Musicale, JIM '96, Île de Tatihou, France, 1996, pp. 2-7. [The hal link does not always work. - _N. J. A. Sloane_, Feb 19 2025]
J.-P. Allouche and T. Johnson, Narayana's cows and delayed morphisms, in G. Assayag, M. Chemillier, and C. Eloy, Troisièmes Journées d'Informatique Musicale, JIM '96, Île de Tatihou, France, 1996, pp. 2-7. [Local copy with annotations and a correction from _N. J. A. Sloane_, Feb 19 2025]
Peter G. Anderson, More Properties of the Zeckendorf Array, Fib. Quart. 52-5 (2014), 15-21. With 2 more initial zeros.
Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (2010), 119-135.
D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 9.
Bruce M. Boman, Geometric Capitulum Patterns Based on Fibonacci p-Proportions, Fibonacci Quart. 58 (2020), no. 5, 91-102.
Russ Chamberlain, Sam Ginsburg and Chi Zhang, Generating Functions and Wilf-equivalence on Theta_k-embeddings, University of Wisconsin, April 2012.
P. Chinn and S. Heubach, (1, k)-compositions, Congr. Numer. 164 (2003), 183-194. [Local copy]
Hùng Việt Chu, Nurettin Irmak, Steven J. Miller, László Szalay, and Sindy Xin Zhang, Schreier Multisets and the s-step Fibonacci Sequences, arXiv:2304.05409 [math.CO], 2023. See also Integers (2024) Vol. 24A, Art. No. A7, p. 3.
Adi Dani, Compositions of natural numbers over arithmetic progressions
E. Di Cera and Y. Kong, Theory of multivalent binding in one and two-dimensional lattices, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.
Larry Ericksen and Peter G. Anderson, Patterns in differences between rows in k-Zeckendorf arrays, The Fibonacci Quarterly, Vol. 50, February 2012.
I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5.
R. K. Guy, Letter to N. J. A. Sloane with attachment, 1988
V. C. Harris and C. C. Styles, A generalization of Fibonacci numbers, Fib. Quart. 2 (1964) 277-289, sequence u(n,3,1).
J. Hermes, Anzahl der Zerlegungen einer ganzen rationalen Zahl in Summanden, Math. Ann., 45 (1894), 371-380.
Brian Hopkins and Hua Wang, Restricted Color n-color Compositions, arXiv:2003.05291 [math.CO], 2020.
Jia Huang, Compositions with restricted parts, arXiv:1812.11010 [math.CO], 2018.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 377
Milan Janjic, Binomial Coefficients and Enumeration of Restricted Words, Journal of Integer Sequences, 2016, Vol 19, #16.7.3.
Sergey Kirgizov, Q-bonacci words and numbers, arXiv:2201.00782 [math.CO], 2022.
S. Kitaev, Independent sets on path-schemes, JIS 9 (2006) # 06.2.2 G(x) for M={1,2,3} gives seq. shifted 4 places left
R. J. Mathar, Paving rectangular regions with rectangular tiles: Tatami and Non-Tatami Tilings, arXiv:1311.6135 [math.CO], 2013, Table 17.
R. J. Mathar, Tilings of rectangular regions by rectangular tiles: Counts derived from transfer matrices, arXiv:1406.7788 [math.CO] (2014), eq. (23).
Flaviano Morone, Ian Leifer, and Hernán A. Makse, Fibration symmetries uncover the building blocks of biological networks, Proceedings of the National Academy of Sciences (2020) Vol. 117, No. 15, 8306-8314.
Augustine O. Munagi, Euler-type identities for integer compositions via zig-zag graphs, Integers 12 (2012), Paper No. A60, 10 pp.
Augustine O. Munagi, Integer Compositions and Higher-Order Conjugation, J. Int. Seq., Vol. 21 (2018), Article 18.8.5.
Denis Neiter and Amsha Proag, Links Between Sums Over Paths in Bernoulli's Triangles and the Fibonacci Numbers, Journal of Integer Sequences, Vol. 19 (2016), #16.8.3.
Djamila Oudrar and Maurice Pouzet, Ordered structures with no finite monomorphic decomposition. Application to the profile of hereditary classes, arXiv:2312.05913 [math.CO], 2023. See p. 18.
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
E. Wilson, The Scales of Mt. Meru
Dominika Závacká, Cristina Dalfó, and Miquel Angel Fiol, Integer sequences from k-iterated line digraphs, CEUR: Proc. 24th Conf. Info. Tech. - Appl. and Theory (ITAT 2024) Vol 3792, 156-161. See p. 161, Table 2.
Index entries for two-way infinite sequences
Index entries for linear recurrences with constant coefficients, signature (1,0,0,1).

Cf. A000045, A000079, A000930, A003520, A005708, A005709, A005710, A005711, A017898.
Cf. A048718, A072827, A072850, A072851, A072852, A072853, A072854, A072855, A072856.
Cf. A079955 - A080014.
See A017898 for an essentially identical sequence.
Row sums of A180184.

a003269 n = a003269_list !! n
a003269_list = 0 : 1 : 1 : 1 : zipWith (+) a003269_list
                                          (drop 3 a003269_list)
-- Reinhard Zumkeller, Feb 27 2011

I:=[0,1,1,1]; [n le 4 select I[n] else Self(n-1) + Self(n-4) :n in [1..50]]; // Marius A. Burtea, Sep 13 2019

with(combstruct): SeqSetU := [S, {S=Sequence(U), U=Set(Z, card > 3)}, unlabeled]: seq(count(SeqSetU, size=j), j=4..51);
seq(add(binomial(n-3*k,k),k=0..floor(n/3)),n=0..47); # Zerinvary Lajos, Apr 03 2007
A003269:=z/(1-z-z**4); # Simon Plouffe in his 1992 dissertation
ZL:=[S, {a = Atom, b = Atom, S = Prod(X,Sequence(Prod(X,b))), X = Sequence(b,card >= 3)}, unlabelled]: seq(combstruct[count](ZL, size=n), n=3..50); # Zerinvary Lajos, Mar 26 2008
M:= Matrix(4, (i,j)-> if j=1 then [1,0,0,1][i] elif (i=j-1) then 1 else 0 fi); a:= n-> (M^(n))[1,2]; seq(a(n), n=0..48); # Alois P. Heinz, Jul 27 2008

a[0]= 0; a[1]= a[2]= a[3]= 1; a[n_]:= a[n]= a[n-1] + a[n-4]; Table[a[n], {n,0,50}]
CoefficientList[Series[x/(1-x-x^4), {x,0,50}], x] (* Zerinvary Lajos, Mar 29 2007 *)
Table[Sum[Binomial[n-3*i-1,i], {i,0,(n-1)/3}], {n,0,50}]
LinearRecurrence[{1,0,0,1}, {0,1,1,1}, 50] (* Robert G. Wilson v, Jul 12 2014 *)
nxt[{a_,b_,c_,d_}]:={b,c,d,a+d}; NestList[nxt,{0,1,1,1},50][[;;,1]] (* Harvey P. Dale, May 27 2024 *)

{a(n) = polcoeff( if( n<0, (1 + x^3) / (1 + x^3 - x^4), 1 / (1 - x - x^4)) + x * O(x^abs(n)), abs(n))} /* Michael Somos, Jul 12 2003 */

@CachedFunction
def a(n): return ((n+2)//3) if (n<4) else a(n-1) + a(n-4) # a = A003269
[a(n) for n in (0..50)] # G. C. Greubel, Jul 25 2022

G.f.: x/(1-x-x^4).
G.f.: -1 + 1/(1-Sum_{k>=0} x^(4*k+1)).
a(n) = a(n-3) + a(n-4) + a(n-5) + a(n-6) for n>4.
a(n) = floor(d*c^n + 1/2) where c is the positive real root of -x^4+x^3+1 and d is the positive real root of 283*x^4-18*x^2-8*x-1 (c=1.38027756909761411... and d=0.3966506381592033124...). - Benoit Cloitre, Nov 30 2002
Equivalently, a(n) = floor(c^(n+3)/(c^4+3) + 1/2) with c as defined above (see A086106). - Greg Dresden and Shuer Jiang, Aug 31 2019
a(n) = term (1,2) in the 4 X 4 matrix [1,1,0,0; 0,0,1,0; 0,0,0,1; 1,0,0,0]^n. - Alois P. Heinz, Jul 27 2008
From Paul Barry, Oct 20 2009: (Start)
a(n+1) = Sum_{k=0..n} C((n+3*k)/4,k)*((1+(-1)^(n-k))/2 + cos(Pi*n/2))/2;
a(n+1) = Sum_{k=0..n} C(k,floor((n-k)/3))(2*cos(2*Pi*(n-k)/3)+1)/3. (End)
a(n) = Sum_{j=0..(n-1)/3} binomial(n-1-3*j,j) (cf. A180184). - Vladimir Kruchinin, May 23 2011
A017817(n) = a(-4 - n) * (-1)^n. - Michael Somos, Jul 12 2003
G.f.: Q(0)*x/2, where Q(k) = 1 + 1/(1 - x*(2*k+1 + x^3)/( x*(2*k+2 + x^3) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 29 2013
Appears a(n) = hypergeometric([1/4-n/4,1/2-n/4,3/4-n/4,1-n/4], [1/3-n/3,2/3-n/3,1-n/3], -4^4/3^3) for n>=10. - Peter Luschny, Sep 18 2014

Additional comments from Yong Kong (ykong(AT)curagen.com), Dec 16 2000

Initial 0 prepended by N. J. A. Sloane, Apr 09 2008

A003520 a(n) = a(n-1) + a(n-5); a(0) = ... = a(4) = 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 8, 11, 15, 20, 26, 34, 45, 60, 80, 106, 140, 185, 245, 325, 431, 571, 756, 1001, 1326, 1757, 2328, 3084, 4085, 5411, 7168, 9496, 12580, 16665, 22076, 29244, 38740, 51320, 67985, 90061, 119305, 158045, 209365, 277350, 367411, 486716, 644761

Offset: 0

N. J. A. Sloane

This comment covers a family of sequences which satisfy a recurrence of the form a(n) = a(n-1) + a(n-m), with a(n) = 1 for n = 0..m-1. The generating function is 1/(1-x-x^m). Also a(n) = Sum_{i=0..n/m} binomial(n-(m-1)*i, i). This family of binomial summations or recurrences gives the number of ways to cover (without overlapping) a linear lattice of n sites with molecules that are m sites wide. Special case: m=1: A000079; m=4: A003269; m=5: A003520; m=6: A005708; m=7: A005709; m=8: A005710.
Also counts ordered partitions such that no part is less than 5. For example, a(12) = a(11) + a(7) where a(7) counts 11,6+5 and 5+6 and a(11) counts 15,10+5, 9+6,8+7,7+8,6+9,5+10 and 5+5+5. Thus a(12) = 3 + 8 = 11. a(12) counts 16,11+5,10+6,9+7,8+8,7+9,6+10 and 6+5+5 but also 5+11,5+6+5 and 5+5+6. Similar results hold for the other sequences formed by a(n) = a(n-1) + a(n-k). - Alford Arnold, Aug 06 2003
Number of compositions of n into parts 1 and 5. - Joerg Arndt, Jun 25 2011
The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n>=5, 2*a(n-5) equals the number of 2-colored compositions of n with all parts >= 5, such that no adjacent parts have the same color. - Milan Janjic, Nov 27 2011
a(n+4) equals the number of binary words of length n having at least 4 zeros between every two successive ones. - Milan Janjic, Feb 07 2015
Number of tilings of a 5 X n rectangle with 5 X 1 pentominoes. - M. Poyraz Torcuk, Mar 26 2022

A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 119.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=0..500
Jarib R. Acosta, Yadira Caicedo, Juan P. Poveda, José L. Ramírez, and Mark Shattuck, Some New Restricted n-Color Composition Functions, J. Int. Seq., Vol. 22 (2019), Article 19.6.4.
Mudit Aggarwal and Samrith Ram, Generating Functions for Straight Polyomino Tilings of Narrow Rectangles, J. Int. Seq., Vol. 26 (2023), Article 23.1.4.
Michael A. Allen, On a Two-Parameter Family of Generalizations of Pascal's Triangle, arXiv:2209.01377 [math.CO], 2022.
Michael A. Allen, Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings, arXiv:2409.00624 [math.CO], 2024. See pp. 18, 22.
Roland Bacher, On the number of perfect lattices, arXiv:1704.02234 [math.NT], 2017. See Section 6.
D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 9.
Bruce M. Boman, Geometric Capitulum Patterns Based on Fibonacci p-Proportions, Fibonacci Quart. 58 (2020), no. 5, 91-102.
Bruce M. Boman, Thien-Nam Dinh, Keith Decker, Brooks Emerick, Christopher Raymond, and Gilberto Schleinger, Why do Fibonacci numbers appear in patterns of growth in nature?, in Fibonacci Quarterly, 55(5): pp 30-41, (2017).
P. Chinn and S. Heubach, (1, k)-compositions, Congr. Numer. 164 (2003), 183-194. [Local copy]
E. Di Cera and Y. Kong, Theory of multivalent binding in one and two-dimensional lattices, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.
I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5
R. K. Guy, Letter to N. J. A. Sloane with attachment, 1988
V. C. Harris and C. C. Styles, A generalization of Fibonacci numbers, Fib. Quart. 2 (1964) 277-289, sequence u(n,4,1).
V. E. Hoggatt, Jr., 7-page typed letter to N. J. A. Sloane with suggestions for new sequences, circa 1977.
Brian Hopkins and Hua Wang, Restricted Color n-color Compositions, arXiv:2003.05291 [math.CO], 2020.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 378
S. Kitaev, Independent sets on path-schemes, JIS 9 (2006) # 06.2.2 G(x) for M={1,2,3,4} gives seq. shifted 4 places left
T. G. Lewis, B. J. Smith and M. Z. Smith, Fibonacci sequences and money management, Fib. Quart., 14 (1976), 37-41.
Sergey Kirgizov, Q-bonacci words and numbers, arXiv:2201.00782 [math.CO], 2022.
R. J. Mathar, Paving rectangular regions with rectangular tiles: Tatami and Non-Tatami Tilings, arXiv:1311.6135 [math.CO], 2013, Table 33.
R. J. Mathar, Tiling n x m rectangles with 1 x 1 and s x s squares, arXiv:1609.03964 [math.CO] (2016), Section 4.4.
Augustine O. Munagi, Integer Compositions and Higher-Order Conjugation, J. Int. Seq., Vol. 21 (2018), Article 18.8.5.
Denis Neiter and Amsha Proag, Links Between Sums Over Paths in Bernoulli's Triangles and the Fibonacci Numbers, Journal of Integer Sequences, Vol. 19 (2016), Article 16.8.3.
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
E. Wilson, The Scales of Mt. Meru
Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,1)

Apart from initial terms, same as A017899.

Cf. A000045, A000079, A000930, A003269, A005708, A005709, A005710, A005711.

a[0]:=1:a[1]:=1:a[2]:=1:a[3]:=1:a[4]:=1:for n from 5 to 60 do a[n]:=a[n-1]+a[n-5] od:seq(a[n],n=0..60);
with(combstruct): SeqSetU := [S, {S=Sequence(U), U=Set(Z, card > 4)}, unlabeled]: seq(count(SeqSetU, size=j), j=5..55); # Zerinvary Lajos, Oct 10 2006
A003520:=-1/(z**3+z**2-1)/(z**2-z+1); # Simon Plouffe in his 1992 dissertation
ZL:=[S, {a = Atom, b = Atom, S = Prod(X,Sequence(Prod(X,b))), X = Sequence(b,card >= 4)}, unlabelled]: seq(combstruct[count](ZL, size=n), n=4..54); # Zerinvary Lajos, Mar 26 2008
M := Matrix(5, (i,j)-> if j=1 then [1, 0, 0, 0, 1][i] elif (i=j-1) then 1 else 0 fi); a:= n-> (M^(n))[1,1]: seq(a(n), n=0..50); # Alois P. Heinz, Jul 27 2008

a[0] = a[1] = a[2] = a[3] = a[4] = 1; a[n_] := a[n] = a[n - 1] + a[n - 5]; Table[ a[n], {n, 0, 49}] (* Robert G. Wilson v, Dec 09 2004 *)
CoefficientList[Series[1/(1 - x - x^5), {x, 0, 51}], x] (* Zerinvary Lajos, Mar 29 2007 *)
LinearRecurrence[{1, 0, 0, 0, 1}, {1, 1, 1, 1, 1}, 80] (* Vladimir Joseph Stephan Orlovsky, Feb 16 2012 *)
nxt[{a_,b_,c_,d_,e_}]:={b,c,d,e,e+a}; NestList[nxt,{1,1,1,1,1},50][[;;,1]] (* Harvey P. Dale, Sep 27 2023 *)

a(n):=sum(binomial(n-1+(-4)*j,j),j,0,(n-1)/4); /* Vladimir Kruchinin, May 23 2011 */

my(x='x+O('x^66)); Vec(x/(1-(x+x^5))) /* Joerg Arndt, Jun 25 2011 */

G.f.: 1/(1-x-x^5) = 1/((1-x+x^2)(1-x^2-x^3)).
a(n) = Sum_{j=0..(n-1)/4} binomial(n-1+(-4)*j,j).
For n>5, a(n) = floor( d*c^n + 1/2) where c is the positive real root of x^5-x^4-1 and d is the positive real root of 161*x^3-23*x^2-12*x-1 ( c=1.32471795724474602... and d=0.3811571478326847...) - Benoit Cloitre, Nov 30 2002
a(n) = term (1,1) in the 5 X 5 matrix [1,1,0,0,0; 0,0,1,0,0; 0,0,0,1,0; 0,0,0,0,1; 1,0,0,0,0]^n. - Alois P. Heinz, Jul 27 2008
For positive integers n and k such that k <= n <= 5*k, and 4 divides n-k, define c(n,k) = binomial(k,(n-k)/4), and c(n,k)=0, otherwise. Then, for n >= 1,  a(n) = sum(c(n,k), k=1..n). - Milan Janjic, Dec 09 2011
Apparently a(n) = hypergeometric([-1/5*n, 1/5-1/5*n, 2/5-1/5*n, 3/5-1/5*n, 4/5-1/5*n], [-1/4*n, 1/4-1/4*n, 1/2-1/4*n, 3/4-1/4*n], -5^5/4^4) for n>=16. - Peter Luschny, Sep 18 2014
7*a(n) = A117373(n+4) +5*b(n) +4*b(n-1) +b(n-2) where b(n) = A182097(n). - R. J. Mathar, Aug 07 2017

Additional comments from Yong Kong (ykong(AT)curagen.com), Dec 16 2000

A005709 a(n) = a(n-1) + a(n-7), with a(i) = 1 for i = 0..6.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 10, 13, 17, 22, 28, 35, 43, 53, 66, 83, 105, 133, 168, 211, 264, 330, 413, 518, 651, 819, 1030, 1294, 1624, 2037, 2555, 3206, 4025, 5055, 6349, 7973, 10010, 12565, 15771, 19796, 24851

Offset: 0

N. J. A. Sloane

This comment covers a family of sequences which satisfy a recurrence of the form a(n) = a(n-1) + a(n-m), with a(n) = 1 for n = 0...m-1. The generating function is 1/(1-x-x^m). Also a(n) = Sum_{i=0..n/m} binomial(n-(m-1)*i, i). This family of binomial summations or recurrences gives the number of ways to cover (without overlapping) a linear lattice of n sites with molecules that are m sites wide. Special case: m=1: A000079; m=4: A003269; m=5: A003520; m=6: A005708; m=7: A005709; m=8: A005710.
For n >= 7, a(n-7) is the number of compositions of n in which each part is >=7. - Milan Janjic, Jun 28 2010
Number of compositions of n into parts 1 and 7. - Joerg Arndt, Jun 24 2011
a(n+6) is the number of binary words of length n having at least 6 zeros between every two successive ones. - Milan Janjic, Feb 09 2015
Number of tilings of a 7 X n rectangle with 7 X 1 heptominoes. - M. Poyraz Torcuk, Feb 26 2022

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

T. D. Noe, Table of n, a(n) for n=0..500
Mudit Aggarwal and Samrith Ram, Generating Functions for Straight Polyomino Tilings of Narrow Rectangles, J. Int. Seq., Vol. 26 (2023), Article 23.1.4.
Michael A. Allen, On a Two-Parameter Family of Generalizations of Pascal's Triangle, arXiv:2209.01377 [math.CO], 2022.
Michael A. Allen, Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings, arXiv:2409.00624 [math.CO], 2024. See p. 18.
D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 10.
P. Chinn and S. Heubach, (1, k)-compositions, Congr. Numer. 164 (2003), 183-194. [Local copy]
E. Di Cera and Y. Kong, Theory of multivalent binding in one and two-dimensional lattices, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.
I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5.
R. K. Guy, Letter to N. J. A. Sloane with attachment, 1988
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 380
S. Kitaev, Independent sets on path-schemes, JIS 9 (2006) # 06.2.2 G(x) for M={1,2,3,4,5,6} gives seq. shifted 6 places left
R. J. Mathar, Tiling n x m rectangles with 1 x 1 and s x s squares, arXiv:1609.03964 [math.CO], 2016, Section 4.6.
Augustine O. Munagi, Integer Compositions and Higher-Order Conjugation, J. Int. Seq., Vol. 21 (2018), Article 18.8.5.
David Newman, Problem E3274, Amer. Math. Monthly, 95 (1988), 555.
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 (1,0,0,0,0,0,1).

Cf. A000045, A000079, A000930, A003269, A003520, A005708, A005710, A005711.

A005709 := proc(n) option remember; if n <=6 then 1; else A005709(n-1)+A005709(n-7); fi; end;
with(combstruct): SeqSetU := [S, {S=Sequence(U), U=Set(Z, card > 6)}, unlabeled]: seq(count(SeqSetU, size=j), j=7..55); # Zerinvary Lajos, Oct 10 2006
ZL:=[S, {a = Atom, b = Atom, S = Prod(X,Sequence(Prod(X,b))), X = Sequence(b,card >= 6)}, unlabelled]: seq(combstruct[count](ZL, size=n), n=6..54); # Zerinvary Lajos, Mar 26 2008
M:= Matrix(7, (i,j)-> if j=1 and member(i,[1,7]) then 1 elif (i=j-1) then 1 else 0 fi); a:= n-> (M^(n))[1,1]; seq(a(n), n=0..50); # Alois P. Heinz, Jul 27 2008

f[ n_Integer ] := f[ n ]=If[ n>7, f[ n-1 ]+f[ n-7 ], 1 ]
Table[Sum[Binomial[n-6*i, i], {i, 0, n/7}], {n, 0, 45}] (* Adi Dani, Jun 25 2011 *)
LinearRecurrence[{1, 0, 0, 0, 0, 0, 1}, {1, 1, 1, 1, 1, 1, 1}, 80] (* Vladimir Joseph Stephan Orlovsky, Feb 16 2012 *)

x='x+O('x^66); Vec(1/(1-(x+x^7))) /* Joerg Arndt, Jun 25 2011 */

G.f.: 1/(1-x-x^7). - Simon Plouffe in his 1992 dissertation.
For positive integers n and k such that k <= n <= 7*k, and 6 divides n-k, define c(n,k) = binomial(k,(n-k)/6), and c(n,k)=0, otherwise. Then, for n >= 1, a(n) = Sum_{k=1..n} c(n,k). - Milan Janjic, Dec 09 2011
Apparently a(n) = hypergeometric([1/7-n/7, 2/7-n/7, 3/7-n/7, 4/7-n/7, 5/7-n/7, 6/7-n/7, -n/7], [1/6-n/6, 1/3-n/6, 1/2-n/6, 2/3-n/6, 5/6-n/6, -n/6], -7^7/6^6) for n >= 36. - Peter Luschny, Sep 19 2014

Additional comments from Yong Kong (ykong(AT)curagen.com), Dec 16 2000

A005708 a(n) = a(n-1) + a(n-6), with a(i) = 1 for i = 0..5.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 9, 12, 16, 21, 27, 34, 43, 55, 71, 92, 119, 153, 196, 251, 322, 414, 533, 686, 882, 1133, 1455, 1869, 2402, 3088, 3970, 5103, 6558, 8427, 10829, 13917, 17887, 22990, 29548, 37975, 48804, 62721, 80608, 103598, 133146, 171121, 219925, 282646

Offset: 0

N. J. A. Sloane

This comment covers a family of sequences which satisfy a recurrence of the form a(n) = a(n-1) + a(n-m), with a(n) = 1 for n = 0...m-1. The generating function is 1/(1-x-x^m). Also a(n) = sum_{i=0..n/m} binomial(n-(m-1)*i, i). This family of binomial summations or recurrences gives the number of ways to cover (without overlapping) a linear lattice of n sites with molecules that are m sites wide. Special case: m=1: A000079; m=4: A003269; m=5: A003520; m=6: A005708; m=7: A005709; m=8: A005710.
For n>=6, a(n-6) = number of compositions of n in which each part is >=6. - Milan Janjic, Jun 28 2010
Number of compositions of n into parts 1 and 6. - Joerg Arndt, Jun 24 2011
The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n>=6, 2*a(n-6) equals the number of 2-colored compositions of n with all parts >=6, such that no adjacent parts have the same color. - Milan Janjic, Nov 27 2011
a(n+5) equals the number of binary words of length n having at least 5 zeros between every two successive ones. - Milan Janjic, Feb 07 2015
Number of tilings of a 6 X n rectangle with 6 X 1 hexominoes. - M. Poyraz Torcuk, Mar 26 2022

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

T. D. Noe, Table of n, a(n) for n=0..500
Jarib R. Acosta, Yadira Caicedo, Juan P. Poveda, José L. Ramírez, and Mark Shattuck, Some New Restricted n-Color Composition Functions, J. Int. Seq., Vol. 22 (2019), Article 19.6.4.
Mudit Aggarwal and Samrith Ram, Generating Functions for Straight Polyomino Tilings of Narrow Rectangles, J. Int. Seq., Vol. 26 (2023), Article 23.1.4.
Michael A. Allen, On a Two-Parameter Family of Generalizations of Pascal's Triangle, arXiv:2209.01377 [math.CO], 2022.
Michael A. Allen, Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings, arXiv:2409.00624 [math.CO], 2024. See pp. 18, 22.
D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 10.
Bruce M. Boman, Thien-Nam Dinh, Keith Decker, Brooks Emerick, Christopher Raymond, and Gilberto Schleinger, Why do Fibonacci numbers appear in patterns of growth in nature?, in Fibonacci Quarterly, 55(5): pp 30-41, (2017).
P. Chinn and S. Heubach, (1, k)-compositions, Congr. Numer. 164 (2003), 183-194. [Local copy]
E. Di Cera and Y. Kong, Theory of multivalent binding in one and two-dimensional lattices, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.
I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5.
R. K. Guy, Letter to N. J. A. Sloane with attachment, 1988
V. C. Harris and C. C. Styles, A generalization of Fibonacci numbers, Fib. Quart. 2 (1964) 277-289, sequence u(n,5,1).
V. E. Hoggatt, Jr., 7-page typed letter to N. J. A. Sloane with suggestions for new sequences, circa 1977.
Sergey Kirgizov, Q-bonacci words and numbers, arXiv:2201.00782 [math.CO], 2022.
S. Kitaev, Independent sets on path-schemes, JIS 9 (2006) # 06.2.2 G(x) for M={1,2,3,4,5} gives seq. shifted 5 places left
D. Kleitman, Solution to Problem E3274, Amer. Math. Monthly, 98 (1991), 958-959.
R. J. Mathar, Tiling n x m rectangles with 1 x 1 and s x s squares, arXiv:1609.03964 [math.CO] (2016), Section 4.5
Augustine O. Munagi, Integer Compositions and Higher-Order Conjugation, J. Int. Seq., Vol. 21 (2018), Article 18.8.5.
D. Newman, Problem E3274, Amer. Math. Monthly, 95 (1988), 555.
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
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 379
Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,0,1).

Cf. A000045, A000079, A000930, A003269, A003520, A005709, A005710, A005711.

with(combstruct): SeqSetU := [S, {S=Sequence(U), U=Set(Z, card > 5)}, unlabeled]: seq(count(SeqSetU, size=j), j=6..59); # Zerinvary Lajos, Oct 10 2006
ZL:=[S, {a = Atom, b = Atom, S = Prod(X,Sequence(Prod(X,b))), X = Sequence(b,card >= 5)}, unlabelled]: seq(combstruct[count](ZL, size=n), n=5..58); # Zerinvary Lajos, Mar 26 2008
M := Matrix(6, (i,j)-> if j=1 and member(i,[1,6]) then 1 elif (i=j-1) then 1 else 0 fi); a:= n-> (M^(n))[1,1]; seq(a(n), n=0..60); # Alois P. Heinz, Jul 27 2008

LinearRecurrence[{1, 0, 0, 0, 0, 1}, {1, 1, 1, 1, 1, 1}, 80] (* Vladimir Joseph Stephan Orlovsky, Feb 16 2012 *)

x='x+O('x^66); Vec(x/(1-(x+x^6))) /* Joerg Arndt, Jun 25 2011 */

G.f.: 1/(1-x-x^6). - Simon Plouffe in his 1992 dissertation
a(n) = term (1,1) in the 6 X 6 matrix [1,1,0,0,0,0; 0,0,1,0,0,0; 0,0,0,1,0,0; 0,0,0,0,1,0; 0,0,0,0,0,1; 1,0,0,0,0,0]^n. - Alois P. Heinz, Jul 27 2008
For positive integers n and k such that k <= n <= 6*k and 5 divides n-k, define c(n,k) = binomial(k,(n-k)/5), and c(n,k)=0, otherwise. Then, for n>= 1, a(n) = sum_{k=1..n} c(n,k). - Milan Janjic, Dec 09 2011
Apparently a(n) = hypergeometric([1/6-n/6, 1/3-n/6, 1/2-n/6, 2/3-n/6, 5/6-n/6, -n/6], [1/5-n/5, 2/5-n/5, 3/5- n/5, 4/5-n/5, -n/5], -6^6/5^5) for n>=25. - Peter Luschny, Sep 19 2014

Additional comments from Yong Kong (ykong(AT)curagen.com), Dec 16 2000

A005710 a(n) = a(n-1) + a(n-8), with a(i) = 1 for i = 0..7.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 14, 18, 23, 29, 36, 44, 53, 64, 78, 96, 119, 148, 184, 228, 281, 345, 423, 519, 638, 786, 970, 1198, 1479, 1824, 2247, 2766, 3404, 4190, 5160, 6358, 7837, 9661, 11908, 14674, 18078, 22268, 27428, 33786, 41623

Offset: 0

N. J. A. Sloane

This comment covers a family of sequences which satisfy a recurrence of the form a(n) = a(n-1) + a(n-m), with a(n) = 1 for n = 0...m-1. The generating function is 1/(1-x-x^m). Also a(n) = Sum_{i=0..n/m} binomial(n-(m-1)*i, i). This family of binomial summations or recurrences gives the number of ways to cover (without overlapping) a linear lattice of n sites with molecules that are m sites wide. Special case: m=1: A000079; m=4: A003269; m=5: A003520; m=6: A005708; m=7: A005709; m=8: A005710.
For n >= 8, a(n-8) = number of compositions of n in which each part is >= 8. - Milan Janjic, Jun 28 2010
Number of compositions of n into parts 1 and 8. - Joerg Arndt, Jun 24 2011
a(n+7) equals the number of binary words of length n having at least 7 zeros between every two successive ones. - Milan Janjic, Feb 09 2015

P. Chinn and S. Heubach, (1, k)-compositions, Congr. Numer. 164 (2003), 183-194.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..500
Mudit Aggarwal and Samrith Ram, Generating Functions for Straight Polyomino Tilings of Narrow Rectangles, J. Int. Seq., Vol. 26 (2023), Article 23.1.4.
Michael A. Allen, On a Two-Parameter Family of Generalizations of Pascal's Triangle, arXiv:2209.01377 [math.CO], 2022.
Michael A. Allen, Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings, arXiv:2409.00624 [math.CO], 2024. See p. 18.
D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 10.
P. Chinn and S. Heubach, (1, k)-compositions, Congr. Numer. 164 (2003), 183-194. [Local copy]
E. Di Cera and Y. Kong, Theory of multivalent binding in one and two-dimensional lattices, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.
I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5
R. K. Guy, Letter to N. J. A. Sloane with attachment, 1988
Jia Huang, Compositions with restricted parts, arXiv:1812.11010 [math.CO], 2018.
D. Kleitman, Solution to Problem E3274, Amer. Math. Monthly, 98 (1991), 958-959.
A. O. Munagi, Euler-type identities for integer compositions via zig-zag graphs, Integers 12 (2012), Paper No. A60, 10 pp.
Augustine O. Munagi, Integer Compositions and Higher-Order Conjugation, J. Int. Seq., Vol. 21 (2018), Article 18.8.5.
D. Newman, Problem E3274, Amer. Math. Monthly, 95 (1988), 555.
Djamila Oudrar and Maurice Pouzet, Ordered structures with no finite monomorphic decomposition. Application to the profile of hereditary classes, arXiv:2312.05913 [math.CO], 2023. See p. 18.
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
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 381
Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,0,0,0,1).

Cf. A000045, A000079, A000930, A003269, A003520, A005708, A005709, A005711.

A005710:=-1/(-1+z+z**8); # Simon Plouffe in his 1992 dissertation.
ZL:=[S, {a = Atom, b = Atom, S = Prod(X,Sequence(Prod(X,b))), X = Sequence(b,card >= 7)}, unlabelled]: seq(combstruct[count](ZL, size=n), n=7..62); # Zerinvary Lajos, Mar 26 2008
M := Matrix(8, (i,j)-> if j=1 and member(i,[1,8]) then 1 elif (i=j-1) then 1 else 0 fi); a := n -> (M^(n))[1,1]; seq(a(n), n=0..55); # Alois P. Heinz, Jul 27 2008

LinearRecurrence[{1, 0, 0, 0, 0, 0, 0, 1}, {1, 1, 1, 1, 1, 1, 1, 1}, 80] (* Vladimir Joseph Stephan Orlovsky, Feb 16 2012 *)
CoefficientList[Series[1/(1-x-x^8),{x,0,60}],x] (* Harvey P. Dale, Jun 14 2016 *)

x='x+O('x^66); Vec(x/(1-(x+x^8))) /* Joerg Arndt, Jun 25 2011 */

G.f.: 1/(1-x-x^8).
For positive integers n and k such that k <= n <= 8*k, and 7 divides n-k, define c(n,k) = binomial(k,(n-k)/7), and c(n,k) = 0, otherwise. Then, for n >= 1, a(n-1) = Sum_{k=1..n} c(n,k). - Milan Janjic, Dec 09 2011
Apparently a(n) = hypergeometric([1/8-n/8, 1/4-n/8, 3/8-n/8, 1/2-n/8, 5/8-n/8, 3/4-n/8, 7/8-n/8, -n/8], [1/7-n/7, 2/7-n/7, 3/7-n/7, 4/7-n/7, 5/7-n/7, 6/7-n/7, -n/7], -8^8/7^7) for n >= 49. - Peter Luschny, Sep 19 2014

Additional comments from Yong Kong (ykong(AT)curagen.com), Dec 16 2000

A017903 Expansion of 1/(1 - x^9 - x^10 - ...).

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 15, 19, 24, 30, 37, 45, 54, 64, 76, 91, 110, 134, 164, 201, 246, 300, 364, 440, 531, 641, 775, 939, 1140, 1386, 1686, 2050, 2490, 3021, 3662, 4437, 5376, 6516, 7902, 9588

Offset: 0

N. J. A. Sloane

A Lamé sequence of higher order.
a(n) = number of compositions of n in which each part is >=9. - Milan Janjic, Jun 28 2010
a(n+9) equals the number of n-length binary words such that 0 appears only in a run which length is a multiple of 9. - Milan Janjic, Feb 17 2015

Alois P. Heinz, Table of n, a(n) for n = 0..1000
I. M. Gessel, Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5
J. Hermes, Anzahl der Zerlegungen einer ganzen rationalen Zahl in Summanden, Math. Ann., 45 (1894), 371-380.
Augustine O. Munagi, Integer Compositions and Higher-Order Conjugation, J. Int. Seq., Vol. 21 (2018), Article 18.8.5.
Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,0,0,0,0,1)

For Lamé sequences of orders 1 through 9 see A000045, A000930, A017898-A017904.

Cf. A005711.

f := proc(r) local t1,i; t1 := []; for i from 1 to r do t1 := [op(t1),0]; od: for i from 1 to r+1 do t1 := [op(t1),1]; od: for i from 2*r+2 to 50 do t1 := [op(t1),t1[i-1]+t1[i-1-r]]; od: t1; end; # set r = order
a:= n-> (Matrix(9, (i,j)-> if (i=j-1) then 1 elif j=1 then [1, 0$7, 1][i] else 0 fi)^n)[9,9]: seq(a(n), n=0..55); # Alois P. Heinz, Aug 04 2008

CoefficientList[(1-x)/(1-x-x^9) + O[x]^70, x] (* Jean-François Alcover, Jun 08 2015 *)

Vec((x-1)/(x-1+x^9)+O(x^99)) \\ Charles R Greathouse IV, Sep 26 2012

G.f.: (x-1)/(x-1+x^9). - Alois P. Heinz, Aug 04 2008
For positive integers n and k such that k <= n <= 9*k, and 8 divides n-k, define c(n,k) = binomial(k,(n-k)/8), and c(n,k) = 0, otherwise. Then, for n>= 1, a(n+9) = sum(c(n,k), k=1..n). - Milan Janjic, Dec 09 2011
a(n) = A005711(n-10) for n > 9. - Alois P. Heinz, May 21 2018

A141539 Square array A(n,k) of numbers of length n binary words with at least k "0" between any two "1" digits (n,k >= 0), read by antidiagonals.

Original entry on oeis.org

1, 1, 2, 1, 2, 4, 1, 2, 3, 8, 1, 2, 3, 5, 16, 1, 2, 3, 4, 8, 32, 1, 2, 3, 4, 6, 13, 64, 1, 2, 3, 4, 5, 9, 21, 128, 1, 2, 3, 4, 5, 7, 13, 34, 256, 1, 2, 3, 4, 5, 6, 10, 19, 55, 512, 1, 2, 3, 4, 5, 6, 8, 14, 28, 89, 1024, 1, 2, 3, 4, 5, 6, 7, 11, 19, 41, 144, 2048, 1, 2, 3, 4, 5, 6, 7, 9, 15, 26, 60, 233, 4096

Offset: 0

Alois P. Heinz, Aug 15 2008

A(n,k+1) = A(n,k) - A143291(n,k).
From Gary W. Adamson, Dec 19 2009: (Start)
Alternative method generated from variants of an infinite lower triangle T(n) = A000012 = (1; 1,1; 1,1,1; ...) such that T(n) has the leftmost column shifted up n times. Then take lim_{k->infinity} T(n)^k, obtaining a left-shifted vector considered as rows of an array (deleting the first 1) as follows:
  1, 2, 4, 8, 16, 32, 64, 128, 256, ... = powers of 2
  1, 1, 2, 3,  5,  8, 13,  21,  34, ... = Fibonacci numbers
  1, 1, 1, 2,  3,  4,  6,   9,  13, ... = A000930
  1, 1, 1, 1,  2,  3,  4,   5,   7, ... = A003269
  ... with the next rows A003520, A005708, A005709, ... such that beginning with the Fibonacci row, the succession of rows are recursive sequences generated from a(n) = a(n-1) + a(n-2); a(n) = a(n-1) + a(n-3), ... a(n) = a(n-1) + a(n-k); k = 2,3,4,... Last, columns going up from the topmost 1 become rows of triangle A141539. (End)

			A(4,2) = 6, because 6 binary words of length 4 have at least 2 "0" between any two "1" digits: 0000, 0001, 0010, 0100, 1000, 1001.
Square array A(n,k) begins:
    1,  1,  1,  1,  1,  1,  1,  1, ...
    2,  2,  2,  2,  2,  2,  2,  2, ...
    4,  3,  3,  3,  3,  3,  3,  3, ...
    8,  5,  4,  4,  4,  4,  4,  4, ...
   16,  8,  6,  5,  5,  5,  5,  5, ...
   32, 13,  9,  7,  6,  6,  6,  6, ...
   64, 21, 13, 10,  8,  7,  7,  7, ...
  128, 34, 19, 14, 11,  9,  8,  8, ...

Alois P. Heinz, Table of n, a(n) for n = 0..140, flattened

Cf. column k=0: A000079, k=1: A000045(n+2), k=2: A000930(n+2), A068921, A078012(n+5), k=3: A003269(n+4), A017898(n+7), k=4: A003520(n+4), A017899(n+9), k=5: A005708(n+5), A017900(n+11), k=6: A005709(n+6), A017901(n+13), k=7: A005710(n+7), A017902(n+15), k=8: A005711(n+7), A017903(n+17), k=9: A017904(n+19), k=10: A017905(n+21), k=11: A017906(n+23), k=12: A017907(n+25), k=13: A017908(n+27), k=14: A017909(n+29).
Main diagonal gives A000027(n+1).
A(2n,n) gives A000217(n+1)
A(3n,n) gives A008778.
A(3n,2n) gives A034856(n+1).
A(2n,3n) gives A005408.
A(2^n-1,n) gives A376697.
See also A143291.

A:= proc(n, k) option remember;
      if k=0 then 2^n
    elif n<=k and n>=0 then n+1
    elif n>0 then A(n-1, k) +A(n-k-1, k)
    else          A(n+1+k, k) -A(n+k, k)
      fi
    end:
seq(seq(A(n, d-n), n=0..d), d=0..15);

a[n_, k_] := a[n, k] = Which[k == 0, 2^n, n <= k && n >= 0, n+1, n > 0, a[n-1, k] + a[n-k-1, k], True, a[n+1+k, k] - a[n+k, k]]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 15}] // Flatten (* Jean-François Alcover, Dec 17 2013, translated from Maple *)

G.f. of column k: x^(-k)/(1-x-x^(k+1)).

A(n,k) = 2^n if k=0, otherwise A(n,k) = n+1 if n<=k, otherwise A(n,k) = A(n-1,k) + A(n-k-1,k).

A355898 a(1) = a(2) = 1; a(n) = gcd(a(n-1), a(n-2)) + (a(n-1) + a(n-2))/gcd(a(n-1), a(n-2)).

Original entry on oeis.org

1, 1, 3, 5, 9, 15, 11, 27, 39, 25, 65, 23, 89, 113, 203, 317, 521, 839, 1361, 2201, 3563, 5765, 9329, 15095, 24425, 7909, 32335, 40245, 14521, 54767, 69289, 124057, 193347, 317405, 46443, 363849, 136767, 166875, 101217, 89367, 63531, 50969, 114501, 165471, 93327, 86269, 179597, 265867, 445465, 711333

Offset: 1

N. J. A. Sloane, Sep 01 2022

nonn

Suggested by A351871.
Sequence appears to diverge, but it would be nice to have a proof.
From Giorgos Kalogeropoulos, Nov 01 2022 : (Start)
Conjecture: For n >= 3775 a(n) can also be expressed in the following three ways:
1) a(n) = 1 + a(n-1) + a(n-2).
2) a(n) = 2*a(n-1) - a(n-3).
3) If A = a(3774), B = a(3772) and F = Fibonacci A000045(n),
   a(n) = (A+1)*F(n-3772) - (B+1)*F(n-3774) - 1.
These three formulas only work for n >= 3775. (End)

Seiichi Manyama, Table of n, a(n) for n = 1..5000 (terms 1..1002 from N. J. A. Sloane)
Michael De Vlieger, Labeled scalar plot of m = log_2(a(n)), n = 1..2^12, highlighting areas with near-zero second differences of log_2(a(n)) in red, otherwise blue. Labels are indices that begin and end a run of second differences near zero. The third run begins at n approximately 3797 but continues at least to n = 2^16. "Near-zero" means m > 10^-10.
Peter Munn, Logarithmic plot of a(n)/A005711(n). (Note that A005711 has essentially constant exponential growth.)
Mathematics Stack Exchange user Augusto Santi, A singular variant of the OEIS sequence A349576.
Giorgos Kalogeropoulos, After the term a(3773) it appears that the logarithmic graph is a straight line. This happens because the GCD of two successive terms from a(3773) and on is equal to 1. I tested all the terms up to a(10^6). If this holds to infinity then the sequence diverges. Here are the log graphs: Log plot 5000 terms, Log plot 10000 terms, Log plot 100000 terms.

Cf. A005711, A351871, A355899.

A351871 := proc(u,v,M) local n,r,s,g,t,a;
a:=[u,v]; r:=u; s:=v;
for n from 1 to M do g:=gcd(r,s); t:=g+(r+s)/g; a:=[op(a),t];
   r:=s; s:=t; od;
a;
end proc;
A351871(1,1,100);

Nest[Append[#1, #3 + Total[#2]/#3] & @@ {#1, #2, GCD @@ #2} & @@ {#, #[[-2 ;; -1]], GCD[#[[-2 ;; -1]]]} &, {1, 1}, 48] (* Michael De Vlieger, Sep 03 2022 *)

{a355898(N=50,A1=1,A2=1)= my(a=vector(N));a[1]=A1;a[2]=A2;for(n=1,N,if(n>2,my(g=gcd(a[n-1],a[n-2]));a[n]=g+(a[n-1]+a[n-2])/g);print1(a[n],",")) } \\ Ruud H.G. van Tol, Sep 19 2022

from math import gcd
from itertools import islice
def A355898_gen(): # generator of terms
    yield from (a:=(1,1))
    while True: yield (a:=(a[1],(b:=gcd(*a))+sum(a)//b))[1]
A355898_list = list(islice(A355898_gen(),30)) # Chai Wah Wu, Sep 01 2022

cp's OEIS Frontend

A003269 a(n) = a(n-1) + a(n-4) with a(0) = 0, a(1) = a(2) = a(3) = 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

SageMath

Formula

Extensions

A003520 a(n) = a(n-1) + a(n-5); a(0) = ... = a(4) = 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Formula

Extensions

A005709 a(n) = a(n-1) + a(n-7), with a(i) = 1 for i = 0..6.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A005708 a(n) = a(n-1) + a(n-6), with a(i) = 1 for i = 0..5.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A005710 a(n) = a(n-1) + a(n-8), with a(i) = 1 for i = 0..7.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A017903 Expansion of 1/(1 - x^9 - x^10 - ...).

Views

Author

Keywords