

A027383


Number of balanced strings of length n: let d(S) = #(1's)  #(0's), # == count in S, then S is balanced if every substring T of S has 2 <= d(T) <= 2.


71



1, 2, 4, 6, 10, 14, 22, 30, 46, 62, 94, 126, 190, 254, 382, 510, 766, 1022, 1534, 2046, 3070, 4094, 6142, 8190, 12286, 16382, 24574, 32766, 49150, 65534, 98302, 131070, 196606, 262142, 393214, 524286, 786430, 1048574, 1572862, 2097150, 3145726
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Number of "fold lines" seen when a rectangular piece of paper is folded n+1 times along alternate orthogonal directions and then unfolded.  Quim Castellsaguer (qcastell(AT)pie.xtec.es), Dec 30 1999
Also the number of binary strings with the property that, when scanning from left to right, once the first 1 is seen in position j, there must be a 1 in positions j+2, j+4, ... until the end of the string. (Positions j+1, j+3, ... can be occupied by 0 or 1.)  Jeffrey Shallit, Sep 02 2002
a(n1) is also the Moore lower bound on the order of a (3,n)cage.  Eric W. Weisstein, May 20 2003 and Jason Kimberley, Oct 30 2011
Partial sums of A016116.  Hieronymus Fischer, Sep 15 2007
Equals row sums of triangle A152201.  Gary W. Adamson, Nov 29 2008
From John P. McSorley, Sep 28 2010: (Start)
a(n) = DPE(n+1) is the total number of kdoublepalindromes of n up to cyclic equivalence. See sequence A180918 for the definitions of a kdoublepalindrome of n and of cyclic equivalence. Sequence A180918 is the 'DPE(n,k)' triangle read by rows where DPE(n,k) is the number of kdoublepalindromes of n up to cyclic equivalence. For example, we have a(4) = DPE(5) = DPE(5,1) + DPE(5,2) + DPE(5,3) + DPE(5,4) + DPE(5,5) = 0 + 2 + 2 + 1 + 1 = 6.
The 6 doublepalindromes of 5 up to cyclic equivalence are 14, 23, 113, 122, 1112, 11111. They come from cyclic equivalence classes {14,41}, {23,32}, {113,311,131}, {122,212,221}, {1112,2111,1211,1121}, and {11111}. Hence a(n)=DPE(n+1) is the total number of cyclic equivalence classes of n containing at least one doublepalindrome.
(End)
From Herbert Eberle, Oct 02 2015: (Start)
For n > 0, there is a redblack tree of height n with a(n1) internal nodes and none with less.
In order a redblack tree of given height has minimal number of nodes, it has exactly 1 path with strictly alternating red and black nodes. All nodes outside this height defining path are black.
Consider:
mrbt5 R
/ \
/ \
/ \
/ B
/ / \
mrbt4 B / B
/ \ B E E
/ B E E
mrbt3 R E E
/ \
/ B
mrbt2 B E E
/ E
mrbt1 R
E E
(Red nodes shown as R, blacks as B, externals as E.)
Redblack trees mrbt1, mrbt2, mrbt3, mrbt4, mrbt5 of respective heights h = 1, 2, 3, 4, 5; all minimal in the number of internal nodes, namely 1, 2, 4, 6, 10.
Recursion (let n = h1): a(1) = 0, a(n) = a(n1) + 2^floor(n/2), n >= 0.
(End)
Also the number of strings of length n with the digits 1 and 2 with the property that the sum of the digits of all substrings of uneven length is not divisible by 3. An example with length 8 is 21221121.  Herbert Kociemba, Apr 29 2017
a(n2) is the number of achiral nbead necklaces or bracelets using exactly two colors. For n=4, the four arrangements are AAAB, AABB, ABAB, and ABBB.  Robert A. Russell, Sep 26 2018
Partial sums of powers of 2 repeated 2 times, like A200672 where is 3 times.  Yuchun Ji, Nov 16 2018
Also the number of binary words of length n with cutsresistance <= 2, where, for the operation of shortening all runs by one, cutsresistance is the number of applications required to reach an empty word. Explicitly, these are words whose sequence of runlengths, all of which are 1 or 2, has no oddlength run of 1's sandwiched between two 2's.  Gus Wiseman, Nov 28 2019
Also the number of updown paths with n steps such that the height difference between the highest and lowest points is at most 2.  Jeremy Dover, Jun 17 2020


REFERENCES

John P. McSorley: Counting kcompositions of n with palindromic and related structures. Preprint, 2010. [John P. McSorley, Sep 28 2010]


LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..5000
J. Jordan and R. Southwell, Further Properties of Reproducing Graphs, Applied Mathematics, Vol. 1 No. 5, 2010, pp. 344350.  From N. J. A. Sloane, Feb 03 2013
Leonard F. Klosinski, Gerald L. Alexanderson and Loren C. Larson, Under misprinted head B3, Amer Math. Monthly, 104(1997) 753754.
Laurent Noé, Spaced seed design on profile HMMs for precise HTS readmapping efficient sliding window product on the matrix semigroup, in Rapide Bilan 20122013, LIFL, Université Lille 1  INRIA Journées au vert 11 et 12 juin 2013.
Eric Weisstein's World of Mathematics, Cage Graph
Index entries for sequences obtained by enumerating foldings
Index entries for linear recurrences with constant coefficients, signature (1,2,2).


