A003269 -id:A003269 - cp's OEIS frontend

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

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

A274142 Number of integers in n-th generation of tree T(1/2) defined in Comments.

Original entry on oeis.org

1, 1, 1, 2, 2, 4, 5, 8, 11, 17, 25, 37, 54, 81, 119, 177, 261, 388, 574, 851, 1260, 1868, 2767, 4101, 6077, 9006, 13347, 19781, 29315, 43448, 64392, 95436, 141444, 209636, 310705, 460501, 682519, 1011581, 1499295, 2222155, 3293534, 4881472, 7235018, 10723311, 15893460, 23556367, 34913897, 51747400

Offset: 0

Clark Kimberling, Jun 11 2016

nonn

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,2x,x+1,x^2}, etc.  Let T(r) be the tree obtained by substituting r for x.
Guide to related sequences:
r           sequence
1/2         A274142
1/3         A274143
1/4         A274144
2/3         A274145
3/4         A274146
-1/2        A274147
-1/3        A274148
-1/4        A274149
-2/3        A274150
-3/4        A274151
3/2         A274152
5/2         A274153
-3/2        A274154
-5/2        A274155
2^(1/2)     A000045 (Fibonacci numbers)
2^(1/3)     A000930
2^(1/4)     A003269
2^(-1/2)    A274156
3^(-1/2)    A274157
2^(-1/3)    A274158
3^(-1/3)    A274159
i           A274160
2i          A206743
3i          A274162
4i          A274163
i/2         A274149
i/3         A274165
i+1         A274166
i-1         A274167
(-1+3i)/2   A274168

			If r = 1/2, then g(3) = {3,2r,r+1, r^2}, in which the integers are 3 and 1, so that a(3) = 2.

Kenny Lau, Table of n, a(n) for n = 0..5847

Cf. A274143-A274160, A274162, A274163, A274165-A274168.

