A007798 -id:A007798 - cp's OEIS frontend

A060590 Numerator of the expected time to finish a random Tower of Hanoi problem with n disks using optimal moves.

0, 2, 2, 14, 10, 62, 42, 254, 170, 1022, 682, 4094, 2730, 16382, 10922, 65534, 43690, 262142, 174762, 1048574, 699050, 4194302, 2796202, 16777214, 11184810, 67108862, 44739242, 268435454, 178956970, 1073741822, 715827882, 4294967294

Offset: 0

Henry Bottomley, Apr 05 2001

			a(2)=2 since there are nine equally likely possibilities, with times required of 0,1,1,2,2,3,3,3,3 giving an average of 18/9 = 2/1.

Harry J. Smith, Table of n, a(n) for n = 0..500
Index entries for linear recurrences with constant coefficients, signature (0,5,0,-4).
Index entries for sequences related to Towers of Hanoi

Denominator is A010684(n). Cf. A007798, A060586, A060589, A020988 (even bisection).

a(n)={2*(2^n - 1)*(2 - (-1)^n)/3} \\ Harry J. Smith, Jul 07 2009

a(n) = 2*(2^n - 1)*(2 - (-1)^n)/3.
a(2n) = A020988(n-1).
From Ralf Stephan, Mar 07 2003: (Start)
G.f.: (4*x^3+2*x^2+2*x)/(4*x^4-5*x^2+1).
a(n+4) = 5*a(n+2) - 4*a(n). (End)

A060589 a(n) = 2(2^n-1)3^(n-1).

Original entry on oeis.org

0, 2, 18, 126, 810, 5022, 30618, 185166, 1115370, 6705342, 40271418, 241746606, 1450833930, 8706066462, 52239587418, 313447090446, 1880711240490, 11284353536382, 67706379498618, 406239051832686, 2437436635519050, 14624626786683102, 87747781640805018

Offset: 0

Henry Bottomley, Apr 05 2001

a(n)/3^n is the expected time to finish a random Tower of Hanoi problem with n disks using optimal moves.

Harry J. Smith, Table of n, a(n) for n = 0..200
Index entries for linear recurrences with constant coefficients, signature (9,-18).

Cf. A007798, A060586, A060590.

[2*(2^n - 1)*3^(n - 1): n in [0..30]]; // Vincenzo Librandi, Jul 03 2018

Table[2 (2^n - 1) 3^(n - 1), {n, 0, 50}] (* or *) LinearRecurrence[{9, -18}, {0, 2}, 40] (* Vincenzo Librandi, Jul 03 2018 *)

a(n)={2*(2^n - 1)*3^(n - 1)} \\ Harry J. Smith, Jul 07 2009

a(n) = Sum_{j<2^n} j*A001316(j) = 6*a(n-1) + A008776(n-1) = 4*A000400(n-1) - A008776(n-1) = A000244(n)*A060590(n)/A010684(n).

G.f.: 2*x/((3*x-1)*(6*x-1)). [Colin Barker, Dec 26 2012]

Corrected by T. D. Noe, Nov 07 2006

A134939 Numerator of the expected number of random moves in Tower of Hanoi problem with n disks starting on peg 1 and ending on peg 3.

Original entry on oeis.org

0, 2, 64, 1274, 21760, 348722, 5422144, 83000234, 1259729920, 19027002722, 286576949824, 4309163074394, 64731832372480, 971825991711122, 14585021567101504, 218843984372767754, 3283277591489597440, 49254723695591689922, 738870890792896773184, 11083513664870504400314

Offset: 0

Toby Berger (tb6n(AT)virginia.edu), Jan 23 2008

Both allowable transitions out of any of the three special states in which all the disks are on one of the pegs have probability 1/2 and each of the three allowable transitions out of any of the other 3^n - 3 states have probability 1/3.

			The values of e(0), ..., e(4), e(5) are 0, 2, 64/3, 1274/9, 21760/27, 348722/81.

M. A. Alekseyev and T. Berger, Solving the Tower of Hanoi with Random Moves. In: J. Beineke, J. Rosenhouse (eds.) The Mathematics of Various Entertaining Subjects: Research in Recreational Math, Princeton University Press, 2016, pp. 65-79. ISBN 978-0-691-16403-8
mersenneforum.org, Towers of Hanoi with random moves.
Index entries for linear recurrences with constant coefficients, signature (32,-342,1440,-2025).
Index entries for sequences related to Towers of Hanoi

