OFFSET
0,1
COMMENTS
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
For n >= 3, also the number of dominating sets on the n-cycle graph C_n. - Eric W. Weisstein, Mar 30 2017
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
For n >= 3, also the number of minimal edge covers in the n-web graph. - Eric W. Weisstein, Aug 03 2017
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
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
REFERENCES
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 500.
G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 1..200 from T. D. Noe)
Kunle Adegoke, Robert Frontczak, and Taras Goy, Binomial Tribonacci Sums, Disc. Math. Lett. (2022) Vol. 8, 30-37.
Kunle Adegoke, Adenike Olatinwo, and Winning Oyekanmi, New Tribonacci Recurrence Relations and Addition Formulas, arXiv:1811.03663 [math.CO], 2018.
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.
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.
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.
Curtis Cooper, Steven Miller, Peter J. C. Moses, Murat Sahin, and Thotsaporn Thanatipanonda, On Identities Of Ruggles, Horadam, Howard, and Young, Preprint, 2016.
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.
M. Elia, Derived Sequences, The Tribonacci Recurrence and Cubic Forms, The Fibonacci Quarterly, 39.2 (2001), 107-109.
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.
G. Everest, Y. Puri and T. Ward, Integer sequences counting periodic points, arXiv:math/0204173 [math.NT], 2002.
Daniel C. Fielder, Special integer sequences controlled by three parameters, Fibonacci Quarterly 6, 1968, 64-70.
Robert Frontczak, Sums of Tribonacci and Tribonacci-Lucas Numbers, International Journal of Mathematical Analysis, Vol. 12 (2018), No. 1, pp. 19-24.
Robert Frontczak, Convolutions for Generalized Tribonacci Numbers and Related Results, International Journal of Mathematical Analysis (2018) Vol. 12, Issue 7, 307-324.
Petros Hadjicostas, Cyclic Compositions of a Positive Integer with Parts Avoiding an Arithmetic Sequence, Journal of Integer Sequences, 19 (2016), #16.8.2.
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,...
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].
Pin-Yen Lin, De Moivre type identities for the Tribonacci numbers, The Fibonacci Quarterly 26, no.2, (1988), 131-134.
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.
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.
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.
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.
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.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
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.
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.
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.
Eric Weisstein's World of Mathematics, Cycle Graph
Eric Weisstein's World of Mathematics, Dominating Set
Eric Weisstein's World of Mathematics, Lucas n-Step Number
Eric Weisstein's World of Mathematics, Maximal Irredundant Set
Eric Weisstein's World of Mathematics, Minimal Edge Cover
Eric Weisstein's World of Mathematics, Sun Graph
Eric Weisstein's World of Mathematics, Tribonacci Number
Eric Weisstein's World of Mathematics, Web Graph
Wikipedia, Companion matrix.
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.
L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern '11..1', Math. Scientist, 40 (2015), 89-96.
Index entries for linear recurrences with constant coefficients, signature (1,1,1).
FORMULA
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.
G.f.: (3-2*x-x^2)/(1-x-x^2-x^3). - Miklos Kristof, Jul 29 2002
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
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
a(n) = A073145(-n). for all n in Z. - Michael Somos, Dec 17 2016
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
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
EXAMPLE
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 + ...
MAPLE
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
A001644 :=proc(n)
option remember;
if n <= 2 then
1+2*modp(n+1, 2)
else
procname(n-1)+procname(n-2)+procname(n-3);
end if;
end proc:
seq(A001644(n), n=0..80) ;
MATHEMATICA
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]
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 *)
LinearRecurrence[{1, 1, 1}, {3, 1, 3}, 40] (* Vladimir Joseph Stephan Orlovsky, Feb 08 2012 *)
Table[RootSum[-1 - # - #^2 + #^3 &, #^n &], {n, 0, 40}] (* Eric W. Weisstein, Mar 30 2017 *)
RootSum[-1 - # - #^2 + #^3 &, #^Range[0, 40] &] (* Eric W. Weisstein, Aug 17 2017 *)
PROG
(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 */
(PARI) my(x='x+O('x^40)); Vec((3-2*x-x^2)/(1-x-x^2-x^3)) \\ Altug Alkan, Apr 19 2018
(Haskell)
a001644 n = a001644_list !! n
a001644_list = 3 : 1 : 3 : zipWith3 (((+) .) . (+))
a001644_list (tail a001644_list) (drop 2 a001644_list)
-- Reinhard Zumkeller, Apr 13 2014
(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
(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
(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
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
EXTENSIONS
Edited by Mario Catalani (mario.catalani(AT)unito.it), Jul 17 2002
Deleted certain dangerous or potentially dangerous links. - N. J. A. Sloane, Jan 30 2021
STATUS
approved