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

Author

Robert A. Beeler, Jun 05 2014

Keywords

• nonn
• easy

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

Crossrefs

Terms in product are A000325.

Programs

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

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)

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)