A005711 a(n) = a(n-1) + a(n-9) for n >= 9; a(n) = 1 for n=0..7; a(8) = 2.

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, 11638, 14128, 17149, 20811, 25248

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

a(n+7) equals the number of binary words of length n having at least 8 zeros between every two successive ones. - Milan Janjic, Feb 09 2015

a(n) is the number of compositions of n+1 into parts 1 and 9. - Joerg Arndt, May 19 2018

References

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• P. Chinn and S. Heubach, (1, k)-compositions, Congr. Numer. 164 (2003), 183-194. [Local copy]
• I. M. Gessel, 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
• D. Kleitman, Solution to Problem E3274, Amer. Math. Monthly, 98 (1991), 958-959.
• 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 382
• Index entries for linear recurrences with constant coefficients, signature (1, 0, 0, 0, 0, 0, 0, 0, 1).

Crossrefs

Cf. A005710.

Programs

Maple

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

Mathematica

CoefficientList[Series[(1+x^8)/(1-x-x^9), {x, 0, 57}], x] (* Michael De Vlieger, May 20 2018 *)
LinearRecurrence[{1,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,2},60] (* Harvey P. Dale, Jul 30 2022 *)

PARI

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

Formula

G.f.: (1+x^8)/(1-x-x^9).

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-1) = Sum_{k=1..n} c(n,k). - Milan Janjic, Dec 09 2011