Combinatorial proof of Hamiltonian paths on the rook graph

82 Views Asked by At

We can be sure that number of Hamiltonian paths on the rook graph for any single cell on $n\times2$ chessboard equals $$ H(n+1) = \sum_{k=0}^{n} \binom{n}{k} \binom{k}{\lfloor{\frac{k}{2}\rfloor}} \left(n-\lfloor{\frac{k}{2}\rfloor}\right)! \left(n-\lfloor{\frac{k+1}{2}\rfloor}\right)!$$ Is there a combinatorial proof for it?