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

1, 2, 4, 10, 20, 42, 84, 170, 340, 682, 1364, 2730, 5460, 10922, 21844, 43690, 87380, 174762, 349524, 699050, 1398100, 2796202, 5592404, 11184810, 22369620, 44739242, 89478484, 178956970, 357913940, 715827882, 1431655764, 2863311530, 5726623060

Offset: 0

Author

Clark Kimberling

Keywords

• nonn
• easy

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

Crossrefs

Row sums of A026637.

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

A167030 is an essentially identical sequence.

Programs

Magma

[n eq 0 select 1 else (2^(n+2) -3-(-1)^n)/3 : n in [0..40]]; // G. C. Greubel, Jun 28 2024

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 *)

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

Python

def A026644(n): return ((4<Chai Wah Wu, Apr 17 2025

SageMath

[(2^(n+2)-3-(-1)^n)/3 + int(n==0) for n in range(41)] # G. C. Greubel, Jun 28 2024

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) = A052953(n+1) - 2, n>0. [Moved from A020988, R. J. Mathar, Oct 21 2008]

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

a(n) = A000975(n+1) - A000035(n+1), n>0, a(0)=1. - Yuchun Ji, Aug 05 2020

Extensions

Recurrence in definition line found by Lee Hae-hwang, Apr 03 2002