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

 

Logo

"Email this user" was broken Aug 14 to 9am Aug 16. If you sent someone a message in this period, please send it again.

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

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

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]

Curtis Cooper, S. Miller, P. J. C. Moses, M. Sahin, et al., On Identities Of Ruggles, Horadam, Howard, and Young, Preprint, 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

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.

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.

S. Saito, T. Tanaka, 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

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

RootSum[-1 - # - #^2 + #^3 &, #^Range[0, 20] &] (* 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 */

(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

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,changed

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 August 20 20:09 EDT 2017. Contains 290837 sequences.