A006355 Number of binary vectors of length n containing no singletons.

1, 0, 2, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 466, 754, 1220, 1974, 3194, 5168, 8362, 13530, 21892, 35422, 57314, 92736, 150050, 242786, 392836, 635622, 1028458, 1664080, 2692538, 4356618, 7049156, 11405774, 18454930, 29860704, 48315634

Offset: 0

Author

David M. Bloom

Keywords

• nonn
• easy
• nice

Comments

Number of cvtemplates at n-2 letters given <= 2 consecutive consonants or vowels (n >= 4).

Number of (n,2) Freiman-Wyner sequences.

Diagonal sums of the Riordan array ((1-x+x^2)/(1-x), x/(1-x)), A072405 (where this begins 1,0,1,1,1,1,...). - Paul Barry, May 04 2005

Central terms of the triangle in A094570. - Reinhard Zumkeller, Mar 22 2011

Pisano period lengths: 1, 1, 8, 3, 20, 8, 16, 6, 24, 20, 10, 24, 28, 16, 40, 12, 36, 24, 18, 60, ... . - R. J. Mathar, Aug 10 2012

Also the number of matchings in the (n-2)-pan graph for n >= 5. - Eric W. Weisstein, Oct 03 2017

a(n) is the number of bimultus bitstrings of length n. A bitstring is bimultus if each of its 1's possess at least one neighboring 1 and each of its 0's possess at least one neighboring 0. - Steven Finch, May 26 2020

Examples

			a(6)=10 because we have: 000000, 000011, 000111, 001100, 001111, 110000, 110011, 111000, 111100, 111111. - _Geoffrey Critzer_, Jan 26 2014
		

References

• A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 16, 51.

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 0..4786 (next term has 1001 digits)
• Kassie Archer and Aaron Geary, Powers of permutations that avoid chains of patterns, arXiv:2312.14351 [math.CO], 2023. See p. 15.
• J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124. [Annotated scanned copy]
• Ian F. Blake, The enumeration of certain run length sequences, Information and Control, 55 (1982), 222-237.
• Alexander Burstein, Sergey Kitaev, and Toufik Mansour, Partially ordered patterns and their combinatorial interpretations, PU. M. A. Vol. 19 (2008), No. 2-3, pp. 27-38.
• Steven Finch, Variance of longest run duration in a random bitstring, arXiv:2005.12185 [math.CO], 2020.
• Enoch Haga, Room for Expansion, Word Ways, 33 (No. 2, 2000), pp. 106-113 (see p. 110).
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 898.
• Sergey Kitaev and Jeffrey Remmel, (a,b)-rectangle patterns in permutations and words, arXiv:1304.4286 [math.CO], 2013.
• Thor Martinsen, Non-Fisherian generalized Fibonacci numbers, Notes Num. Theor. Disc. Math. (2025) Vol. 31, No. 2, 370-389. See p. 389.
• Noriaki Sannomiya, Hosho Katsura, and Yu Nakayama, Supersymmetry breaking and Nambu-Goldstone fermions with cubic dispersion, arXiv preprint arXiv:1612.02285 [cond-mat.str-el], 2016-2017. See Table II, line 2.
• Eric Weisstein's World of Mathematics, Independent Edge Set, Matching and Pan Graph.
• Index entries for linear recurrences with constant coefficients, signature (1,1).

Crossrefs

Except for initial term, = 2*Fibonacci numbers (A000045).

Essentially the same as A047992, A054886, A055389, A068922, and A090991.

Column 2 in A265584.

Cf. A094570, A097925, A097926, A118658, A119457.

Programs

Haskell

a006355 n = a006355_list !! n
a006355_list = 1 : fib2s where
   fib2s = 0 : map (+ 1) (scanl (+) 1 fib2s)
-- Reinhard Zumkeller, Mar 20 2013

Magma

[1] cat [Lucas(n) - Fibonacci(n): n in [1..50]]; // Vincenzo Librandi, Aug 02 2014

Maple

a:= n-> if n=0 then 1 else (Matrix([[2,-2]]). Matrix([[1,1], [1,0]])^n) [1,1] fi: seq(a(n), n=0..38); # Alois P. Heinz, Aug 18 2008
a := n -> ifelse(n=0, 1, -2*I^n*ChebyshevU(n-2, -I/2)):
seq(simplify(a(n)), n = 0..38);  # Peter Luschny, Dec 03 2023

Mathematica

Join[{1}, Last[#] - First[#] & /@ Partition[Fibonacci[Range[-1, 40]], 4, 1]] (* Harvey P. Dale, Sep 30 2011 *)
Join[{1}, LinearRecurrence[{1, 1}, {0, 2}, 38]] (* Jean-François Alcover, Sep 23 2017 *)
(* Programs from Eric W. Weisstein, Oct 03 2017 *)
Join[{1}, Table[2 Fibonacci[n], {n, 0, 40}]]
Join[{1}, 2 Fibonacci[Range[0, 40]]]
CoefficientList[Series[(1-x+x^2)/(1-x-x^2), {x, 0, 40}], x] (* End *)

PARI

a(n)=if(n,2*fibonacci(n-1),1) \\ Charles R Greathouse IV, Mar 14 2012

PARI

my(x='x+O('x^50)); Vec((1-x+x^2)/(1-x-x^2)) \\ Altug Alkan, Nov 01 2015

SageMath

def A006355(n): return 2*fibonacci(n-1) - int(n==0)
print([A006355(n) for n in range(51)]) # G. C. Greubel, Apr 18 2025

Formula

a(n+2) = F(n-1) + F(n+2), for n > 0.

G.f.: (1-x+x^2)/(1-x-x^2). - Paul Barry, May 04 2005

a(n) = A119457(n-1,n-2) for n > 2. - Reinhard Zumkeller, May 20 2006

a(n) = 2*F(n-1) for n > 0, F(n)=A000045(n) and a(0)=1. - Mircea Merca, Jun 28 2012

G.f.: 1 - x + x*Q(0), where Q(k) = 1 + x^2 + (2*k+3)*x - x*(2*k+1 + x)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 05 2013

a(n) = A118658(n) - 0^n. - M. F. Hasler, Nov 05 2014

a(n) = 2^(-n)*((1+r)*(1-r)^n - (1-r)*(1+r)^n)/r for n > 0, where r=sqrt(5). - Colin Barker, Jan 28 2017

a(n) = a(n-1) + a(n-2) for n >= 3. - Armend Shabani, Nov 25 2020

E.g.f.: 2*exp(x/2)*(5*cosh(sqrt(5)*x/2) - sqrt(5)*sinh(sqrt(5)*x/2))/5 - 1. - Stefano Spezia, Apr 18 2022

a(n) = F(n-3) + F(n-2) + F(n-1) for n >= 3, where F(n)=A000045(n). - Gergely Földvári, Aug 03 2024

Extensions

Corrected by T. D. Noe, Oct 31 2006