Combinatorial proof of Hamiltonian paths on the rook graph

85 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?