A073724 a(n) = (4^(n+1) + 6n + 5)/9.
1, 3, 9, 31, 117, 459, 1825, 7287, 29133, 116515, 466041, 1864143, 7456549, 29826171, 119304657, 477218599, 1908874365, 7635497427, 30541989673, 122167958655, 488671834581, 1954687338283, 7818749353089, 31274997412311
Offset: 0
Examples
Moving a tower of 4 disks = 2^4 - 1 moves, coded {1,0,5,1,2,3,1,0,5,4,2,5,1,0,5}. The move from peg 1 to peg 2 has code "0" and this occurs 3 times. For 3 disks we also find 3 zeros in {0,1,3,0,4,5,0}. Hence a(2)=3. The coding corresponds to the rank of the permutation {'from peg' 1, 'to peg' 2, 'by peg' 3} or {1,2,3} with rank 0.
Links
- Vincenzo Librandi, Table of n, a(n) for n = 0..170
- Hacène Belbachir and El-Mehdi Mehiri, Enumerating moves in the optimal solution of the Tower of Hanoi, arXiv:2210.08657 [math.CO], 2022.
- F. J. van de Bult, D. C. Gijswijt, J. P. Linderman, N. J. A. Sloane and Allan Wilks, A Slow-Growing Sequence Defined by an Unusual Recurrence, J. Integer Sequences, Vol. 10 (2007), #07.1.2.
- F. J. van de Bult, D. C. Gijswijt, J. P. Linderman, N. J. A. Sloane and Allan Wilks, A Slow-Growing Sequence Defined by an Unusual Recurrence [pdf, ps].
- Index entries for sequences related to Gijswijt's sequence
- Index entries for linear recurrences with constant coefficients, signature (6,-9,4).
- Index entries for sequences related to Towers of Hanoi
Crossrefs
Programs
-
Magma
[(4^(n+1)+6*n+5)/9: n in [0..40] ]; // Vincenzo Librandi, Apr 28 2011
-
Mathematica
Table[(4^(n+1)+6n+5)/9, {n, 0, 24}] -
PARI
a(n)=(4*4^n+6*n+5)/9
-
PARI
a(n)=polcoeff((1-3*x)/(1-4*x)/(1-x)^2+x*O(x^n),n)
Formula
G.f.: (1-3*x)/((1-4*x)*(1-x)^2).
a(n) = Sum_{k=0..n} A047849(k). - L. Edson Jeffery, May 01 2021
From Elmo R. Oliveira, Dec 11 2023: (Start)
a(n) = 6*a(n-1) - 9*a(n-2) + 4*a(n-3) for n>2.
E.g.f.: (1/9)*(4*(exp(4*x)) + 6*x*exp(x) + 5*exp(x)). (End)
Comments