|
| |
|
|
A027383
|
|
Number of balanced strings of length n: let d(S)= #(1)'s in S - #(0)'s, then S is balanced if every substring T has -2<=d(T)<=2.
|
|
43
| |
|
|
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; 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 (shallit(AT)graceland.uwaterloo.ca), Sep 02 2002
a(n-1) is also the Moore lower bound on the order of a (3,n)-cage. - Eric Weisstein, May 20 2003 and Jason Kimberley, Oct 30 2011
a(n) = sum 2^min(k,n-k), k=0..n
Partial sums of A016116. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Sep 15 2007
Equals row sums of triangle A152201 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 29 2008]
Contribution from John P. McSorley (mcsorley60(AT)hotmail.com), Sep 28 2010: (Start)
a(n)=DPE(n+1) is the total number of k-double-palindromes of n upto 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 upto
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 upto 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)
|
|
|
REFERENCES
| Under misprinted head B3 in Amer Math. Monthly, 104(1997) 753-754.
John P.McSorley: Counting k-compositions of n with palindromic and related structures. Preprint, 2010. [From John P. McSorley (mcsorley60(AT)hotmail.com), Sep 28 2010]
|
|
|
LINKS
| Vincenzo Librandi, Table of n, a(n) for n = 0..5000 Eric Weisstein's World of Mathematics, Cage Graph
Index entries for sequences obtained by enumerating foldings
Index to sequences with linear recurrences with constant coefficients, signature (1,2,-2).
|
|
|
FORMULA
| 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.
2^Floor[(n+2)/2]+2^Floor[(n+1)/2]-2. - Quim Castellsaguer (qcastell(AT)pie.xtec.es).
a(n)=2^(n/2)(3+2sqrt(2)+(3-2sqrt(2))(-1)^n)/2-2. - Paul Barry (pbarry(AT)wit.ie), Apr 23 2004
a(n) = A132340(A052955(n)). - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Aug 20 2007
a(n)=A052955(n+1)-1. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Sep 15 2007
a(n)=A132666(a(n+1))-1. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Sep 15 2007
a(n)=A132666(a(n-1)+1) for n>0. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Sep 15 2007
A132666(a(n))=a(n-1)+1 for n>0 - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Sep 15 2007
G.f.: (1 + x)/((1 - x)*(1 - 2*x^2)). - David Callan (callan(AT)stat.wisc.edu), 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
|
|
|
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
|
|
|
MAPLE
| 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 (zerinvarylajos(AT)yahoo.com), 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}] (* From Jean-François Alcover, Oct 21 2011, after Quim Castellsaguer *)
|
|
|
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
|
|
|
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).
Sequence in context: A001747 A048670 A077625 * A138016 A113118 A032417
Adjacent sequences: A027380 A027381 A027382 * A027384 A027385 A027386
|
|
|
KEYWORD
| nonn,nice,easy,base
|
|
|
AUTHOR
| R. K. Guy (rkg(AT)cpsc.ucalgary.ca)
|
|
|
EXTENSIONS
| More terms from Larry Reeves (larryr(AT)acm.org), Mar 24 2000
|
| |
|
|
