# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/ Search: id:a001644 Showing 1-1 of 1 %I A001644 M2625 N1040 #262 Apr 04 2024 10:32:21 %S A001644 3,1,3,7,11,21,39,71,131,241,443,815,1499,2757,5071,9327,17155,31553, %T A001644 58035,106743,196331,361109,664183,1221623,2246915,4132721,7601259, %U A001644 13980895,25714875,47297029,86992799,160004703,294294531,541292033,995591267,1831177831 %N A001644 a(n) = a(n-1) + a(n-2) + a(n-3), a(0)=3, a(1)=1, a(2)=3. %C A001644 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 A001644 For n >= 3, also the number of dominating sets on the n-cycle graph C_n. - _Eric W. Weisstein_, Mar 30 2017 %C A001644 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 A001644 For n >= 3, also the number of minimal edge covers in the n-web graph. - _Eric W. Weisstein_, Aug 03 2017 %C A001644 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 A001644 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 A001644 Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 500. %D A001644 G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255. %D A001644 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence). %D A001644 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). %H A001644 G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 1..200 from T. D. Noe) %H A001644 Kunle Adegoke, Robert Frontczak, and Taras Goy, Binomial Tribonacci Sums, Disc. Math. Lett. (2022) Vol. 8, 30-37. %H A001644 Kunle Adegoke, Adenike Olatinwo, and Winning Oyekanmi, New Tribonacci Recurrence Relations and Addition Formulas, arXiv:1811.03663 [math.CO], 2018. %H A001644 Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, Linear recurrence sequences with indices in arithmetic progression and their sums, arXiv:1505.06339 [math.NT], 2015. %H A001644 Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5. %H A001644 C. A. Charalambides, Lucas numbers and polynomials of order k and the length of the longest circular success run, The Fibonacci Quarterly, 29 (1991), 290-297. %H A001644 Curtis Cooper, Steven Miller, Peter J. C. Moses, Murat Sahin, and Thotsaporn Thanatipanonda, On Identities Of Ruggles, Horadam, Howard, and Young, Preprint, 2016. %H A001644 Curtis Cooper, Steven Miller, Peter J. C. Moses, Murat Sahin, and Thotsaporn Thanatipanonda, On identities of Ruggles, Hradam, Howard, and Young, The Fibonacci Quarterly, 55.5 (2017), 42-65. %H A001644 M. Elia, Derived Sequences, The Tribonacci Recurrence and Cubic Forms, The Fibonacci Quarterly, 39.2 (2001), 107-109. %H A001644 G. Everest, A. J. van der Poorten, Y. Puri and T. Ward, Integer Sequences and Periodic Points, Journal of Integer Sequences, Vol. 5 (2002), Article 02.2.3. %H A001644 G. Everest, Y. Puri and T. Ward, Integer sequences counting periodic points, arXiv:math/0204173 [math.NT], 2002. %H A001644 Daniel C. Fielder, Special integer sequences controlled by three parameters, Fibonacci Quarterly 6, 1968, 64-70. %H A001644 Robert Frontczak, Sums of Tribonacci and Tribonacci-Lucas Numbers, International Journal of Mathematical Analysis, Vol. 12 (2018), No. 1, pp. 19-24. %H A001644 Robert Frontczak, Convolutions for Generalized Tribonacci Numbers and Related Results, International Journal of Mathematical Analysis (2018) Vol. 12, Issue 7, 307-324. %H A001644 Petros Hadjicostas, Cyclic Compositions of a Positive Integer with Parts Avoiding an Arithmetic Sequence, Journal of Integer Sequences, 19 (2016), #16.8.2. %H A001644 A. Ilic, S. Klavzar, and Y. Rho, Generalized Lucas Cubes, Appl. An. Disc. Math. 6 (2012) 82-94, proposition 11 for the sequence starting 1, 2, 4, 7, 11,... %H A001644 Günter Köhler, Generating functions of Fibonacci-like sequences and decimal expansion of some fractions, The Fibonacci Quarterly 23, no.1, (1985), 29-35 [a(n) is there Lambda_n on p. 35]. %H A001644 Pin-Yen Lin, De Moivre type identities for the Tribonacci numbers, The Fibonacci Quarterly 26, no.2, (1988), 131-134. %H A001644 Matthew Macauley, Jon McCammond, and Henning S. Mortveit, Dynamics groups of asynchronous cellular automata, Journal of Algebraic Combinatorics, Vol 33, No 1 (2011), pp. 11-35. %H A001644 Tony D. Noe and Jonathan Vos Post, Primes in Fibonacci n-step and Lucas n-step Sequences, J. of Integer Sequences, Vol. 8 (2005), Article 05.4.4. %H A001644 J. Pan, Some Properties of the Multiple Binomial Transform and the Hankel Transform of Shifted Sequences, J. Int. Seq. 14 (2011) # 11.3.4, remark 17. %H A001644 Andreas N. Philippou and Spiros D. Dafnis, A simple proof of an identity generalizing Fibonacci-Lucas identities, Fibonacci Quarterly (2018) Vol. 56, No. 4, 334-336. %H A001644 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. %H A001644 Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992 %H A001644 J. L. Ramírez and V. F. Sirvent, A Generalization of the k-Bonacci Sequence from Riordan Arrays, The Electronic Journal of Combinatorics, 22(1) (2015), #P1.38. %H A001644 Souvik Roy, Nazim Fatès, and Sukanta Das, Reversibility of Elementary Cellular Automata with fully asynchronous updating: an analysis of the rules with partial recurrence, hal-04456320 [nlin.CG], [cs], 2024. See p. 17. %H A001644 S. Saito, T. Tanaka, and N. Wakabayashi, Combinatorial Remarks on the Cyclic Sum Formula for Multiple Zeta Values, J. Int. Seq. 14 (2011) # 11.2.4, Table 3. %H A001644 Eric Weisstein's World of Mathematics, Cycle Graph %H A001644 Eric Weisstein's World of Mathematics, Dominating Set %H A001644 Eric Weisstein's World of Mathematics, Lucas n-Step Number %H A001644 Eric Weisstein's World of Mathematics, Maximal Irredundant Set %H A001644 Eric Weisstein's World of Mathematics, Minimal Edge Cover %H A001644 Eric Weisstein's World of Mathematics, Sun Graph %H A001644 Eric Weisstein's World of Mathematics, Tribonacci Number %H A001644 Eric Weisstein's World of Mathematics, Web Graph %H A001644 Wikipedia, Companion matrix. %H A001644 A. V. Zarelua, On Matrix Analogs of Fermat's Little Theorem, Mathematical Notes, vol. 79, no. 6, 2006, pp. 783-796. Translated from Matematicheskie Zametki, vol. 79, no. 6, 2006, pp. 840-855. %H A001644 L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern '11..1', Math. Scientist, 40 (2015), 89-96. %H A001644 Index entries for linear recurrences with constant coefficients, signature (1,1,1). %F A001644 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 A001644 a(n) = A000073(n) + 2*A000073(n-1) + 3*A000073(n-2). %F A001644 G.f.: (3-2*x-x^2)/(1-x-x^2-x^3). - _Miklos Kristof_, Jul 29 2002 %F A001644 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 A001644 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 A001644 a(n) = A073145(-n). for all n in Z. - _Michael Somos_, Dec 17 2016 %F A001644 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 A001644 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 A001644 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 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 A001644 :=proc(n) %p A001644 option remember; %p A001644 if n <= 2 then %p A001644 1+2*modp(n+1,2) %p A001644 else %p A001644 procname(n-1)+procname(n-2)+procname(n-3); %p A001644 end if; %p A001644 end proc: %p A001644 seq(A001644(n),n=0..80) ; %t A001644 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 A001644 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 A001644 LinearRecurrence[{1, 1, 1}, {3, 1, 3}, 40] (* _Vladimir Joseph Stephan Orlovsky_, Feb 08 2012 *) %t A001644 Table[RootSum[-1 - # - #^2 + #^3 &, #^n &], {n, 0, 40}] (* _Eric W. Weisstein_, Mar 30 2017 *) %t A001644 RootSum[-1 - # - #^2 + #^3 &, #^Range[0, 40] &] (* _Eric W. Weisstein_, Aug 17 2017 *) %o A001644 (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 A001644 (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 A001644 (Haskell) %o A001644 a001644 n = a001644_list !! n %o A001644 a001644_list = 3 : 1 : 3 : zipWith3 (((+) .) . (+)) %o A001644 a001644_list (tail a001644_list) (drop 2 a001644_list) %o A001644 -- _Reinhard Zumkeller_, Apr 13 2014 %o A001644 (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 A001644 (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 A001644 (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 A001644 Cf. A000073, A073145, A106293 (Pisano periods), A073728 (partial sums). %Y A001644 Cf. A058265. %Y A001644 Cf. A001609, A001634 - A001636, A001638 - A001645, A001648, A001649. %K A001644 nonn,easy %O A001644 0,1 %A A001644 _N. J. A. Sloane_ %E A001644 Edited by Mario Catalani (mario.catalani(AT)unito.it), Jul 17 2002 %E A001644 Deleted certain dangerous or potentially dangerous links. - _N. J. A. Sloane_, Jan 30 2021 # Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE