A026644 - OEIS

%I #121 Jun 30 2024 09:10:15

%S 1,2,4,10,20,42,84,170,340,682,1364,2730,5460,10922,21844,43690,87380,

%T 174762,349524,699050,1398100,2796202,5592404,11184810,22369620,

%U 44739242,89478484,178956970,357913940,715827882,1431655764,2863311530,5726623060

%N a(n) = a(n-1) + 2*a(n-2) + 2, for n>=3, where a(0)= 1, a(1)= 2, a(2)= 4.

%C Number of moves to solve Chinese rings puzzle.

%C a(n-1) (with a(0):=0) enumerates all sequences of length m=1,2,...,floor(n/2) with nonzero integer entries n_i satisfying sum |n_i| <= n-m. Rephrasing K. A. Meissner's example p. 6. Example n=4: from length m=1: [1], [2], [3], each in 2 signed versions; from m=2: [1,1] in 2^2 = 4 signed versions. Hence a(3) = a(4-1) = 3*2 + 1*4 = 10.

%C Also the number of different 3-colorings (out of 4 colors) for the vertices of all triangulated planar polygons on a base with n+1 vertices if the colors of the two base vertices are fixed. - _Patrick Labarque_, Mar 23 2010

%C For n > 0, also the total distance that the disks travel from the leftmost peg to the rightmost peg in the Tower of Hanoi puzzle, in the unique solution with 2^n-1 moves (see links). - _Sela Fried_, Dec 17 2023

%D Richard I. Hess, Compendium of Over 7000 Wire Puzzles, privately printed, 1991.

%D Richard I. Hess, Analysis of Ring Puzzles, booklet distributed at 13th International Puzzle Party, Amsterdam, Aug 20 1993.

%H Vincenzo Librandi, <a href="/A026644/b026644.txt">Table of n, a(n) for n = 0..1000</a>

%H Thomas Baruchel, <a href="https://arxiv.org/abs/1908.02250">Properties of the cumulated deficient binary digit sum</a>, arXiv:1908.02250 [math.NT], 2019.

%H Sela Fried, <a href="/A026644/a026644_1.pdf">Economically solving the Tower of Hanoi puzzle</a>.

%H Nicolas Gastineau and O. Togni, <a href="https://arxiv.org/abs/1711.10906">On S-packing edge-colorings of cubic graphs</a>, arXiv preprint arXiv:1711.10906 [cs.DM], 2017.

%H Lee Hae-hwang, <a href="/A026644/a026644.html">Illustration of initial terms in terms of rosemary plants</a>

%H Krzysztof A. Meissner, <a href="https://arxiv.org/abs/gr-qc/0407052">Black hole entropy in Loop Quantum Gravity</a>, arXiv:gr-qc/0407052, 2004.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-2).

%F a(2*k) = 2*a(2*k-1), a(2*k+1) = 2*a(2*k) + 2. - _Peter Shor_, Apr 11 2002

%F For n>0: a(n+1) = a(n) + 2*b(n+1) + 4*b(n), where b(k) = A001045(k). - _N. J. A. Sloane_, May 16 2003

%F For n>0: if n mod 2 = 0 then (2^(n+2)-4)/3 else (2^(n+2)-2)/3. - Richard Hess

%F a(2*n) = 2*n-1 + Sum_{k=0..2*n-1} a(k), n>0; a(2*n+1) = 2*n+1 + Sum_{k=0..n} a(k). - _Lee Hae-hwang_, Sep 17 2002; corrected by _R. J. Mathar_, Oct 21 2008

%F a(n) = 2*n + 2*Sum_{k=1..n-2} a(k), n>0. - _Lee Hae-hwang_, Sep 19 2002; corrected by _R. J. Mathar_, Oct 21 2008

%F From _Paul Barry_, Oct 24 2007: (Start)

%F G.f.: (1 - x^2 + 2*x^3)/((1 - x)*(1 - x - 2*x^2)).

%F a(n) = J(n+2) - 1 + 0^n, where J(n) = A001045(n) (Jacobsthal numbers).

%F a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3).

%F a(n) = 0^n + Sum_{k=0..n} (2 - 2*0^(n-k))*J(k+1). (End)

%F a(n) = A052953(n+1) - 2, n>0. [Moved from A020988, _R. J. Mathar_, Oct 21 2008]

%F a(n) = floor(A097074(n+1)/2), n>0. - _Gary Detlefs_, Dec 19 2010

%F a(n) = A169969(2*n-1) - 1, n>=2; a(n) = 3*2^(n-1) - 1 - A169969(2*n-7), n>=5 . - _Yosu Yurramendi_, Jul 05 2016

%F a(n+3) = 3*2^(n+2) - 2 - a(n), n>=1, a(1)=2, a(2)=4, a(3)=10 . - _Yosu Yurramendi_, Jul 05 2016

%F a(n) + A084170(n) = 3*2^n - 2, n>=1. - _Yosu Yurramendi_, Jul 05 2016

%F E.g.f: (3 - 4*cosh(x) + 4*cosh(2*x) - 2*sinh(x) + 4*sinh(2*x))/3. - _Ilya Gutkovskiy_, Jul 05 2016

%F a(n+3) = 9*2^n + A084170(n), n>=0. - _Yosu Yurramendi_, Jul 07 2016

%F a(n) = A000975(n+1) - A000035(n+1), n>0, a(0)=1. - _Yuchun Ji_, Aug 05 2020

%p f:=n-> if n mod 2 = 0 then (2^(n+2)-4)/3 else (2^(n+2)-2)/3; fi;

%t Join[{1}, Floor[(2^Range[3, 40] - 2)/3]] (* or *) LinearRecurrence[{2,1,-2},{1,2,4,10},40] (* _Vladimir Joseph Stephan Orlovsky_, Jan 29 2012 *)

%t CoefficientList[Series[(1-x^2+2x^3)/((1-x)(1-x-2x^2)),{x,0,1001}],x] (* _Vincenzo Librandi_, Apr 04 2012 *)

%o (PARI) Vec((1-x^2+2*x^3)/(1-x)/(1-x-2*x^2)+O(x^99)) \\ _Charles R Greathouse IV_, Apr 04 2012

%o (Magma) [n eq 0 select 1 else (2^(n+2) -3-(-1)^n)/3 : n in [0..40]]; // _G. C. Greubel_, Jun 28 2024

%o (SageMath) [(2^(n+2)-3-(-1)^n)/3 + int(n==0) for n in range(41)] # _G. C. Greubel_, Jun 28 2024

%Y Row sums of A026637.

%Y For n >= 1, equals twice A000975, also A001045 - 1.

%Y A167030 is an essentially identical sequence.

%K nonn,easy

%O 0,2

%A _Clark Kimberling_

%E Recurrence in definition line found by _Lee Hae-hwang_, Apr 03 2002