

A027383


a(2*n) = 3*2^n  2; a(2*n+1) = 2^(n+2)  2.


115



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, 4194302, 6291454
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

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.
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) = 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)
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
Also the number of nonsingleton integer compositions of n + 2 with no odd part other than the first or last. Including singletons gives A052955. This is an unsorted (or ordered) version of A351003. The version without even (instead of odd) interior parts is A001911, complement A232580. Note that A000045(n1) counts compositions without odd parts, with nonsingleton case A077896, and A052952/A074331 count nonsingleton compositions without even parts. Also the number of compositions y of n + 1 such that y_i = y_{i+1} for all even i.  Gus Wiseman, Feb 19 2022


REFERENCES

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


LINKS

Leonard F. Klosinski, Gerald L. Alexanderson and Loren C. Larson, Under misprinted head B3, Amer Math. Monthly, 104(1997) 753754.


FORMULA

a(0)=1, a(1)=2; thereafter a(n+2) = 2*a(n) + 2.
a(2n1) = 2^(n+1)  2 = A000918(n+1).
G.f.: (1 + x)/((1  x)*(1  2*x^2)).  David Callan, Jul 22 2008
a(n) = Sum_{k=0..n} 2^min(k, nk).
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
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
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
E.g.f.: 3*cosh(sqrt(2)*x)  2*cosh(x) + 2*sqrt(2)*sinh(sqrt(2)*x)  2*sinh(x).  Stefano Spezia, Apr 06 2022


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.


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 *)
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
(Haskell)
import Data.List (transpose)
a027383 n = a027383_list !! n
a027383_list = concat $ transpose [a033484_list, drop 2 a000918_list]
(Python)
def a(n): return 2**((n+2)//2) + 2**((n+1)//2)  2


CROSSREFS

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).
a(n) = A305540(n+2,2), the second column of the triangle.
Numbers whose binary expansion is a balanced word are A330029.
The complementary compositions are counted by A274230(n1) + 1, with bisections A060867 (even) and A134057 (odd).
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A029744 = {s(n), n>=1}, the numbers 2^k and 3*2^k, as the parent: A029744 (s(n)); A052955 (s(n)1), A027383 (s(n)2), A354788 (s(n)3), A347789 (s(n)4), A209721 (s(n)+1), A209722 (s(n)+2), A343177 (s(n)+3), A209723 (s(n)+4); A060482, A136252 (minor differences from A354788 at the start); A354785 (3*s(n)), A354789 (3*s(n)7). The first differences of A029744 are 1,1,1,2,2,4,4,8,8,... which essentially matches eight sequences: A016116, A060546, A117575, A131572, A152166, A158780, A163403, A320770. The bisections of A029744 are A000079 and A007283.  N. J. A. Sloane, Jul 14 2022


KEYWORD

nonn,nice,easy


AUTHOR



EXTENSIONS

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


STATUS

approved



