A286017 Number of matchings in the n-Hanoi graph.

4, 125, 4007754, 132460031222098852477, 4782311037918647241715144272946478084784910628903006412891408

Offset: 1

Author

Eric W. Weisstein, Jun 16 2017

Keywords

• nonn

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..7
• Eric Weisstein's World of Mathematics, Independent Edge Set
• Eric Weisstein's World of Mathematics, Matching
• Eric Weisstein's World of Mathematics, Hanoi Graph

Crossrefs

Cf. A288839 (chromatic polynomials of the n-Hanoi graph).

Cf. A193233 (chromatic polynomial with highest coefficients first).

Cf. A137889 (directed Hamiltonian paths in the n-Hanoi graph).

Cf. A288490 (independent vertex sets in the n-Hanoi graph).

Cf. A193136 (spanning trees of the n-Hanoi graph).

Cf. A288796 (undirected paths in the n-Hanoi graph).

Programs

Mathematica

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};
a[n_] := Module[{v = {1, 1, 0, 0}}, For[i = 1, i <= n, i++, v = next[v]]; v[[1]]];
Array[a, 5] (* Jean-François Alcover, Oct 02 2017, translated from Andrew Howroyd's PARI code *)
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 *)

PARI

\\ here h0..h3 are number of matchings in Hanoi graph less 0..3 apex vertices.
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]}
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

Extensions

a(5) from Andrew Howroyd, Jun 17 2017