|
%I #46 Oct 04 2017 05:34:54
%S 4,125,4007754,132460031222098852477,
%T 4782311037918647241715144272946478084784910628903006412891408
%N Number of matchings in the n-Hanoi graph.
%H Andrew Howroyd, <a href="/A286017/b286017.txt">Table of n, a(n) for n = 1..7</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IndependentEdgeSet.html">Independent Edge Set</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Matching.html">Matching</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HanoiGraph.html">Hanoi Graph</a>
%t next[{h0_, h1_, h2_, h3_}] := {h0^3 + 3*h0*h1^2 + 3*h1^2*h2 + h2^3, h0^2*h1 + 2*h0*h1*h2 + h1^3 + 2*h1*h2^2 + h1^2*h3 + h2^2*h3, h0*h1^2 + 2*h1^2*h2 + h0*h2^2 + 2*h1*h2*h3 + h2^3 + h2*h3^2, h1^3 + 3*h1*h2^2 + 3*h2^2*h3 + h3^3};
%t a[n_] := Module[{v = {1, 1, 0, 0}}, For[i = 1, i <= n, i++, v = next[v]]; v[[1]]];
%t Array[a, 5] (* _Jean-François Alcover_, Oct 02 2017, translated from _Andrew Howroyd_'s PARI code *)
%t Rest @ NestList[Function[{h, i, j, k}, {h^3 + 3 h i^2 + 3 i^2 j + j^3, h^2 i + 2 h i j + i^3 + 2 i j^2 + i^2 k + j^2 k, h i^2 + 2 i^2 j + h j^2 + 2 i j k + j^3 + j k^2, i^3 + 3 i j^2 + 3 j^2 k + k^3}] @@ # &, {1, 1, 0, 0}, 5][[All, 1]] (* _Eric W. Weisstein_, Oct 02 2017 *)
%o (PARI)
%o \\ here h0..h3 are number of matchings in Hanoi graph less 0..3 apex vertices.
%o Next(h0, h1, h2, h3)={[ h0^3 + 3*h0*h1^2 + 3*h1^2*h2 + h2^3, h0^2*h1 + 2*h0*h1*h2 + h1^3 + 2*h1*h2^2 + h1^2*h3 + h2^2*h3, h0*h1^2 + 2*h1^2*h2 + h0*h2^2 + 2*h1*h2*h3 + h2^3 + h2*h3^2, h1^3 + 3*h1*h2^2 + 3*h2^2*h3 + h3^3]}
%o a(n) = {my(v); v=[1, 1, 0, 0]; for(i=1, n, v=Next(v[1], v[2], v[3], v[4])); v[1]} \\ _Andrew Howroyd_, Jun 17 2017
%Y Cf. A288839 (chromatic polynomials of the n-Hanoi graph).
%Y Cf. A193233 (chromatic polynomial with highest coefficients first).
%Y Cf. A137889 (directed Hamiltonian paths in the n-Hanoi graph).
%Y Cf. A288490 (independent vertex sets in the n-Hanoi graph).
%Y Cf. A193136 (spanning trees of the n-Hanoi graph).
%Y Cf. A288796 (undirected paths in the n-Hanoi graph).
%K nonn
%O 1,1
%A _Eric W. Weisstein_, Jun 16 2017
%E a(5) from _Andrew Howroyd_, Jun 17 2017
| 