A243521 - OEIS

%I #21 Jan 22 2021 20:30:41

%S 1,3,12,57,300,1701,10206,63825,411096,2702349,17992506,120543561,

%T 808224372,5400815829,35868103734,236354531841,1544182760496,

%U 10001335837725,64233753928722,409298268016761,2589206145139596

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

%H Colin Barker, <a href="/A243521/b243521.txt">Table of n, a(n) for n = 0..1000</a>

%H <a href="/index/Rec#order_10">Index entries for linear recurrences with constant coefficients</a>, signature (40,-715,7522,-51583,240964,-776637,1705554,-2442744,2060640,-777600).

%H <a href="/index/To#Hanoi">Index entries for sequences related to Towers of Hanoi</a>

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

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

%F From _Colin Barker_, Jul 18 2019: (Start)

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

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

%F (End)

%o (Sage)

%o for n in range(11):

%o     t=0

%o     for k in range(n+1):

%o         for j in range(n-k+1):

%o             t=t+((Combinations(n,k).cardinality())*(Combinations(n-k,j).cardinality())*((2^k)-k)*((2^j)-j)*((2^(n-k-j))-n+k+j));

%o     print(t)

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

%Y Terms in product are A000325.

%K nonn,easy

%O 0,2

%A _Robert A. Beeler_, Jun 05 2014