|
%I #117 Feb 16 2024 10:22:44
%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 G.f.: (1 - x^2 + 2*x^3)/((1 - x)*(1 - x - 2*x^2)); a(n) = J(n+2) - 1 + 0^n, where J(n) = A001045(n); a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3); a(n) = 0^n + Sum_{k=0..n} (2 - 2*0^(n-k))*J(k+1). - _Paul Barry_, Oct 24 2007
%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
%Y a(n) = T(n, 0) + T(n, 1) + ... + T(n, n), T given by 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
|
