login
a(n) = a(n-1) + a(n-9) for n >= 9; a(n) = 1 for n=0..7; a(8) = 2.
(Formerly M0479)
13

%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_