Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
%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