A001644 - OEIS (original) (raw)

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

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

For n >= 4, a(n) is the nearest integer to x^n, where x = 1.839286755214161132551... (A058265). - Lee A. Newberg, Oct 31 2025

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

Kunle Adegoke, Robert Frontczak, and Taras Goy, Binomial Tribonacci Sums, Disc. Math. Lett. (2022) Vol. 8, 30-37.

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.

Graham Everest, Alfred J. van der Poorten, Yash Puri and Thomas Ward, Integer Sequences and Periodic Points, Journal of Integer Sequences, Vol. 5 (2002), Article 02.2.3.

Aleksandar Ilić, Sandi Klavžar, and Yoomi Rho, Generalized Lucas Cubes, Appl. An. Disc. Math. 6 (2012) 82-94, proposition 11 for the sequence starting 1, 2, 4, 7, 11,...

Eurico Ruivo, Pedro Paulo Balbi, Kévin Perrot, Marco Montalva-Medel, and Eric Goles, Exploring one-dimensional, binary, radius-2 cellular automata, over cyclic configurations, in terms of their ability to solve decision problems by distributed consensus, arXiv:2510.01040 [cs.DM], 2025. See p. 17.

Eric Weisstein's World of Mathematics, Cycle Graph

Eric Weisstein's World of Mathematics, Sun Graph

Eric Weisstein's World of Mathematics, Web Graph

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.

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

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

Sum_{i=1..n-1} a(i)*a(n-i) = n*a(n) - (T(n+1) + 4*T(n) + 9*T(n-1)) for T(n) = A000073(n). - Greg Dresden, Feb 13 2026

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

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:

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

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)

(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

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