%I M0479 #95 May 25 2023 06:58:13
%S 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,
%T 110,134,164,201,246,300,364,440,531,641,775,939,1140,1386,1686,2050,
%U 2490,3021,3662,4437,5376,6516,7902,9588,11638,14128,17149,20811,25248
%N a(n) = a(n-1) + a(n-9) for n >= 9; a(n) = 1 for n=0..7; a(8) = 2.
%C 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
%C a(n) is the number of compositions of n+1 into parts 1 and 9. - _Joerg Arndt_, May 19 2018
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Alois P. Heinz, <a href="/A005711/b005711.txt">Table of n, a(n) for n = 0..1000</a>
%H P. Chinn and S. Heubach, <a href="/A005710/a005710.pdf">(1, k)-compositions</a>, Congr. Numer. 164 (2003), 183-194. [Local copy]
%H I. M. Gessel, Ji Li, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Gessel/gessel6.html">Compositions and Fibonacci identities</a>, J. Int. Seq. 16 (2013) 13.4.5
%H R. K. Guy, <a href="/A004001/a004001_2.pdf">Letter to N. J. A. Sloane with attachment, 1988</a>
%H D. Kleitman, <a href="http://www.jstor.org/stable/2324158">Solution to Problem E3274</a>, Amer. Math. Monthly, 98 (1991), 958-959.
%H Augustine O. Munagi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Munagi/munagi10.html">Integer Compositions and Higher-Order Conjugation</a>, J. Int. Seq., Vol. 21 (2018), Article 18.8.5.
%H D. Newman, <a href="http://www.jstor.org/stable/2322766">Problem E3274</a>, Amer. Math. Monthly, 95 (1988), 555.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=382">Encyclopedia of Combinatorial Structures 382</a>
%H <a href="/index/Rec#order_09">Index entries for linear recurrences with constant coefficients</a>, signature (1, 0, 0, 0, 0, 0, 0, 0, 1).
%F G.f.: (1+x^8)/(1-x-x^9).
%F 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
%p A005711:=-(1+z**8)/(-1+z+z**9); # _Simon Plouffe_ in his 1992 dissertation
%p 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
%p 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
%t CoefficientList[Series[(1+x^8)/(1-x-x^9), {x, 0, 57}], x] (* _Michael De Vlieger_, May 20 2018 *)
%t 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 *)
%o (PARI) x='x+O('x^66); Vec((1+x^8)/(1-x-x^9)) /* _Joerg Arndt_, Jun 25 2011 */
%Y Cf. A005710.
%K nonn,easy
%O 0,9
%A _N. J. A. Sloane_