login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #18 Jan 08 2016 10:56:31

%S 0,4,146,3034,52916,857824,13426406,206324374,3138660776,47471139964,

%T 715573119866,10765074628114,161759034582236,2428929817996504,

%U 36456836245518926,547058495778290254,8207730761823753296,123132640134289171444,1847139704277091999586,27708446454015214334794,415638854666404701309956

%N 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.

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

%H M. A. Alekseyev and T. Berger, <a href="http://arxiv.org/abs/1304.3780">Solving the Tower of Hanoi with Random Moves</a>. 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

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (32,-342,1440,-2025).

%F a(n) = ( (3^n - 1)*(5^(n+1) - 2*3^(n+1)) + 5^n - 3^n ) / 4.

%F a(n) = 3^n*A007798(n) + 2*A134939(n).

%F 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

%o (PARI) 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

%Y Cf. A007798, A134939, A226511.

%K nonn,easy

%O 0,2

%A _Max Alekseyev_, Sep 08 2014