On the number of Hamiltonian cycles of \(P_ 4\times{} P_ n\) (Q1813274)

The Cartesian product (in other literature often called the Cartesian sum) of two simple graphs \(G_ 1=(V_ 1,E_ 1)\), \(G_ 2=(V_ 2,E_ 2)\) is the graph \(G_ 1\times G_ 2=(V,E)\) with \(V=V_ 1\times V_ 2\) and \(\{(x_ 1,x_ 2), (y_ 1,y_ 2)\}\in E\) iff \(x_ 2=y_ 2\), \(\{x_ 1,y_ 1\}\in E_ 1\) or \(x_ 1=y_ 1\), \(\{x_ 2,y_ 2\}\in E_ 2\). Let \(P_ n\) denote the path on \(n\) vertices, and \(H_ m(n)\) the number of Hamiltonian cycles in \(P_ m\times P_ n\). The authors give a characterization of the so-called signatures for the Hamiltonian cycles of the graph \(P_ 4\times P_ n\), an explicit formula for \(H_ 4(n)\) in terms of binomial coefficients, and a recurrence relation for \(H_ 4(n)\) enabling the determination of the explicit and asymptotic values of \(H_ 4(n)\), \(n\geq 2\). Abbreviating \(H_ 4(n)\) by \(H(n)\) they get in particular: \[ H(n)=\sum_ i\sum_ k2^{k-1}{n-1-2i\choose 2k- 1}{i+k-1\choose k-1}, \] where \(k\) runs from 1 to \(\lfloor(n-1-2^ i)/2\rfloor\) and \(i\) from \(0\) to \(\lfloor(n-1)/2\rfloor\); \[ H(n)=2H(n- 1)+2H(n-2)-2H(n-3)+H(n-4) \] for \(n\geq 5\) with \(H(4)=3H(3)=6H(2)=6\), \(H(1)=0\); the generating function of \(H(n)\) is \(\sum^ \infty_{n=0}H(n)x^ n=-x^ 2/F(x)\) with \(F(x)=x^ 4-2x^ 3-2x^ 2+2x-1\), and \(H(n)=\sum^ 4_{i=1}(\alpha_ i/F'(\alpha_ i))\alpha^ n_ i\), where \(\alpha_ 1,\dots,\alpha_ 4\) are the zeros of \(F(x)\) with approximate values 2,539; -1,276; \(0,369\pm 0,416i\), respectively; \(H(n)\sim 0,136\cdot(2,539)^ n+0,116\cdot(-1,276)^ n\) for \(n\to\infty\). There are some misprints.