FORMULA

a(n) = Sum_{k=0..n} 2^min(k, nk).
a(2n) = 3*2^n  2 = A033484(n);
a(2n1) = 2^(n+1)  2 = A000918(n+1).
a(n+2) = 2*a(n) + 2.
a(n) = 2^floor((n+2)/2) + 2^floor((n+1)/2)  2.  Quim Castellsaguer (qcastell(AT)pie.xtec.es)
a(n) = 2^(n/2)*(3 + 2*sqrt(2) + (32*sqrt(2))*(1)^n)/2  2.  Paul Barry, Apr 23 2004
a(n) = A132340(A052955(n)).  Reinhard Zumkeller, Aug 20 2007
a(n) = A052955(n+1)  1.  Hieronymus Fischer, Sep 15 2007
a(n) = A132666(a(n+1))  1.  Hieronymus Fischer, Sep 15 2007
a(n) = A132666(a(n1)+1) for n > 0.  Hieronymus Fischer, Sep 15 2007
A132666(a(n)) = a(n1) + 1 for n > 0.  Hieronymus Fischer, Sep 15 2007
G.f.: (1 + x)/((1  x)*(1  2*x^2)).  David Callan, Jul 22 2008
a(n) = 2*( (a(n2)+1) mod (a(n1)+1) ), n > 1.  Pierre Charland, Dec 12 2010
a(n) = A136252(n1) + 1, for n > 0.  Jason Kimberley, Nov 01 2011
G.f.: (1+x*R(0))/(1x), where R(k)= 1 + 2*x/( 1  x/(x + 1/R(k+1) )); (continued fraction).  Sergei N. Gladkovskii, Aug 16 2013
a(n) = 2^((2*n + 3*(1(1)^n))/4)*3^((1+(1)^n)/2)  2.  Luce ETIENNE, Sep 01 2014
a(n) = a(n1) + 2^floor((n1)/2) for n>0, a(0)=1.  Yuchun Ji, Nov 23 2018


EXAMPLE

After 3 folds one sees 4 fold lines.
Example: a(3) = 6 because the strings 001, 010, 100, 011, 101, 110 have the property.
Binary: 1, 10, 100, 110, 1010, 1110, 10110, 11110, 101110, 111110, 1011110, 1111110, 10111110, 11111110, 101111110, 111111110, 1011111110, 1111111110, 10111111110, ...  Jason Kimberley, Nov 02 2011
Example: Partial sums of powers of 2 repeated 2 times:
a(3) = 1+1+2 = 4.
a(4) = 1+1+2+2 = 6
a(5) = 1+1+2+2+4 = 10
Yuchun Ji, Nov 16 2018


MAPLE

a[0]:=0:a[1]:=1:for n from 2 to 100 do a[n]:=2*a[n2]+2 od: seq(a[n], n=1..41); # Zerinvary Lajos, Mar 16 2008


MATHEMATICA

a[n_?EvenQ] := 3*2^(n/2)2; a[n_?OddQ] := 2^(2+(n1)/2)2; Table[a[n], {n, 0, 40}] (* JeanFrançois Alcover, Oct 21 2011, after Quim Castellsaguer *)
LinearRecurrence[{1, 2, 2}, {1, 2, 4}, 41] (* Robert G. Wilson v, Oct 06 2014 *)
Table[Length[Select[Tuples[{0, 1}, n], And[Max@@Length/@Split[#]<=2, !MatchQ[Length/@Split[#], {___, 2, ins:1.., 2, ___}/; OddQ[Plus[ins]]]]&]], {n, 0, 15}] (* Gus Wiseman, Nov 28 2019 *)


PROG

(MAGMA) [2^Floor((n+2)/2)+2^Floor((n+1)/2)2: n in [0..50]]; // Vincenzo Librandi, Aug 16 2011
(PARI) a(n)=2^(n\2+1)+2^((n+1)\2)2 \\ Charles R Greathouse IV, Oct 21 2011
(Haskell)
import Data.List (transpose)
a027383 n = a027383_list !! n
a027383_list = concat $ transpose [a033484_list, drop 2 a000918_list]
 Reinhard Zumkeller, Jun 17 2015


CROSSREFS

Cf. A132666, A152201.
Moore lower bound on the order of a (k,g) cage: A198300 (square); rows: A000027 (k=2), this sequence (k=3), A062318 (k=4), A061547 (k=5), A198306 (k=6), A198307 (k=7), A198308 (k=8), A198309 (k=9), A198310 (k=10), A094626 (k=11); columns: A020725 (g=3), A005843 (g=4), A002522 (g=5), A051890 (g=6), A188377 (g=7).  Jason Kimberley, Oct 30 2011
Cf. A000066 (actual order of a (3,g)cage).
Cf. A000918, A033484.
a(n) = A305540(n+2,2), the second column of the triangle.
Numbers whose binary expansion is a balanced word are A330029.
Binary words counted by cutsresistance are A319421 or A329860.
Cf. A000975, A062011, A329862, A329863.
Sequence in context: A307889 A239951 A077625 * A280611 A138016 A239787
Adjacent sequences: A027380 A027381 A027382 * A027384 A027385 A027386


KEYWORD

nonn,nice,easy,base


AUTHOR

R. K. Guy


EXTENSIONS

More terms from Larry Reeves (larryr(AT)acm.org), Mar 24 2000


STATUS

approved



