0,3

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]

Thomas Fink and Yong Mao, The 85 Ways to Tie a Tie, Broadway Books, New York (1999), p. 138.

Robert L. Lamphere, A Recurrence Relation in the Spinout Puzzle, The College Mathematics Journal, Vol. 27, Nbr. 4, Page 289, Sep. 96.

A. K. Whitford, Binet's Formula Generalized, Fibonacci Quarterly, Vol. 15, No. 1, 1979, pp. 21, 24, 29.

T. D. Noe, Table of n, a(n) for n=0..300

Index entries for sequences related to linear recurrences with constant coefficients

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 394

S. Lafortune, A. Ramani, B. Grammaticos, Y. Ohta and K.M. Tamizhmani, Blending two discrete integrability criteria: ...

N. J. A. Sloane, Transforms

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Hans Isdahl, "Knitwear" puzzle

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))-1]-[((-1)^(n))-1]/2}/3.

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(n).

G.f.: x/((1+x)(1-x)(1-2x)) = x/(1-2x-x^2+2x^3); a(n)=2a(n-1)+a(n-2)-2a(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

Let b(n)=(-1)^(n+1)a(n). Then b(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)=2*2^n/3-1/2-(-1)^n/6=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(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".

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

F[n_] := Ceiling[2(2^n-1)/3]; Table[F[n], {n, 0, 40}]

(PARI) {a(n)=if(n<0, 0, 2*2^n\3)} /* Michael Somos Sep 04 2006 */

Partial sums of A001045. Cf. A015441, A053404, A026644.

Row sums of triangle A013580.

Cf. A119440, A130125, A135228.

Cf. A005578.

A000295 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Jun 02 2009]

Sequence in context: A056599 A030525 A116385 this_sequence A032283 A027437 A101510

Adjacent sequences: A000972 A000973 A000974 this_sequence A000976 A000977 A000978

nonn,easy,nice

Mira Bernstein (mira(AT)math.berkeley.edu), N. J. A. Sloane (njas(AT)research.att.com), rgwv, Sep 13, 1996.

Additional comments from Barry E. Williams, Jan 10 2000