The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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(n-1) 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 k-double-palindromes of n up to cyclic equivalence. See sequence A180918 for the definitions of a k-double-palindrome 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 k-double-palindromes 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 double-palindromes 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 double-palindrome. (End) From Herbert Eberle, Oct 02 2015: (Start) For n > 0, there is a red-black tree of height n with a(n-1) internal nodes and none with less. In order a red-black 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.) Red-black 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 = h-1): a(-1) = 0, a(n) = a(n-1) + 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(n-2) is the number of achiral n-bead 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 cuts-resistance <= 2, where, for the operation of shortening all runs by one, cuts-resistance is the number of applications required to reach an empty word. Explicitly, these are words whose sequence of run-lengths, all of which are 1 or 2, has no odd-length run of 1's sandwiched between two 2's. - Gus Wiseman, Nov 28 2019 Also the number of up-down 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 k-compositions 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. 344-350. - 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) 753-754. Laurent Noé, Spaced seed design on profile HMMs for precise HTS read-mapping efficient sliding window product on the matrix semi-group, in Rapide Bilan 2012-2013, 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 linear recurrences with constant coefficients, signature (1,2,-2). FORMULA a(n) = Sum_{k=0..n} 2^min(k, n-k). a(2n) = 3*2^n - 2 = A033484(n); a(2n-1) = 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) + (3-2*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(n-1)+1) for n > 0. - Hieronymus Fischer, Sep 15 2007 A132666(a(n)) = a(n-1) + 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(n-2)+1) mod (a(n-1)+1) ), n > 1. - Pierre Charland, Dec 12 2010 a(n) = A136252(n-1) + 1, for n > 0. - Jason Kimberley, Nov 01 2011 G.f.: (1+x*R(0))/(1-x), 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(n-1) + 2^floor((n-1)/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:a:=1:for n from 2 to 100 do a[n]:=2*a[n-2]+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+(n-1)/2)-2; Table[a[n], {n, 0, 40}] (* Jean-Franç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 cuts-resistance 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 EXTENSIONS More terms from Larry Reeves (larryr(AT)acm.org), Mar 24 2000 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified April 10 08:09 EDT 2021. Contains 342845 sequences. (Running on oeis4.)