cp's OEIS Frontend

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.

%I A243521 #21 Jan 22 2021 20:30:41
%S A243521 1,3,12,57,300,1701,10206,63825,411096,2702349,17992506,120543561,
%T A243521 808224372,5400815829,35868103734,236354531841,1544182760496,
%U A243521 10001335837725,64233753928722,409298268016761,2589206145139596
%N 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.
%H A243521 Colin Barker, <a href="/A243521/b243521.txt">Table of n, a(n) for n = 0..1000</a>
%H A243521 <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 A243521 <a href="/index/To#Hanoi">Index entries for sequences related to Towers of Hanoi</a>
%F A243521 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 A243521 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 A243521 From _Colin Barker_, Jul 18 2019: (Start)
%F A243521 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 A243521 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 A243521 (End)
%o A243521 (Sage)
%o A243521 for n in range(11):
%o A243521     t=0
%o A243521     for k in range(n+1):
%o A243521         for j in range(n-k+1):
%o A243521             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 A243521     print(t)
%o A243521 (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 A243521 Terms in product are A000325.
%K A243521 nonn,easy
%O A243521 0,2
%A A243521 _Robert A. Beeler_, Jun 05 2014