cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A001644 a(n) = a(n-1) + a(n-2) + a(n-3), a(0)=3, a(1)=1, a(2)=3.

Original entry on oeis.org

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
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

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

Examples

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

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

Crossrefs

Cf. A000073, A073145, A106293 (Pisano periods), A073728 (partial sums).
Cf. A058265.
Cf. A001609, A001634 - A001636, A001638 - A001645, A001648, A001649.

Programs

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

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(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

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

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.