What is the number of perfect matchings on the one-dimensional skeleton of a $k$ dimensional cube?

147 Views Asked by At

Let $Q_k$ denote the one skeleton of the $k$-dimensional cube. How many perfect matchings are there in $Q_k$?

I honestly don't even have a clue for this question. For $k=1$, there is trivially one, for $k=2$, there are two, for $k=3$, there are nine? Some people in my class have said that it should be $k^2$, but I have not seen any literature on this subject; wikipedia only gives a lower bound for this. It seems like if there were an answer, it would be provided somewhere on the internet. A sketch of a proof or a link would be great. Thanks.

Edit: I do not have a sound definition of $Q_k$, nor even the $k$ dimensional cube. Even an answer providing definitions of those would be helpful.

1

There are 1 best solutions below

2
On BEST ANSWER

The number of complete matchings in the hypercube graph $Q_n$ is sequence A005271 in The On-Line Encyclopedia of Integer Sequences. It seems to be a hard problem; apparently the exact number is known only for $n\le7$:

1
2
9
272
589185
16332454526976
391689748492473664721077609089