|
%I #177 Aug 14 2022 15:28:12
%S 1,2,4,6,10,14,22,30,46,62,94,126,190,254,382,510,766,1022,1534,2046,
%T 3070,4094,6142,8190,12286,16382,24574,32766,49150,65534,98302,131070,
%U 196606,262142,393214,524286,786430,1048574,1572862,2097150,3145726,4194302,6291454
%N a(2*n) = 3*2^n - 2; a(2*n+1) = 2^(n+2) - 2.
%C 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.
%C 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
%C 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
%C 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
%C Partial sums of A016116. - _Hieronymus Fischer_, Sep 15 2007
%C Equals row sums of triangle A152201. - _Gary W. Adamson_, Nov 29 2008
%C From _John P. McSorley_, Sep 28 2010: (Start)
%C 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.
%C 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.
%C (End)
%C From _Herbert Eberle_, Oct 02 2015: (Start)
%C For n > 0, there is a red-black tree of height n with a(n-1) internal nodes and none with less.
%C 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.
%C Consider:
%C mrbt5 R
%C / \
%C / \
%C / \
%C / B
%C / / \
%C mrbt4 B / B
%C / \ B E E
%C / B E E
%C mrbt3 R E E
%C / \
%C / B
%C mrbt2 B E E
%C / E
%C mrbt1 R
%C E E
%C (Red nodes shown as R, blacks as B, externals as E.)
%C 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.
%C Recursion (let n = h-1): a(-1) = 0, a(n) = a(n-1) + 2^floor(n/2), n >= 0.
%C (End)
%C 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
%C 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
%C Partial sums of powers of 2 repeated 2 times, like A200672 where is 3 times. - _Yuchun Ji_, Nov 16 2018
%C 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
%C 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
%C Also the number of non-singleton 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(n-1) counts compositions without odd parts, with non-singleton case A077896, and A052952/A074331 count non-singleton 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
%D John P. McSorley: Counting k-compositions of n with palindromic and related structures. Preprint, 2010. [_John P. McSorley_, Sep 28 2010]
%H Vincenzo Librandi, <a href="/A027383/b027383.txt">Table of n, a(n) for n = 0..5000</a>
%H J. Jordan and R. Southwell, <a href="http://dx.doi.org/10.4236/am.2010.15045">Further Properties of Reproducing Graphs</a>, Applied Mathematics, Vol. 1 No. 5, 2010, pp. 344-350. - From _N. J. A. Sloane_, Feb 03 2013
%H Leonard F. Klosinski, Gerald L. Alexanderson and Loren C. Larson, <a href="http://www.jstor.org/stable/2975240">Under misprinted head B3</a>, Amer Math. Monthly, 104(1997) 753-754.
%H Laurent Noé, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.258.5910">Spaced seed design on profile HMMs for precise HTS read-mapping efficient sliding window product on the matrix semi-group</a>, in Rapide Bilan 2012-2013, LIFL, Université Lille 1 - INRIA Journées au vert 11 et 12 juin 2013.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CageGraph.html">Cage Graph</a>
%H <a href="/index/Fo#fold">Index entries for sequences obtained by enumerating foldings</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,2,-2).
%F a(0)=1, a(1)=2; thereafter a(n+2) = 2*a(n) + 2.
%F a(2n) = 3*2^n - 2 = A033484(n);
%F a(2n-1) = 2^(n+1) - 2 = A000918(n+1).
%F G.f.: (1 + x)/((1 - x)*(1 - 2*x^2)). - _David Callan_, Jul 22 2008
%F a(n) = Sum_{k=0..n} 2^min(k, n-k).
%F a(n) = 2^floor((n+2)/2) + 2^floor((n+1)/2) - 2. - Quim Castellsaguer (qcastell(AT)pie.xtec.es)
%F a(n) = 2^(n/2)*(3 + 2*sqrt(2) + (3-2*sqrt(2))*(-1)^n)/2 - 2. - _Paul Barry_, Apr 23 2004
%F a(n) = A132340(A052955(n)). - _Reinhard Zumkeller_, Aug 20 2007
%F a(n) = A052955(n+1) - 1. - _Hieronymus Fischer_, Sep 15 2007
%F a(n) = A132666(a(n+1)) - 1. - _Hieronymus Fischer_, Sep 15 2007
%F a(n) = A132666(a(n-1)+1) for n > 0. - _Hieronymus Fischer_, Sep 15 2007
%F A132666(a(n)) = a(n-1) + 1 for n > 0. - _Hieronymus Fischer_, Sep 15 2007
%F G.f.: (1 + x)/((1 - x)*(1 - 2*x^2)). - _David Callan_, Jul 22 2008
%F a(n) = 2*( (a(n-2)+1) mod (a(n-1)+1) ), n > 1. - _Pierre Charland_, Dec 12 2010
%F a(n) = A136252(n-1) + 1, for n > 0. - _Jason Kimberley_, Nov 01 2011
%F 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
%F a(n) = 2^((2*n + 3*(1-(-1)^n))/4)*3^((1+(-1)^n)/2) - 2. - _Luce ETIENNE_, Sep 01 2014
%F a(n) = a(n-1) + 2^floor((n-1)/2) for n>0, a(0)=1. - _Yuchun Ji_, Nov 23 2018
%F 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
%e After 3 folds one sees 4 fold lines.
%e Example: a(3) = 6 because the strings 001, 010, 100, 011, 101, 110 have the property.
%e 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
%e Example: Partial sums of powers of 2 repeated 2 times:
%e a(3) = 1+1+2 = 4;
%e a(4) = 1+1+2+2 = 6;
%e a(5) = 1+1+2+2+4 = 10.
%e _Yuchun Ji_, Nov 16 2018
%p a[0]:=0:a[1]:=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
%t 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 *)
%t LinearRecurrence[{1, 2, -2}, {1, 2, 4}, 41] (* _Robert G. Wilson v_, Oct 06 2014 *)
%t 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 *)
%o (Magma) [2^Floor((n+2)/2)+2^Floor((n+1)/2)-2: n in [0..50]]; // _Vincenzo Librandi_, Aug 16 2011
%o (PARI) a(n)=2^(n\2+1)+2^((n+1)\2)-2 \\ _Charles R Greathouse IV_, Oct 21 2011
%o (Haskell)
%o import Data.List (transpose)
%o a027383 n = a027383_list !! n
%o a027383_list = concat $ transpose [a033484_list, drop 2 a000918_list]
%o -- _Reinhard Zumkeller_, Jun 17 2015
%o (Python)
%o def a(n): return 2**((n+2)//2) + 2**((n+1)//2) - 2
%o print([a(n) for n in range(43)]) # _Michael S. Branicky_, Feb 19 2022
%Y Cf. A132666, A152201.
%Y 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
%Y Cf. A000066 (actual order of a (3,g)-cage).
%Y Bisections are A033484 (even) and A000918 (odd).
%Y a(n) = A305540(n+2,2), the second column of the triangle.
%Y Numbers whose binary expansion is a balanced word are A330029.
%Y Binary words counted by cuts-resistance are A319421 or A329860.
%Y Cf. A000975, A062011, A329862, A329863.
%Y The complementary compositions are counted by A274230(n-1) + 1, with bisections A060867 (even) and A134057 (odd).
%Y Cf. A000346, A000984, A001405, A001700, A011782 (compositions).
%Y 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
%K nonn,nice,easy
%O 0,2
%A _R. K. Guy_
%E More terms from Larry Reeves (larryr(AT)acm.org), Mar 24 2000
%E Replaced definition with a simpler one. - _N. J. A. Sloane_, Jul 09 2022
|