z = 18; t = Join[{{0}}, Expand[NestList[DeleteDuplicates[Flatten[Map[{# + 1, x*#} &, #], 1]] &, {1}, z]]];
u = Table[t[[k]] /. x -> 1/2, {k, 1, z}];
Table[Count[Map[IntegerQ, u[[k]]], True], {k, 1, z}]
(* second program: *)
T[0] = {0}; T[n_] := T[n] = Complement[Join[T[n-1]+1, x*T[n-1]], T[n-1]]; Reap[For[n = 0, n <= 25, n++, cnt = Count[T[n] /. x -> 1/2, Integer]; Print[n, " ", cnt]; Sow[cnt]]][[2, 1]] (* _Jean-François Alcover, Jun 14 2016 *)

More terms from Jean-François Alcover, Jun 14 2016

More terms from Kenny Lau, Jul 04 2016

A145153 Square array A(n,k), n >= 0, k >= 0, read by antidiagonals, where sequence a_k of column k is the expansion of x/((1 - x - x^4)*(1 - x)^(k - 1)).

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 2, 1, 0, 0, 1, 3, 3, 1, 1, 0, 1, 4, 6, 4, 2, 1, 0, 1, 5, 10, 10, 6, 3, 1, 0, 1, 6, 15, 20, 16, 9, 4, 1, 0, 1, 7, 21, 35, 36, 25, 13, 5, 2, 0, 1, 8, 28, 56, 71, 61, 38, 18, 7, 3, 0, 1, 9, 36, 84, 127, 132, 99, 56, 25, 10, 4, 0, 1, 10, 45, 120, 211, 259, 231, 155, 81, 35, 14, 5

Offset: 0

Alois P. Heinz, Oct 03 2008

Each row sequence a_n (for n > 0) is produced by a polynomial of degree n-1, whose (rational) coefficients are given in row n of A145140/A145141. The coefficients *(n-1)! are given in A145142.

Each column sequence a_k is produced by a recursion, whose coefficients are given by row k of A145152.

			Square array A(n,k) begins:
  0, 0, 0,  0,  0,  0,   0, ...
  1, 1, 1,  1,  1,  1,   1, ...
  0, 1, 2,  3,  4,  5,   6, ...
  0, 1, 3,  6, 10, 15,  21, ...
  0, 1, 4, 10, 20, 35,  56, ...
  1, 2, 6, 16, 36, 71, 127, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened

Rows 0-9 give: A000004, A000012, A001477, A000217, A000292, A145126, A145127, A145128, A145129, A145130.
Columns 0-9 give: A017898(n-1) for n>0, A003269, A098578, A145131, A145132, A145133, A145134, A145135, A145136, A145137.
Main diagonal gives: A145138.
Antidiaginal sums give: A145139.
Numerators/denominators of polynomials for rows give: A145140/A145141.
Cf. A145142, A145143, A145144, A145145, A145146, A145147, A145148, A145149, A145150, A145151, A145152.

A:= proc(n, k) coeftayl (x/ (1-x-x^4)/ (1-x)^(k-1), x=0, n) end:
seq(seq(A(n, d-n), n=0..d), d=0..13);

a[n_, k_] := SeriesCoefficient[x/(1 - x - x^4)/(1 - x)^(k - 1), {x, 0, n}]; Table[a[n - k, k], {n, 0, 12}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Dec 05 2013 *)

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

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

A001609 a(1) = a(2) = 1, a(3) = 4; thereafter a(n) = a(n-1) + a(n-3).

Original entry on oeis.org

1, 1, 4, 5, 6, 10, 15, 21, 31, 46, 67, 98, 144, 211, 309, 453, 664, 973, 1426, 2090, 3063, 4489, 6579, 9642, 14131, 20710, 30352, 44483, 65193, 95545, 140028, 205221, 300766, 440794, 646015, 946781, 1387575, 2033590, 2980371, 4367946, 6401536, 9381907

Offset: 1

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 = 1...m-1, a(m) = m + 1. The generating function is (x + m*x^m)/(1 - x - x^m). Also a(n) = 1 + n*Sum_{i=1..n/m} binomial(n-1-(m-1)*i, i-1)/i. This gives the number of ways to cover (without overlapping) a ring lattice (or necklace) of n sites with molecules that are m sites wide. Special cases: m=2: A000204, m=3: A001609, m=4: A014097, m=5: A058368, m=6: A058367, m=7: A058366, m=8: A058365, m=9: A058364.
The sequence defined by {a(n) - 1} plays a role for the computation of A065414, A146486, A146487, and A146488 equivalent to the role of A001610 for A005596, A146482, A146483 and A146484, see the variable a_{2,n} in arXiv:0903.2514. - R. J. Mathar, Mar 28 2009
Except for n = 2, a(n) is the number of digits in n-th term of A049064. This can be derived form the T. Sillke link below. - Jianing Song, Apr 28 2019

			G.f. = x + x^2 + 4*x^3 + 5*x^4 + 6*x^5 + 10*x^6 + 15*x^7 + 21*x^8 + ...

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

Indranil Ghosh, Table of n, a(n) for n = 1..6012 (terms 1..500 from T. D. Noe)
Ignacio Cascudo, On squares of cyclic codes, arXiv:1703.01267 [cs.IT], 2017. See Theorem 6.1/Table 1.
Johann Cigler, Some remarks on generalized Fibonacci and Lucas polynomials, arXiv:1912.06651 [math.CO], 2019.
E. Di Cera and Y. Kong, Theory of multivalent binding in one and two-dimensional lattices, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.
Daniel C. Fielder, Special integer sequences controlled by three parameters, Fibonacci Quarterly 6, 1968, 64-70.
Daniel C. Fielder, Errata:Special integer sequences controlled by three parameters, Fibonacci Quarterly 6, 1968, 64-70.
Dov Jarden, Recurring Sequences, Riveon Lematematika, Jerusalem, 1966. [Annotated scanned copy] See p. 91.
Matthew Macauley, Jon McCammond, Henning S. Mortveit, Dynamics groups of asynchronous cellular automata, Journal of Algebraic Combinatorics, Vol 33, No 1 (2011), pp. 11-35.
M. Newman and D. Shanks, On a sequence arising in series for pi, Math. Comp., 42 (1984), 199-217 (see Eq. 29).
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.
Souvik Roy, Nazim Fatès, and Sukanta Das, Reversibility of Elementary Cellular Automata with fully asynchronous updating: an analysis of the rules with partial recurrence, hal-04456320 [nlin.CG], [cs], 2024. See p. 19.
T. Sillke, The binary form of Conway's sequence
Z. Skupien, Sparse Hamiltonian 2-decompositions together with exact count of numerous Hamiltonian cycles, Discr. Math., 309 (2009), 6382-6390. - _N. J. A. Sloane_, Feb 12 2010
Index entries for linear recurrences with constant coefficients, signature (1,0,1).

Cf. A000204, A014097, A000079, A003269, A003520, A005708, A005709, A005710, A000930, A218439.

Cf. also A049064, A049194.

I:=[1,1,4]; [n le 3 select I[n] else Self(n-1)+Self(n-3): n in [1..45]]; // Vincenzo Librandi, Jun 28 2015

A001609:=-(1+3*z**2)/(-1+z+z**3); # Simon Plouffe in his 1992 dissertation
f:= gfun:-rectoproc({a(n) = a(n-1) + a(n-3), a(1)=1,a(2)=1,a(3)=4},a(n),remember):
map(f, [$1..100]); # Robert Israel, Jun 29 2015

Table[Tr[MatrixPower[{{0, 0, 1}, {1, 0, 0}, {0, 1, 1}}, n]], {n, 1, 60}] (* Artur Jasinski, Jan 10 2007 *)
Table[ HypergeometricPFQ[{1/3 - n/3, 2/3 - n/3, -(n/3)}, {1/2 - n/2, 1 - n/2}, -(27/4)], {n, 20}] (* Alexander R. Povolotsky, Nov 21 2008 *)
a[1] = a[2] = 1; a[3] = 4; m = 3; a[n_] := 1 + n*Sum [Binomial [n - 1 - (m - 1)*i, i - 1]/i, {i, n/m}] A001609 = Table[a[n], {n, 100}] (* Zak Seidov, Nov 21 2008 *)
LinearRecurrence[{1, 0, 1}, {1, 1, 4}, 50] (* Vincenzo Librandi, Jun 28 2015 *)

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

G.f.: x*(1 + 3*x^2)/(1 - x - x^3).
a(n) = trace of successive powers of matrix ({{0,0,1},{1,0,0},{0,1,1}})^n. - Artur Jasinski, Jan 10 2007
a(n) = A000930(n) + 3*A000930(n-2). - R. J. Mathar, Nov 16 2007
Logarithmic derivative of Narayana's cows sequence A000930. - Paul D. Hanna, Oct 28 2012
a(n) = w1^n + w2^n + w3^n, where w1,w2,w3 are the roots of the cubic: (-1 - x^2 + x^3), see A092526. - Gerry Martens, Jun 27 2015

Additional comments from Yong Kong (ykong(AT)curagen.com), Dec 16 2000
More terms from Michael Somos, Oct 03 2002
Deleted certain dangerous or potentially dangerous links. - N. J. A. Sloane, Jan 30 2021

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

Original entry on oeis.org

1, 0, 0, 1, 1, 0, 1, 2, 1, 1, 3, 3, 2, 4, 6, 5, 6, 10, 11, 11, 16, 21, 22, 27, 37, 43, 49, 64, 80, 92, 113, 144, 172, 205, 257, 316, 377, 462, 573, 693, 839, 1035, 1266, 1532, 1874, 2301, 2798, 3406, 4175, 5099, 6204, 7581, 9274, 11303, 13785, 16855, 20577, 25088

Offset: 0

N. J. A. Sloane

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={0,1}. - Vladimir Baltic, Mar 07 2012
Number of compositions (ordered partitions) of n into parts 3 and 4.
For n>=2, a(n-2) is the number of ways to tile the 1xn board with dominoes and squares (ie. monominoes) such that there are either one or two squares between dominoes, no squares at either end of the board, and there is at least one domino. - Enrique Navarrete, Sep 01 2024
For n>=3, a(n-3) is the number of ways to tile the 1xn board with triominoes (ie. size 1x3) and squares (ie. size 1x1) such that there are either none or one squares between triominoes, no squares at either end of the board, and there is at least one triomino. - Enrique Navarrete, Sep 07 2024

Seiichi Manyama, Table of n, a(n) for n = 0..10000
Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics 4 (2010), 119-135.
Johann Cigler, Recurrences for certain sequences of binomial sums in terms of (generalized) Fibonacci and Lucas polynomials, arXiv:2212.02118 [math.NT], 2022.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 484
Milan Janjic, Binomial Coefficients and Enumeration of Restricted Words, Journal of Integer Sequences, 2016, Vol 19, #16.7.3.
E. Wilson, The Scales of Mt. Meru
Index entries for two-way infinite sequences
Index entries for linear recurrences with constant coefficients, signature (0,0,1,1).

A003269(n) = a(-4-n)(-1)^n.

a:=[1,0,0,1];; for n in [5..60] do a[n]:=a[n-3]+a[n-4]; od; a; # G. C. Greubel, Mar 05 2019

I:=[1,0,0,1]; [n le 4 select I[n] else Self(n-3) +Self(n-4): n in [1..60]]; // G. C. Greubel, Mar 05 2019

LinearRecurrence[{0,0,1,1}, {1,0,0,1}, 60] (* G. C. Greubel, Mar 05 2019 *)

a(n)=polcoeff(if(n<0,(1+x)/(1+x-x^4),1/(1-x^3-x^4)) +x*O(x^abs(n)), abs(n))

(1/(1-x^3-x^4)).series(x, 60).coefficients(x, sparse=False) # G. C. Greubel, Mar 05 2019

G.f.: 1/(1-x^3-x^4).
a(n)/a(n-1) tends to A060007. - Gary W. Adamson, Oct 22 2006
a(n) = Sum_{k=0..floor(n/3)} binomial(k,n-3*k). - Seiichi Manyama, Mar 06 2019

More terms from Klaus Strassburger (strass(AT)ddfi.uni-duesseldorf.de), Dec 17 1999

A017898 Expansion of (1-x)/(1-x-x^4).

Original entry on oeis.org

1, 0, 0, 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

Offset: 0

N. J. A. Sloane

A Lamé sequence of higher order.
Essentially the same as A003269, which has much more information.
Number of compositions of n into parts >= 4. - Joerg Arndt, Aug 13 2012

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Christian Ballot, On Functions Expressible as Words on a Pair of Beatty Sequences, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.2.
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.
Milan Janjic, Binomial Coefficients and Enumeration of Restricted Words, Journal of Integer Sequences, 2016, Vol 19, #16.7.3
T. Mansour, M. Shattuck, A monotonicity property for generalized Fibonacci sequences, arXiv:1410.6943 [math.CO], 2014.
Augustine O. Munagi, Integer Compositions and Higher-Order Conjugation, J. Int. Seq., Vol. 21 (2018), Article 18.8.5.
J. D. Opdyke, A unified approach to algorithms generating unrestricted.., J. Math. Model. Algor. 9 (2010) 53-97
Index entries for linear recurrences with constant coefficients, signature (1,0,0,1).

For Lamé sequences of orders 1 through 9 see A000045, A000930, this one, and A017899-A017904.

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(4, (i,j)-> if (i=j-1) then 1 elif j=1 then [1, 0$2, 1][i] else 0 fi)^n)[4,4]: seq(a(n), n=0..42); # Alois P. Heinz, Aug 04 2008

LinearRecurrence[{1, 0, 0, 1}, {1, 0, 0, 0}, 80] (* Vladimir Joseph Stephan Orlovsky, Feb 11 2012 *)
CoefficientList[Series[(1-x)/(1-x-x^4),{x,0,50}],x] (* Harvey P. Dale, Sep 12 2019 *)

a(n)=([0,1,0,0; 0,0,1,0; 0,0,0,1; 1,0,0,1]^n*[1;0;0;0])[1,1] \\ Charles R Greathouse IV, Oct 03 2016

a(n) = a(n-1) + a(n-4). - R. J. Mathar, Mar 06 2008
G.f.: 1/(1-sum(k>=4, x^k)). - Joerg Arndt, Aug 13 2012
Apparently a(n) = hypergeometric([1-1/4*n, 5/4-1/4*n, 3/2-1/4*n, 7/4-1/4*n],[4/3-1/3*n, 5/3-1/3*n, 2-1/3*n], -4^4/3^3) for n>=13. - Peter Luschny, Sep 18 2014
a(n) = A003269(n+1)-A003269(n). - R. J. Mathar, Jun 10 2018

A086106 Decimal expansion of positive root of x^4 - x^3 - 1 = 0.

Original entry on oeis.org

1, 3, 8, 0, 2, 7, 7, 5, 6, 9, 0, 9, 7, 6, 1, 4, 1, 1, 5, 6, 7, 3, 3, 0, 1, 6, 9, 1, 8, 2, 2, 7, 3, 1, 8, 7, 7, 8, 1, 6, 6, 2, 6, 7, 0, 1, 5, 5, 8, 7, 6, 3, 0, 2, 5, 4, 1, 1, 7, 7, 1, 3, 3, 1, 2, 1, 1, 2, 4, 9, 5, 7, 4, 1, 1, 8, 6, 4, 1, 5, 2, 6, 1, 8, 7, 8, 6, 4, 5, 6, 8, 2, 4, 9, 0, 3, 5, 5, 0, 9, 3, 7

Offset: 1

Eric W. Weisstein, Jul 09 2003

Also the growth constant of the Fibonacci 3-numbers A003269 [Stakhov et al.]. - R. J. Mathar, Nov 05 2008

			1.380277569...
The four solutions are the present one, -A230151, and the two complex ones 0.2194474721... - 0.9144736629...*i and its complex conjugate. - _Wolfdieter Lang_, Aug 19 2022

Iain Fox, Table of n, a(n) for n = 1..20000
Simon Baker, Exceptional digit frequencies and expansions in non-integer bases, arXiv:1711.10397 [math.DS], 2017. See the beta(3) constant pp. 3-4.
A. Stakhov and B. Rozin, Theory of Binet formulas for Fibonacci and Lucas p-numbers, Chaos, Solit. Fractals 27 (2006), 1162-1177.
Eric Weisstein's World of Mathematics, Pisot Number.
Index entries for algebraic numbers, degree 4

Cf. -A230151 (other real root).

Cf. A060006.

RealDigits[Root[ -1 - #1^3 + #1^4 &, 2], 10, 110][[1]]

polrootsreal( x^4-x^3-1)[2] \\ Charles R Greathouse IV, Apr 14 2014

default(realprecision, 20080); x=solve(x=1, 2, x^4 - x^3 - 1); for (n=1, 20000, d=floor(x); x=(x-d)*10; write("b086106.txt", n, " ", d));  \\ Iain Fox, Oct 23 2017

Equals (1 + (A^2 + sqrt(A^4 - 16*u*A^2 + 2*A))/A)/4 with A = sqrt(8*u + 3/2), u = (-(Bp/2)^(1/3) + (Bm/2)^(1/3)*(1 - sqrt(3)*i)/2 - 3/8)/6, with Bp = 27 + 3*sqrt(3*283), Bm = 27 - 3*sqrt(3*283), and i = sqrt(-1). (Standard computation of a quartic.) The other (negative) real root -A230151 is obtained by using in the first formula the negative square root. The other two complex roots are obtained by replacing A by -A in these two formulas. - Wolfdieter Lang, Aug 19 2022

A376033 Number A(n,k) of binary words of length n avoiding distance (i+1) between "1" digits if the i-th bit is set in the binary representation of k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 2, 1, 2, 4, 1, 2, 3, 8, 1, 2, 4, 5, 16, 1, 2, 3, 6, 8, 32, 1, 2, 4, 4, 9, 13, 64, 1, 2, 3, 8, 6, 15, 21, 128, 1, 2, 4, 5, 12, 9, 25, 34, 256, 1, 2, 3, 6, 7, 18, 13, 40, 55, 512, 1, 2, 4, 4, 8, 11, 27, 19, 64, 89, 1024, 1, 2, 3, 8, 5, 11, 16, 45, 28, 104, 144, 2048

Offset: 0

Alois P. Heinz, Sep 09 2024

Also the number of subsets of [n] avoiding distance (i+1) between elements if the i-th bit is set in the binary representation of k. A(6,3) = 13: {}, {1}, {2}, {3}, {4}, {5}, {6}, {1,4}, {1,5}, {1,6}, {2,5}, {2,6}, {3,6}.
Each column sequence satisfies a linear recurrence with constant coefficients.
The sequence of row n is periodic with period A011782(n) = ceiling(2^(n-1)).

			A(6,6) = 17: 000000, 000001, 000010, 000011, 000100, 000110, 001000, 001100, 010000, 010001, 011000, 100000, 100001, 100010, 100011, 110000, 110001 because 6 = 110_2 and no two "1" digits have distance 2 or 3.
A(6,7) = 10: 000000, 000001, 000010, 000100, 001000, 010000, 010001, 100000, 100001, 100010.
A(7,7) = 14: 0000000, 0000001, 0000010, 0000100, 0001000, 0010000, 0010001, 0100000, 0100001, 0100010, 1000000, 1000001, 1000010, 1000100.
Square array A(n,k) begins:
     1,  1,   1,  1,   1,  1,  1,  1,   1,  1, ...
     2,  2,   2,  2,   2,  2,  2,  2,   2,  2, ...
     4,  3,   4,  3,   4,  3,  4,  3,   4,  3, ...
     8,  5,   6,  4,   8,  5,  6,  4,   8,  5, ...
    16,  8,   9,  6,  12,  7,  8,  5,  16,  8, ...
    32, 13,  15,  9,  18, 11, 11,  7,  24, 11, ...
    64, 21,  25, 13,  27, 16, 17, 10,  36, 17, ...
   128, 34,  40, 19,  45, 25, 27, 14,  54, 25, ...
   256, 55,  64, 28,  75, 37, 41, 19,  81, 37, ...
   512, 89, 104, 41, 125, 57, 60, 26, 135, 57, ...

Alois P. Heinz, Antidiagonals n = 0..200, flattened

Columns k=0-20 give: A000079, A000045(n+2), A006498(n+2), A000930(n+2), A006500, A130137, A079972(n+3), A003269(n+4), A031923(n+1), A263710(n+1), A224809(n+4), A317669(n+4), A351873, A351874, A121832(n+4), A003520(n+4), A208742, A374737, A375977, A375980, A375978.
Rows n=0-2 give: A000012, A007395(k+1), A010702(k+1).
Main diagonal gives A376091.
A(n,2^k-1) gives A141539.
A(2^n-1,2^n-1) gives A376697.
A(n,2^k) gives A209435.
Cf. A011782, A062383, A098011, A376921.

h:= proc(n) option remember; `if`(n=0, 1, 2^(1+ilog2(n))) end:
b:= proc(n, k, t) option remember; `if`(n=0, 1, add(`if`(j=1 and
      Bits[And](t, k)>0, 0, b(n-1, k, irem(2*t+j, h(k)))), j=0..1))
    end:
A:= (n, k)-> b(n, k, 0):
seq(seq(A(n, d-n), n=0..d), d=0..12);

step(v,b)={vector(#v, i, my(j=(i-1)>>1); if(bittest(i-1,0), if(bitand(b,j)==0, v[1+j], 0), v[1+j] + v[1+#v/2+j]));}
col(n,k)={my(v=vector(2^(1+logint(k,2))), r=vector(1+n)); v[1]=r[1]=1; for(i=1, n, v=step(v,k); r[1+i]=vecsum(v)); r}
A(n,k)=if(k==0, 2^n, col(n,k)[n+1]) \\ Andrew Howroyd, Oct 03 2024

A(n,k) = A(n,k+ceiling(2^(n-1))).
A(n,ceiling(2^(n-1))-1) = n+1.
A(n,ceiling(2^(n-2))) = ceiling(3*2^(n-2)) = A098011(n+2).

cp's OEIS Frontend

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

A274142 Number of integers in n-th generation of tree T(1/2) defined in Comments.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A145153 Square array A(n,k), n >= 0, k >= 0, read by antidiagonals, where sequence a_k of column k is the expansion of x/((1 - x - x^4)*(1 - x)^(k - 1)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

A001609 a(1) = a(2) = 1, a(3) = 4; thereafter a(n) = a(n-1) + a(n-3).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI