A243521 The number of states in a Tower of Hanoi puzzle with three pegs and n discs, where a larger disc can be placed directly on top of a smaller one at most once per peg.

1, 3, 12, 57, 300, 1701, 10206, 63825, 411096, 2702349, 17992506, 120543561, 808224372, 5400815829, 35868103734, 236354531841, 1544182760496, 10001335837725, 64233753928722, 409298268016761, 2589206145139596

Offset

0,2

Links

Colin Barker, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (40,-715,7522,-51583,240964,-776637,1705554,-2442744,2060640,-777600).

Index entries for sequences related to Towers of Hanoi

Formula

a(n) = Sum_{i+j+k=n, i >= 0, j >= 0, k>= 0} {n choose i, j, k}(2^i-i)(2^j-j)(2^k-k).

a(n) = 6^n-3*n*5^{n-1}+3*n*(n-1)*4^{n-2}-n*(n-1)*(n-2)3^{n-3}.

From Colin Barker, Jul 18 2019: (Start)

G.f.: (1 - 37*x + 607*x^2 - 5800*x^3 + 35617*x^4 - 146023*x^5 + 400653*x^6 - 711780*x^7 + 746142*x^8 - 353412*x^9) / ((1 - 3*x)^4*(1 - 4*x)^3*(1 - 5*x)^2*(1 - 6*x)).

a(n) = 40*a(n-1) - 715*a(n-2) + 7522*a(n-3) - 51583*a(n-4) + 240964*a(n-5) - 776637*a(n-6) + 1705554*a(n-7) - 2442744*a(n-8) + 2060640*a(n-9) - 777600*a(n-10) for n>9.

(End)

Prog

(Sage)
for n in range(11):
    t=0
    for k in range(n+1):
        for j in range(n-k+1):
            t=t+((Combinations(n, k).cardinality())*(Combinations(n-k, j).cardinality())*((2^k)-k)*((2^j)-j)*((2^(n-k-j))-n+k+j));
    print(t)
(PARI) Vec((1 - 37*x + 607*x^2 - 5800*x^3 + 35617*x^4 - 146023*x^5 + 400653*x^6 - 711780*x^7 + 746142*x^8 - 353412*x^9) / ((1 - 3*x)^4*(1 - 4*x)^3*(1 - 5*x)^2*(1 - 6*x)) + O(x^30)) \\ Colin Barker, Jul 18 2019

Crossrefs

Terms in product are A000325.

Sequence in context: A047891 A166991 A276366 * A369484 A151498 A103370

Adjacent sequences: A243518 A243519 A243520 * A243522 A243523 A243524

Keyword

nonn,easy

Author

Robert A. Beeler, Jun 05 2014

Status

approved