login
This site is supported by donations to The OEIS Foundation.

 

Logo

The OEIS is looking to hire part-time people to help edit core sequences, upload scanned documents, process citations, fix broken links, etc. - Neil Sloane, njasloane@gmail.com

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001644 a(n) = a(n-1) + a(n-2) + a(n-3), a(0)=3, a(1)=1, a(2)=3.
(Formerly M2625 N1040)
69
3, 1, 3, 7, 11, 21, 39, 71, 131, 241, 443, 815, 1499, 2757, 5071, 9327, 17155, 31553, 58035, 106743, 196331, 361109, 664183, 1221623, 2246915, 4132721, 7601259, 13980895, 25714875, 47297029, 86992799, 160004703, 294294531, 541292033, 995591267, 1831177831 (list; graph; refs; listen; history; text; internal format)
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 proven 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

REFERENCES

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).

L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern '11..1', Math. Scientist, 40 (2015), 89-96.

LINKS

G. C. Greubel, Table of n, a(n) for n = 0..1000[Terms 1 through 200 were computed by T. D. Noe; terms 201 to 1000 by G. C. Greubel, Oct 27 2016]

Daniel Birmajer, Juan B. Gil, Michael D. Weiner, Linear recurrence sequences with indices in arithmetic progression and their sums, arXiv:1505.06339 [math.NT], 2015.

Martin Burtscher, Igor Szczyrba, 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.

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.

A. Ilic, S. Klavzar, Y. Rho, Generalized Lucas Cubes, Appl. An. Disc. Math. 6 (2012) 82-94, proposition 11 for the sequence starting 1, 2, 4, 7, 11,...

Pin-Yen Lin, De Moivre type identities for the Tribonacci numbers, The Fibonacci Quarterly 26, no.2, (1988), 131-134

Matthew Macauley , Jon McCammond, 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

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

J. L. Ramírez, V. F. Sirvent, A Generalization of the k-Bonacci Sequence from Riordan Arrays, The Electronic Journal of Combinatorics, 22(1) (2015), #P1.38.

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, Tribonacci Number

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.

a(n) = A000073(n) + 2*A000073(n-1) + 3*A000073(n-2).

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(0)=3, a(1)=1, a(2)=3, a(n) = a(n-1)+a(n-2)+a(n-3). - Harvey P. Dale, Feb 01 2015

a(n) = A073145(-n). for all n in Z. - Michael Somos, Dec 17 2016

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

MATHEMATICA

f[x_] := f[x] = f[x - 1] + f[x - 2] + f[x - 3]; f[0] = 3; f[1] = 1; f[2] = 3

f[n_] := n*Sum[ Sum[ Binomial[j, n - 3*k + 2*j]*Binomial[k, j], {j, n - 3*k, k}]/k, {k, n}]; f[0] = 3; Array[f, 34, 0]

LinearRecurrence[{1, 1, 1}, {3, 1, 3}, 60] (* Vladimir Joseph Stephan Orlovsky, Feb 08 2012 *)

Table[RootSum[-1 - # - #^2 + #^3 &, #^n &], {n, 0, 20}] (* Eric W. Weisstein, Mar 30 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 */

(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

CROSSREFS

Cf. A000073, A073145, A106293 (Pisano periods).

Cf. A058265.

Sequence in context: A064434 A086401 A095732 * A139123 A133580 A019603

Adjacent sequences:  A001641 A001642 A001643 * A001645 A001646 A001647

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane, Apr 30 1991

EXTENSIONS

Edited by Mario Catalani (mario.catalani(AT)unito.it), Jul 17 2002

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 29 10:48 EDT 2017. Contains 287246 sequences.