Ménage numbers, bijections and P-recursiveness (Q1821781)

The straight ménage number \(V^ k_ n\) is the number of permutations \(\sigma\) of \(\{\) 1,2,...,n\(\}\) such that \(\sigma\) (i) is not congruent to any of \(i,i+1,...,\min (i+k-1,n)\) (mod n). A direct combinatorial proof is given of the recurrence relation \(V^ 2_ n=(n-1)(V^ 2_{n- 1}+V^ 2_{n-2})+V^ 2_{n-3}.\) In the terminology of \textit{R. P. Stanley} [Eur. J. Comb. 1, 175-188 (1980; Zbl 0445.05012)] a sequence \((a_ n)\) is P-recursive if there are finitely many polynomials \(p_ i(n)\), \(0\leq i\leq d\), such that \(p_ 0(n)a_ n=\sum^{d}_{i=1}p_ i(n)a_{n-i}\) for all sufficiently large n. The method of proof enables the authors to show also that \(V^ 3_ n\) is P-recursive. The authors close by noting that after these results were obtained, Stanley proved that all \(V^ k_ n\) are P-recursive, as a special case of a more general result.