|
%I M3240 N1308 #94 Feb 17 2024 11:13:10
%S 1,1,4,5,6,10,15,21,31,46,67,98,144,211,309,453,664,973,1426,2090,
%T 3063,4489,6579,9642,14131,20710,30352,44483,65193,95545,140028,
%U 205221,300766,440794,646015,946781,1387575,2033590,2980371,4367946,6401536,9381907
%N a(1) = a(2) = 1, a(3) = 4; thereafter a(n) = a(n-1) + a(n-3).
%C 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.
%C 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
%C 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
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Indranil Ghosh, <a href="/A001609/b001609.txt">Table of n, a(n) for n = 1..6012</a> (terms 1..500 from T. D. Noe)
%H Ignacio Cascudo, <a href="https://arxiv.org/abs/1703.01267">On squares of cyclic codes</a>, arXiv:1703.01267 [cs.IT], 2017. See Theorem 6.1/Table 1.
%H Johann Cigler, <a href="https://arxiv.org/abs/1912.06651">Some remarks on generalized Fibonacci and Lucas polynomials</a>, arXiv:1912.06651 [math.CO], 2019.
%H E. Di Cera and Y. Kong, <a href="http://dx.doi.org/10.1016/S0301-4622(96)02178-3">Theory of multivalent binding in one and two-dimensional lattices</a>, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.
%H Daniel C. Fielder, <a href="http://www.fq.math.ca/Scanned/6-3/fielder.pdf">Special integer sequences controlled by three parameters</a>, Fibonacci Quarterly 6, 1968, 64-70.
%H Daniel C. Fielder, <a href="http://www.fq.math.ca/Scanned/6-3/errata.pdf">Errata:Special integer sequences controlled by three parameters</a>, Fibonacci Quarterly 6, 1968, 64-70.
%H Dov Jarden, <a href="/A001602/a001602.pdf">Recurring Sequences</a>, Riveon Lematematika, Jerusalem, 1966. [Annotated scanned copy] See p. 91.
%H Matthew Macauley, Jon McCammond, Henning S. Mortveit, <a href="http://www.emis.de/journals/JACO/Volume33_1/hgv665924j44t770.html">Dynamics groups of asynchronous cellular automata</a>, Journal of Algebraic Combinatorics, Vol 33, No 1 (2011), pp. 11-35.
%H M. Newman and D. Shanks, <a href="http://dx.doi.org/10.1090/S0025-5718-1984-0725996-9">On a sequence arising in series for pi</a>, Math. Comp., 42 (1984), 199-217 (see Eq. 29).
%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 Souvik Roy, Nazim Fatès, and Sukanta Das, <a href="https://inria.hal.science/hal-04456320">Reversibility of Elementary Cellular Automata with fully asynchronous updating: an analysis of the rules with partial recurrence</a>, hal-04456320 [nlin.CG], [cs], 2024. See p. 19.
%H T. Sillke, <a href="http://www.mathematik.uni-bielefeld.de/~sillke/SEQUENCES/series001">The binary form of Conway's sequence</a>
%H Z. Skupien, <a href="http://dx.doi.org/10.1016/j.disc.2008.11.003">Sparse Hamiltonian 2-decompositions together with exact count of numerous Hamiltonian cycles</a>, Discr. Math., 309 (2009), 6382-6390. - _N. J. A. Sloane_, Feb 12 2010
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,1).
%F G.f.: x*(1 + 3*x^2)/(1 - x - x^3).
%F a(n) = trace of successive powers of matrix ({{0,0,1},{1,0,0},{0,1,1}})^n. - _Artur Jasinski_, Jan 10 2007
%F a(n) = A000930(n) + 3*A000930(n-2). - _R. J. Mathar_, Nov 16 2007
%F Logarithmic derivative of Narayana's cows sequence A000930. - _Paul D. Hanna_, Oct 28 2012
%F 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
%e G.f. = x + x^2 + 4*x^3 + 5*x^4 + 6*x^5 + 10*x^6 + 15*x^7 + 21*x^8 + ...
%p A001609:=-(1+3*z**2)/(-1+z+z**3); # _Simon Plouffe_ in his 1992 dissertation
%p f:= gfun:-rectoproc({a(n) = a(n-1) + a(n-3), a(1)=1,a(2)=1,a(3)=4},a(n),remember):
%p map(f, [$1..100]); # _Robert Israel_, Jun 29 2015
%t Table[Tr[MatrixPower[{{0, 0, 1}, {1, 0, 0}, {0, 1, 1}}, n]], {n, 1, 60}] (* _Artur Jasinski_, Jan 10 2007 *)
%t 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 *)
%t 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 *)
%t LinearRecurrence[{1, 0, 1}, {1, 1, 4}, 50] (* _Vincenzo Librandi_, Jun 28 2015 *)
%o (PARI) {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 */
%o (Magma) 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
%Y Cf. A000204, A014097, A000079, A003269, A003520, A005708, A005709, A005710, A000930, A218439.
%Y Cf. also A049064, A049194.
%K nonn,easy
%O 1,3
%A _N. J. A. Sloane_
%E Additional comments from Yong Kong (ykong(AT)curagen.com), Dec 16 2000
%E More terms from _Michael Somos_, Oct 03 2002
%E Deleted certain dangerous or potentially dangerous links. - _N. J. A. Sloane_, Jan 30 2021
|
