Ménage numbers, bijections and P-recursiveness
type: Item
instance of: scholarly article
title: Ménage numbers, bijections and P-recursiveness
zbMATH Open document ID: 0617.05003
DOI: 10.1016/0012-365X(87)90002-1
author: E. Rodney Canfield
author: Nicholas Wormald
published in: Discrete Mathematics
publication date: 1987-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 11B39
zbMATH DE Number: 3999930
zbMATH Keywords: ménage number
zbMATH Keywords: permutations
zbMATH Keywords: recurrence
zbMATH Keywords: P-recursive
MaRDI profile type: Publication
cites work: Q3932918
cites work: Q5592263
cites work: Q5834385
cites work: Permanents of cyclic (0,1) matrices
cites work: The Enumeration of Locally Restricted Graphs (II)
cites work: Some Unusual Enumeration Problems
cites work: Number of labeled 4-regular graphs
cites work: Q3243274
cites work: Q3851094
cites work: Differentiably finite power series
cites work: The Algebra of Linear Partial Difference Operators and Its Applications
cites work: Sister Celine's technique and its generalizations
cites work: Enumeration of Labelled Graphs II: Cubic Graphs with a given Connectivity
cites work: The Hammond Series of a Symmetric Function and Its Application to P-Recursiveness
full work available at URL: 0012-365x(87)90002-1
OpenAlex ID: W2025532738
description: scientific article; zbMATH DE number 3999930