Cf. A007798, A134940.

a(n) = numerator(e(n)) with e(n) = (3^n-1)*(5^n-3^n) / (2*3^(n-1)), a(n) = (3^n-1)*(5^n-3^n) / 2. - Max Alekseyev, Feb 04 2008

G.f.: -2*x*(45*x^2-1) / ((3*x-1)*(5*x-1)*(9*x-1)*(15*x-1)). - Colin Barker, Dec 26 2012

Values of e(5) onwards and general formula found by Max Alekseyev, Feb 02 2008, Feb 04 2008

Shorter name by Michel Marcus, Dec 27 2012

A060592 Square table by antidiagonals of minimum number of moves between two positions in the Tower of Hanoi (with three pegs: 0,1,2), where with position n written in base 3, xyz means smallest disk is on peg z, second smallest is on peg y, third smallest on peg x, etc. and leading zeros indicate largest disks are all on peg 0.

Original entry on oeis.org

0, 1, 1, 1, 0, 1, 3, 1, 1, 3, 3, 3, 0, 3, 3, 2, 3, 2, 2, 3, 2, 3, 2, 2, 0, 2, 2, 3, 2, 2, 1, 1, 1, 1, 2, 2, 3, 1, 3, 1, 0, 1, 3, 1, 3, 7, 2, 2, 1, 1, 1, 1, 2, 2, 7, 6, 6, 3, 2, 2, 0, 2, 2, 3, 6, 6, 7, 5, 7, 2, 3, 2, 2, 3, 2, 7, 5, 7, 6, 6, 6, 6, 3, 3, 0, 3, 3, 6, 6, 6, 6, 7, 5, 7, 5, 5, 3, 1, 1, 3, 5, 5, 7, 5, 7

Offset: 0

Henry Bottomley, Apr 06 2001

			T(4,9)=5 since 4 and 9 written in base 3 are 11 and 100, i.e. the starting position has the first and second disks on peg 1 and the others on peg 0, while the end position has the third disk on peg 1 and the others on peg 0; the five optimal moves between these positions are: move the third disk to peg 2, then the first to peg 2, the second to peg 0, the first to peg 0 and finally the third to peg 1.

Cf. A001511, A007798, A055661, A055662.

A225476 Triangle read by rows, k!2^kS_2(n, k) where S_m(n, k) are the Stirling-Frobenius subset numbers of order m; n >= 0, k >= 0.

Original entry on oeis.org

1, 1, 1, 1, 4, 2, 1, 13, 18, 6, 1, 40, 116, 96, 24, 1, 121, 660, 1020, 600, 120, 1, 364, 3542, 9120, 9480, 4320, 720, 1, 1093, 18438, 74466, 121800, 94920, 35280, 5040, 1, 3280, 94376, 576576, 1394064, 1653120, 1028160, 322560, 40320, 1, 9841, 478440, 4319160

Offset: 0

Peter Luschny, May 19 2013

The Stirling-Frobenius subset numbers are defined in A225468 (see also the Sage program).

			[n\k][0,   1,   2,    3,   4,   5 ]
[0]   1,
[1]   1,   1,
[2]   1,   4,   2,
[3]   1,  13,  18,    6,
[4]   1,  40, 116,   96,  24,
[5]   1, 121, 660, 1020, 600, 120.

Vincenzo Librandi, Rows n = 0..50, flattened
Peter Luschny, Generalized Eulerian polynomials.
Peter Luschny, The Stirling-Frobenius numbers.
Shi-Mei Ma, Toufik Mansour, Matthias Schork, Normal ordering problem and the extensions of the Stirling grammar, Russian Journal of Mathematical Physics, 2014, 21(2), arXiv 1308.0169 p. 12.

T(n, 0) ~ A000012; T(n, 1) ~ A003462; T(n, 2) ~ A007798.
T(n, n) ~ A000142; T(n, n-1) ~ A001563.
Alternating row sum ~ A000364 (Euler secant numbers).
Cf. A225468, A131689 (m=1).

