OFFSET
0,2
COMMENTS
Number of moves to solve Chinese rings puzzle.
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.
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
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
REFERENCES
Richard I. Hess, Compendium of Over 7000 Wire Puzzles, privately printed, 1991.
Richard I. Hess, Analysis of Ring Puzzles, booklet distributed at 13th International Puzzle Party, Amsterdam, Aug 20 1993.
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Thomas Baruchel, Properties of the cumulated deficient binary digit sum, arXiv:1908.02250 [math.NT], 2019.
Sela Fried, Economically solving the Tower of Hanoi puzzle.
Nicolas Gastineau and O. Togni, On S-packing edge-colorings of cubic graphs, arXiv preprint arXiv:1711.10906 [cs.DM], 2017.
Lee Hae-hwang, Illustration of initial terms in terms of rosemary plants
Krzysztof A. Meissner, Black hole entropy in Loop Quantum Gravity, arXiv:gr-qc/0407052, 2004.
Index entries for linear recurrences with constant coefficients, signature (2,1,-2).
FORMULA
a(2*k) = 2*a(2*k-1), a(2*k+1) = 2*a(2*k) + 2. - Peter Shor, Apr 11 2002
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
For n>0: if n mod 2 = 0 then (2^(n+2)-4)/3 else (2^(n+2)-2)/3. - Richard Hess
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
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
From Paul Barry, Oct 24 2007: (Start)
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) (Jacobsthal numbers).
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). (End)
a(n) = floor(A097074(n+1)/2), n>0. - Gary Detlefs, Dec 19 2010
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
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
a(n) + A084170(n) = 3*2^n - 2, n>=1. - Yosu Yurramendi, Jul 05 2016
E.g.f: (3 - 4*cosh(x) + 4*cosh(2*x) - 2*sinh(x) + 4*sinh(2*x))/3. - Ilya Gutkovskiy, Jul 05 2016
a(n+3) = 9*2^n + A084170(n), n>=0. - Yosu Yurramendi, Jul 07 2016
MAPLE
f:=n-> if n mod 2 = 0 then (2^(n+2)-4)/3 else (2^(n+2)-2)/3; fi;
MATHEMATICA
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 *)
CoefficientList[Series[(1-x^2+2x^3)/((1-x)(1-x-2x^2)), {x, 0, 1001}], x] (* Vincenzo Librandi, Apr 04 2012 *)
PROG
(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
(Magma) [n eq 0 select 1 else (2^(n+2) -3-(-1)^n)/3 : n in [0..40]]; // G. C. Greubel, Jun 28 2024
(SageMath) [(2^(n+2)-3-(-1)^n)/3 + int(n==0) for n in range(41)] # G. C. Greubel, Jun 28 2024
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
EXTENSIONS
Recurrence in definition line found by Lee Hae-hwang, Apr 03 2002
STATUS
approved