|
| |
|
|
A000975
|
|
a(2n) = 2*a(2n-1), a(2n+1) = 2*a(2n)+1 (also n-th number without consecutive equal binary digits).
|
|
93
| |
|
|
0, 1, 2, 5, 10, 21, 42, 85, 170, 341, 682, 1365, 2730, 5461, 10922, 21845, 43690, 87381, 174762, 349525, 699050, 1398101, 2796202, 5592405, 11184810, 22369621, 44739242, 89478485, 178956970, 357913941, 715827882, 1431655765, 2863311530
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| Comments from Jon Stadler (jstadler(AT)coastal.edu): Number of steps to change from a binary string of n 0's to n 1's using a Gray code.
Popular puzzles such as Spin-Out and The Brain Puzzler are based on the Gray binary system and require a(n) steps to complete for some number n.
Antti Karttunen: Not yet proved: a(n) gives also all j for which A048702(j) = A000217(j), i.e. if we take a(n)-th triangular number (a(n)^2+a(n))/2 and multiply it by 3, we get a(n)-th even-length binary palindrome A048701(a(n)) concatenated from a(n) and its reverse. E.g. a(4) = 10, 1010 in binary, the tenth triangular number is 55, * 3 = 165 = 10100101 in binary.
Number of ways to tie a tie of n or fewer half turns, excluding mirror images. Also number of walks of length n or less on a triangular lattice with the following restrictions; given l, r and c as the lattice axes. 1. All steps are taken in the positive axis direction. 2. No two consecutive steps are taken on the same axis. 3. All walks begin with l. 4. All walks end with rlc or lrc - Bill Blewett (billble(AT)microsoft.com), Dec 21 2000
a(n) = minimal number of vertices to be selected in a vertex-cover of the balanced tree B_n. - Sen-Peng Eu (giawgwan(AT)single.url.com.tw), Jun 15 2002
A087117(a(n)) = A038374(a(n)) = 1 for n>1; see also A090050. - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Nov 20 2003
Intersection of A003754 and A003714; complement of A107911; a(n) = A107909(A104161(n)); A007088(a(n)) = A056830(n). - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), May 28 2005
a(n+1) gives row sums of Riordan array (1/(1-x),x(1+2x)). - Paul Barry (pbarry(AT)wit.ie), Jul 18 2005
Total number of initial 01's in all binary words of length n+1. Example: a(3)=5 because the binary words of length 4 that start with 01 are (01)00, (01)(01), (01)10 and (01)11 and the total number of initial 01's is 5 (shown between parentheses). a(n)=Sum(k*A119440(n+1,k),k>=0). - Emeric Deutsch (deutsch(AT)duke.poly.edu), May 19 2006
2^n = 2*A005578(n-1) + 2*A001045(n) + 2*a(n-2). - Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 25 2007
Comment from Hans Isdahl (hansi(AT)nordtroms.net), Jan 07 2008: In Norway we call the 10-ring puzzle "strikketoy" or "knitwear" (see link). It takes 682 moves to free the two parts.
Equals A002450 and A020988 interlaced. - Zak Seidov, Feb 10 2008
For n > 1, let B_n = the complete binary tree with vertex set V where |V| = 2^n - 1. If VC is a minimum-size vertex cover of B_n, Sen-Peng Eu points out that a(n) = |VC|. It also follows that if IS = V\VC, a(n+1) = |IS|. [From Kailasam Viswanathan Iyer (kvi(AT)nitt.edu), Apr 13 2009]
Starting with 1 and convolved with [1, 2, 2, 2,...] = A000295. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Jun 02 2009]
a(n) written in base 2 is sequence A056830(n). [From Jaroslav Krizek (jaroslav.krizek(AT)atlas.cz), Aug 05 2009]
A000975 + A001045 = baguenaudier A166920. (b(n)=0,A000975) + A001045(n+1) = baguenaudier A051049. b(n) will be submitted. [From Paul Curtz (bpcrtz(AT)free.fr), Oct 29 2009]
A000975(n)=Sum_(i=0..n)A001045(i). This sequence gives partial sums of the sequence A001045 Jacobsthal numbers. [From Ctibor O. Zizka (c.zizka(AT)email.cz), Mar 06 2010]
This is the sequence A(0,1;1,2;1)of the family of sequences [a,b:c,d:k] considered by G. Detlefs, and treated as A(a,b;c,d;k) in the W. Lang link given below. [From Wolfdieter Lang (wolfdieter.lang(AT)physik.uni-karlsruhe.de), Oct 18 2010]
From Vladimir Shevelev, Jan 30 2012, Feb 13 2012: (Start)
1) Denote by {n,k} the number of permutations of 1,...,n with the up-down index k (for definition, see comment in A203827). Then max_k{n,k} = {n,a(n)} = A000111(n).
2) a(n) is the minimal number > a(n-1) with the Hamming distance d_H(a(n-1),a(n)) = n. Thus this sequence is the Hamming analog of trianglular numbers 0,1,3,6,10,... (End)
|
|
|
REFERENCES
| Thomas Fink and Yong Mao, The 85 Ways to Tie a Tie, Broadway Books, New York (1999), p. 138.
David Hayes, Kaveh Khodjasteh, Lorenza Viola and Michael J. Biercuk, Reducing sequencing complexity in dynamical quantum error suppression by Walsh modulation, Arxiv preprint arXiv:1109.6002, 2011
Robert L. Lamphere, A Recurrence Relation in the Spinout Puzzle, The College Mathematics Journal, Vol. 27, Nbr. 4, Page 289, Sep. 96.
Clifford A. Pickover, The Math Book, From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics, Sterling Publ., NY, 2009.
A. K. Whitford, Binet's Formula Generalized, Fibonacci Quarterly, Vol. 15, No. 1, 1979, pp. 21, 24, 29.
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=0..300
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 394
Hans Isdahl, "Knitwear" puzzle
S. Lafortune, A. Ramani, B. Grammaticos, Y. Ohta and K.M. Tamizhmani, Blending two discrete integrability criteria: ...
W. Lang, Notes on certain inhomogeneous three term recurrences. [From Wolfdieter Lang (wolfdieter.lang(AT)physik.uni-karlsruhe.de), Oct 18 2010]
N. J. A. Sloane, Transforms
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
Index entries for sequences related to linear recurrences with constant coefficients, signature (2,1,-2).
|
|
|
FORMULA
| a(n) = ceiling(2*(2^n-1)/3).
Alternating sum transform (PSumSIGN) of {2^n - 1} (A000225).
a(n) = a(n-1) + 2*a(n-2) + 1.
a(n)= 2*2^n/3-1/2-(-1)^n/6.
a(n) = Sum(K(i)), for i=1 to n, where K(i) = (2^(i-2) - (-1)^(i-2))/3 and K(1) = K(2) = 0 - Bill Blewett (billble(AT)microsoft.com).
a(n)= n + 2*Sum_{k = 1 to n-2} a(k).
G.f.: x/((1+x)*(1-x)*(1-2*x)) = x/(1-2*x-x^2+2*x^3); a(n)=2*a(n-1)+a(n-2)-2*a(n-3) - Paul Barry (pbarry(AT)wit.ie), Feb 11 2003
a(n)=sum{k=0..floor((n-1)/2), 2^(n-2k-1)} a(n+1)=sum{k=0..floor(n/2), 2^(n-2k) } - Paul Barry (pbarry(AT)wit.ie), Nov 11 2003
a(n+1)=sum{k=0..floor(n/2), 2^(n-2k) }; a(n+1)=sum{k=0..n, sum{j=0..k, (-1)^(j+k)2^j }}. - Paul Barry (pbarry(AT)wit.ie), Nov 12 2003
(-1)^(n+1)*a(n) = Sum(Sum(k!*k* Stirling2(i, k)*(-1)^(k-1), k=1, .., i), i=0, .., n) = (1/3)*(-2)^(n+1)-(1/6)(3*(-1)^(n+1)-1). - Mario Catalani (mario.catalani(AT)unito.it), Dec 22 2003
a(n+1)=(n!/3)*sum(i-(-1)^i+j=n, 0<=i<=n, 0<=j<=n, 1/(i-(-1)^i)!/j!) - Benoit Cloitre (benoit7848c(AT)orange.fr), May 24 2004
a(n)= A001045(n+1)-A059841(n). - Paul Barry (pbarry(AT)wit.ie), Jul 22 2004
a(n)=sum{k=0..n, 2^(n-k-1)*(1-(-1)^k)} - Paul Barry (pbarry(AT)wit.ie), Jul 28 2004
a(n)=sum{k=0..n, binomial(k, n-k+1)2^(n-k)}; a(n)=sum{k=0..floor(n/2), binomial(n-k, k+1)2^k}. - Paul Barry (pbarry(AT)wit.ie), Oct 07 2004
a(n) = floor(2^(n+1)/3) = ceiling(2^(n+1)/3)-1 = A005578(n+1)-1; - Paul Barry (pbarry(AT)wit.ie), Oct 08 2005
Convolution of "Number of fixed points in all 231-avoiding involutions in S_n." (A059570) with "1-n" (A024000), treating the result as if offset=0. - Graeme McRae (g_m(AT)mcraefamily.com), Jul 12 2006
a(n)=A081254(n)-2^n . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Oct 15 2006
Equals row sums of triangle A130125. - Gary W. Adamson (qntmpkt(AT)yahoo.com), May 11 2007
Starting (1, 2, 5, 10, 21, 42,...), = row sums of triangle A135228 - Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 23 2007
Let T = the 3 X 3 matrix [1,1,0; 1,0,1; 0,1,1]. Then T^n * [1,0,0] = [A005578(n), A001045(n), a(n-1)]. - Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 25 2007
If we define f(m,j,x)=sum(binomial(m,k)*stirling2(k,j)*x^(m-k),k=j..m) then a(n-3)=(-1)^(n-1)*f(n,3,-2), (n>=3). [From Milan R. Janjic (agnus(AT)blic.net), Apr 26 2009]
a(n)= floor( A051049(n+1)/3) [From Gary Detlefs (gdetlefs(AT) aol.com) Dec 19 2010]
a(n) = round((2^(n+2)-3)/6) = floor((2^(n+1)-1)/3) = round((2^(n+1)-2)/3); a(n)=a(n-2)+2^(n-1) , n>1. [From Mircea Merca, Dec 27 2010]
a(n) = binary XOR of 2^k-1 for k=0 to k=n. [From Paul D. Hanna, Nov 05 2011]
E.g.f.: 2/3*exp(2*x)-1/2*exp(x)-1/6*exp(-x)
=2/3*U(0); U(k)=1-3/(4*(2^k)-4*(2^k)/(1+3*(-1)^k- 24*x*(2^k)/(8*x*(2^k)*(-1)^k-(k+1)/U(k+1)))) ; (continued fraction). - Sergei N. Gladkovskii, Nov 21 2011
|
|
|
EXAMPLE
| a(4)=10 since 0001,0011,0010,0110,0111,0101,0100,1100,1101,1111 are the 10 binary strings switching 0000 to 1111
a(3) = 1 because "lrc" is the only way to tie a tie with 3 half turns, namely, pass the business end of the tie behind the standing part to the left, bring across the front to the right, then behind to the center. The final motion of tucking the loose end down the front behind the "lr" piece is not considered a "step".
a(4) = 2 because "lrlc" is the only way to tie a tie with 4 half turns. Note that since the number of moves is even, the first step is to go to the left in front of the tie, not behind it. This knot is the standard "four in hand", the most commonly known men's tie knot. By contrast, the second most well known tie knot, the Windsor, is represented by "lcrlcrlc".
a(n) = 2^0-1 XOR 2^1-1 XOR 2^2-1 XOR 2^3-1 XOR ... XOR 2^n-1. [Paul D. Hanna, Nov 05 2011]
|
|
|
MAPLE
| A000975 := proc(n) option remember; if n <= 1 then n else if n mod 2 = 0 then 2*A000975(n-1) else 2*A000975(n-1)+1 fi; fi; end;
seq(iquo(2^n, 3), n=1..33); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 20 2008
|
|
|
MATHEMATICA
| f[n_] := Ceiling[2(2^n-1)/3]; Array[f, 41, 0]
|
|
|
PROG
| (PARI) {a(n)=if(n<0, 0, 2*2^n\3)} /* Michael Somos Sep 04 2006 */
(PARI) {a(n)=if(n<=0, 0, bitxor(a(n-1), 2^n-1))} /* Paul D. Hanna, Nov 05 2011 */
|
|
|
CROSSREFS
| Partial sums of A001045. Cf. A015441, A053404, A026644.
Row sums of triangle A013580.
Cf. A119440, A130125, A135228.
Cf. A005578.
Cf. A000295 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Jun 02 2009]
Cf. A179970. [From Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Aug 04 2010]
Sequence in context: A191531 A030525 A116385 * A032283 A027437 A101510
Adjacent sequences: A000972 A000973 A000974 * A000976 A000977 A000978
|
|
|
KEYWORD
| nonn,easy,nice,changed
|
|
|
AUTHOR
| Mira Bernstein (mira(AT)math.berkeley.edu), N. J. A. Sloane (njas(AT)research.att.com), Robert G. Wilson v, Sep 13, 1996.
|
|
|
EXTENSIONS
| Additional comments from Barry E. Williams, Jan 10 2000
|
| |
|
|