SF_SSO := proc(n, k, m) option remember;
if n = 0 and k = 0 then return(1) fi;
if k > n or k < 0 then return(0) fi;
k*SF_SSO(n-1, k-1, m) + (m*(k+1)-1)*SF_SSO(n-1, k, m) end:
seq(print(seq(SF_SSO(n, k, 2), k=0..n)), n = 0..5);

EulerianNumber[n_, k_, m_] := EulerianNumber[n, k, m] = (If[ n == 0, Return[If[k == 0, 1, 0]]]; Return[(m*(n - k) + m - 1)*EulerianNumber[n - 1, k - 1, m] + (m*k + 1)*EulerianNumber[n - 1, k, m]]); SFSSO[n_, k_, m_] := Sum[ EulerianNumber[n, j, m]*Binomial[j, n - k], {j, 0, n}]/m^k; Table[ SFSSO[n, k, 2], {n, 0, 9}, {k, 0, n}] // Flatten (* Jean-François Alcover, May 29 2013, translated from Sage *)

@CachedFunction
def EulerianNumber(n, k, m) :
    if n == 0: return 1 if k == 0 else 0
    return (m*(n-k)+m-1)*EulerianNumber(n-1, k-1, m)+(m*k+1)*EulerianNumber(n-1, k, m)
def SF_SSO(n, k, m):
    return add(EulerianNumber(n, j, m)*binomial(j, n - k) for j in (0..n))/m^k
for n in (0..6): [SF_SSO(n, k, 2) for k in (0..n)]

T(n, k) = sum_{j=0..n} A_2(n, j)*binomial(j, n-k), where A_2(n, j) are the generalized Eulerian numbers of order m=2.

For a recurrence see the Maple program.

A246961 Numerator of the expected number of random moves in Tower of Hanoi problem with n disks starting at a randomly chosen valid configuration and ending with all disks at peg 1.

Original entry on oeis.org

0, 4, 146, 3034, 52916, 857824, 13426406, 206324374, 3138660776, 47471139964, 715573119866, 10765074628114, 161759034582236, 2428929817996504, 36456836245518926, 547058495778290254, 8207730761823753296, 123132640134289171444, 1847139704277091999586, 27708446454015214334794, 415638854666404701309956

Offset: 0

Max Alekseyev, Sep 08 2014

The expected number of random moves is given by a(n)/3^n = a(n)/A000244(n).

M. A. Alekseyev and T. Berger, Solving the Tower of Hanoi with Random Moves. In: J. Beineke, J. Rosenhouse (eds.) The Mathematics of Various Entertaining Subjects: Research in Recreational Math, Princeton University Press, 2016, pp. 65-79. ISBN 978-0-691-16403-8
Index entries for linear recurrences with constant coefficients, signature (32,-342,1440,-2025).

Cf. A007798, A134939, A226511.

concat(0, Vec(-2*x*(135*x^2-9*x-2)/((3*x-1)*(5*x-1)*(9*x-1)*(15*x-1)) + O(x^100))) \\ Colin Barker, Sep 17 2014

a(n) = ( (3^n - 1)*(5^(n+1) - 2*3^(n+1)) + 5^n - 3^n ) / 4.
a(n) = 3^n*A007798(n) + 2*A134939(n).
G.f.: -2*x*(135*x^2-9*x-2) / ((3*x-1)*(5*x-1)*(9*x-1)*(15*x-1)). - Colin Barker, Sep 17 2014

cp's OEIS Frontend

A060590 Numerator of the expected time to finish a random Tower of Hanoi problem with n disks using optimal moves.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A060589 a(n) = 2*(2^n-1)*3^(n-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A134939 Numerator of the expected number of random moves in Tower of Hanoi problem with n disks starting on peg 1 and ending on peg 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

Views

Author

Keywords

Examples

Links

Crossrefs

A225476 Triangle read by rows, k!*2^k*S_2(n, k) where S_m(n, k) are the Stirling-Frobenius subset numbers of order m; n >= 0, k >= 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

A246961 Numerator of the expected number of random moves in Tower of Hanoi problem with n disks starting at a randomly chosen valid configuration and ending with all disks at peg 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A060589 a(n) = 2(2^n-1)3^(n-1).

A225476 Triangle read by rows, k!2^kS_2(n, k) where S_m(n, k) are the Stirling-Frobenius subset numbers of order m; n >= 0, k >= 0.