|
%I M2625 N1040 #262 Apr 04 2024 10:32:21
%S 3,1,3,7,11,21,39,71,131,241,443,815,1499,2757,5071,9327,17155,31553,
%T 58035,106743,196331,361109,664183,1221623,2246915,4132721,7601259,
%U 13980895,25714875,47297029,86992799,160004703,294294531,541292033,995591267,1831177831
%N a(n) = a(n-1) + a(n-2) + a(n-3), a(0)=3, a(1)=1, a(2)=3.
%C For n >= 3, a(n) is the number of cyclic sequences consisting of n zeros and ones that do not contain three consecutive ones provided the positions of the zeros and ones are fixed on a circle. This is proved in Charalambides (1991) and Zhang and Hadjicostas (2015). For example, a(3)=7 because only the sequences 110, 101, 011, 001, 010, 100 and 000 avoid three consecutive ones. (For n=1,2 the statement is still true provided we allow the sequence to wrap around itself on a circle.) - _Petros Hadjicostas_, Dec 16 2016
%C For n >= 3, also the number of dominating sets on the n-cycle graph C_n. - _Eric W. Weisstein_, Mar 30 2017
%C For n >= 3, also the number of minimal dominating sets and maximal irredundant sets on the n-sun graph. - _Eric W. Weisstein_, Jul 28 and Aug 17 2017
%C For n >= 3, also the number of minimal edge covers in the n-web graph. - _Eric W. Weisstein_, Aug 03 2017
%C For n >= 1, also the number of ways to tile a bracelet of length n with squares, dominoes, and trominoes. - _Ruijia Li_ and _Greg Dresden_, Sep 14 2019
%C If n is prime, then a(n)-1 is a multiple of n ; a counterexample for the converse is given by n = 182. - _Robert FERREOL_, Apr 03 2024
%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 500.
%D G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
%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 G. C. Greubel, <a href="/A001644/b001644.txt">Table of n, a(n) for n = 0..1000</a> (terms 1..200 from T. D. Noe)
%H Kunle Adegoke, Robert Frontczak, and Taras Goy, <a href="https://doi.org/10.47443/dml.2021.0080">Binomial Tribonacci Sums</a>, Disc. Math. Lett. (2022) Vol. 8, 30-37.
%H Kunle Adegoke, Adenike Olatinwo, and Winning Oyekanmi, <a href="https://arxiv.org/abs/1811.03663">New Tribonacci Recurrence Relations and Addition Formulas</a>, arXiv:1811.03663 [math.CO], 2018.
%H Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, <a href="http://arxiv.org/abs/1505.06339">Linear recurrence sequences with indices in arithmetic progression and their sums</a>, arXiv:1505.06339 [math.NT], 2015.
%H Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, <a href="http://www.emis.de/journals/JIS/VOL18/Szczyrba/sz3.html">Analytic Representations of the n-anacci Constants and Generalizations Thereof</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
%H C. A. Charalambides, <a href="http://www.fq.math.ca/Scanned/29-4/charalambides.pdf">Lucas numbers and polynomials of order k and the length of the longest circular success run</a>, The Fibonacci Quarterly, 29 (1991), 290-297.
%H Curtis Cooper, Steven Miller, Peter J. C. Moses, Murat Sahin, and Thotsaporn Thanatipanonda, <a href="http://web.williams.edu/Mathematics/sjmiller/public_html/math/papers/ruggleshoward10.pdf">On Identities Of Ruggles, Horadam, Howard, and Young</a>, Preprint, 2016.
%H Curtis Cooper, Steven Miller, Peter J. C. Moses, Murat Sahin, and Thotsaporn Thanatipanonda, <a href="https://www.fq.math.ca/Papers1/55-5/Cooper.pdf">On identities of Ruggles, Hradam, Howard, and Young</a>, The Fibonacci Quarterly, 55.5 (2017), 42-65.
%H M. Elia, <a href="http://www.fq.math.ca/Scanned/39-2/elia.pdf">Derived Sequences, The Tribonacci Recurrence and Cubic Forms</a>, The Fibonacci Quarterly, 39.2 (2001), 107-109.
%H G. Everest, A. J. van der Poorten, Y. Puri and T. Ward, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL5/Ward/ward2.html">Integer Sequences and Periodic Points</a>, Journal of Integer Sequences, Vol. 5 (2002), Article 02.2.3.
%H G. Everest, Y. Puri and T. Ward, <a href="https://arxiv.org/abs/math/0204173">Integer sequences counting periodic points</a>, arXiv:math/0204173 [math.NT], 2002.
%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 Robert Frontczak, <a href="https://doi.org/10.12988/ijma.2018.712153">Sums of Tribonacci and Tribonacci-Lucas Numbers</a>, International Journal of Mathematical Analysis, Vol. 12 (2018), No. 1, pp. 19-24.
%H Robert Frontczak, <a href="https://doi.org/10.12988/ijma.2018.8429">Convolutions for Generalized Tribonacci Numbers and Related Results</a>, International Journal of Mathematical Analysis (2018) Vol. 12, Issue 7, 307-324.
%H Petros Hadjicostas, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Hadjicostas/hadji2.html">Cyclic Compositions of a Positive Integer with Parts Avoiding an Arithmetic Sequence</a>, Journal of Integer Sequences, 19 (2016), #16.8.2.
%H A. Ilic, S. Klavzar, and Y. Rho, <a href="http://dx.doi.org/10.2298/AADM120108002I">Generalized Lucas Cubes</a>, Appl. An. Disc. Math. 6 (2012) 82-94, proposition 11 for the sequence starting 1, 2, 4, 7, 11,...
%H Günter Köhler, <a href="https://www.fq.math.ca/Scanned/23-1/kohler.pdf">Generating functions of Fibonacci-like sequences and decimal expansion of some fractions</a>, The Fibonacci Quarterly 23, no.1, (1985), 29-35 [a(n) is there Lambda_n on p. 35].
%H Pin-Yen Lin, <a href="http://www.fq.math.ca/Scanned/26-2/lin.pdf">De Moivre type identities for the Tribonacci numbers</a>, The Fibonacci Quarterly 26, no.2, (1988), 131-134.
%H Matthew Macauley, Jon McCammond, and 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 Tony D. Noe and Jonathan Vos Post, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Noe/noe5.html">Primes in Fibonacci n-step and Lucas n-step Sequences</a>, J. of Integer Sequences, Vol. 8 (2005), Article 05.4.4.
%H J. Pan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Pan/pan12.html">Some Properties of the Multiple Binomial Transform and the Hankel Transform of Shifted Sequences</a>, J. Int. Seq. 14 (2011) # 11.3.4, remark 17.
%H Andreas N. Philippou and Spiros D. Dafnis, <a href="https://www.researchgate.net/publication/329752557_A_simple_proof_of_an_identity_generalizing_Fibonacci-Lucas_identities">A simple proof of an identity generalizing Fibonacci-Lucas identities</a>, Fibonacci Quarterly (2018) Vol. 56, No. 4, 334-336.
%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 J. L. Ramírez and V. F. Sirvent, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p38">A Generalization of the k-Bonacci Sequence from Riordan Arrays</a>, The Electronic Journal of Combinatorics, 22(1) (2015), #P1.38.
%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. 17.
%H S. Saito, T. Tanaka, and N. Wakabayashi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Saito/saito22.html">Combinatorial Remarks on the Cyclic Sum Formula for Multiple Zeta Values</a>, J. Int. Seq. 14 (2011) # 11.2.4, Table 3.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CycleGraph.html">Cycle Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DominatingSet.html">Dominating Set</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Lucasn-StepNumber.html">Lucas n-Step Number</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximalIrredundantSet.html">Maximal Irredundant Set</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MinimalEdgeCover.html">Minimal Edge Cover</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SunGraph.html">Sun Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TribonacciNumber.html">Tribonacci Number</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/WebGraph.html">Web Graph</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Companion_matrix">Companion matrix</a>.
%H A. V. Zarelua, <a href="https://doi.org/10.1007/s11006-006-0090-y">On Matrix Analogs of Fermat's Little Theorem</a>, Mathematical Notes, vol. 79, no. 6, 2006, pp. 783-796. Translated from Matematicheskie Zametki, vol. 79, no. 6, 2006, pp. 840-855.
%H L. Zhang and P. Hadjicostas, <a href="http://www.appliedprobability.org/data/files/TMS%20articles/40_2_3.pdf">On sequences of independent Bernoulli trials avoiding the pattern '11..1'</a>, Math. Scientist, 40 (2015), 89-96.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,1).
%F Binet's formula: a(n) = r1^n + r2^n + r3^n, where r1, r2, r3 are the roots of the characteristic polynomial 1 + x + x^2 - x^3, see A058265.
%F a(n) = A000073(n) + 2*A000073(n-1) + 3*A000073(n-2).
%F G.f.: (3-2*x-x^2)/(1-x-x^2-x^3). - _Miklos Kristof_, Jul 29 2002
%F a(n) = n*Sum_{k=1..n} (Sum_{j=n-3*k..k} binomial(j, n-3*k+2*j)* binomial(k,j))/k), n > 0, a(0)=3. - _Vladimir Kruchinin_, Feb 24 2011
%F a(n) = a(n-1) + a(n-2) + a(n-3), a(0)=3, a(1)=1, a(2)=3. - _Harvey P. Dale_, Feb 01 2015
%F a(n) = A073145(-n). for all n in Z. - _Michael Somos_, Dec 17 2016
%F Sum_{k=0..n} k*a(k) = (n*a(n+3) - a(n+2) - (n+1)*a(n+1) + 4)/2. - _Yichen Wang_, Aug 30 2020
%F a(n) = Trace(M^n), where M = [0, 0, 1; 1, 0, 1; 0, 1, 1] is the companion matrix to the monic polynomial x^3 - x^2 - x - 1. It follows that the sequence satisfies the Gauss congruences: a(n*p^r) == a(n*p^(r-1)) (mod p^r) for positive integers n and r and all primes p. See Zarelua. - _Peter Bala_, Dec 29 2022
%e G.f. = 3 + x + 3*x^2 + 7*x^3 + 11*x^4 + 21*x^5 + 39*x^6 + 71*x^7 + 131*x^8 + ...
%p A001644:=-(1+2*z+3*z**2)/(z**3+z**2+z-1); # _Simon Plouffe_ in his 1992 dissertation; gives sequence except for the initial 3
%p A001644 :=proc(n)
%p option remember;
%p if n <= 2 then
%p 1+2*modp(n+1,2)
%p else
%p procname(n-1)+procname(n-2)+procname(n-3);
%p end if;
%p end proc:
%p seq(A001644(n),n=0..80) ;
%t a[x_]:= a[x] = a[x-1] +a[x-2] +a[x-3]; a[0] = 3; a[1] = 1; a[2] = 3; Array[a, 40, 0]
%t a[n_]:= n*Sum[Sum[Binomial[j, n-3*k+2*j]*Binomial[k, j], {j,n-3*k,k}]/k, {k, n}]; a[0] = 3; Array[a, 40, 0] (* _Robert G. Wilson v_, Feb 24 2011 *)
%t LinearRecurrence[{1, 1, 1}, {3, 1, 3}, 40] (* _Vladimir Joseph Stephan Orlovsky_, Feb 08 2012 *)
%t Table[RootSum[-1 - # - #^2 + #^3 &, #^n &], {n, 0, 40}] (* _Eric W. Weisstein_, Mar 30 2017 *)
%t RootSum[-1 - # - #^2 + #^3 &, #^Range[0, 40] &] (* _Eric W. Weisstein_, Aug 17 2017 *)
%o (PARI) {a(n) = if( n<0, polsym(1 - x - x^2 - x^3, -n)[-n+1], polsym(1 + x + x^2 - x^3, n)[n+1])}; /* _Michael Somos_, Nov 02 2002 */
%o (PARI) my(x='x+O('x^40)); Vec((3-2*x-x^2)/(1-x-x^2-x^3)) \\ _Altug Alkan_, Apr 19 2018
%o (Haskell)
%o a001644 n = a001644_list !! n
%o a001644_list = 3 : 1 : 3 : zipWith3 (((+) .) . (+))
%o a001644_list (tail a001644_list) (drop 2 a001644_list)
%o -- _Reinhard Zumkeller_, Apr 13 2014
%o (Magma) I:=[3,1,3]; [n le 3 select I[n] else Self(n-1)+Self(n-2)+ Self(n-3): n in [1..40]]; // _Vincenzo Librandi_, Aug 04 2017
%o (GAP) a:=[3,1,3];; for n in [4..40] do a[n]:=a[n-1]+a[n-2]+a[n-3]; od; a; # _Muniru A Asiru_, Dec 18 2018
%o (SageMath) ((3-2*x-x^2)/(1-x-x^2-x^3)).series(x, 40).coefficients(x, sparse=False) # _G. C. Greubel_, Mar 22 2019
%Y Cf. A000073, A073145, A106293 (Pisano periods), A073728 (partial sums).
%Y Cf. A058265.
%Y Cf. A001609, A001634 - A001636, A001638 - A001645, A001648, A001649.
%K nonn,easy
%O 0,1
%A _N. J. A. Sloane_
%E Edited by Mario Catalani (mario.catalani(AT)unito.it), Jul 17 2002
%E Deleted certain dangerous or potentially dangerous links. - _N. J. A. Sloane_, Jan 30 2021
|
