Let $m>1$ be an integer. Let $P(m)$ be the set of permutations of $\{0,\dots,m-1\}$. Then the $m$th Rencontres number $R(m)$ may be defined in any of these ways:
- the number of rencontres of the first kind, i.e. permutations $p\in P(m)$ where $p(r)\ne p(r-1)+1$ for $r=0,\dots,m-1$ and indexing $p$ is modulo $m$, so $p(0)\ne p(m-1)+1$ is required; however, the equality is in $\mathbb{Z}$, so $p(r)=0, p(r-1)=m-1$ is allowed. (These are the circularly nonconsecutive (CNC) permutations in Mike Earnest's question.)
- the number of rencontres of the second kind, i.e. permutations $p\in P(m)$ where $p(r)\not\equiv p(r-1)+1\mod m$ for $r=1,\dots,m-1$, and the equality is modulo $m$, so $p(r)\equiv0, p(r-1)\equiv m-1$ is banned; however, the indexing is in $\mathbb{Z}$, so $p(0)\equiv p(m-1)+1$ is allowed.
- the number of rencontres of the third kind, i.e. permutations $p\in P(m)$ with exactly one fixed point; that is, there is one $r$ where $p(r)=r$.
(Yes, I know that I'm extending the usage of "rencontre" in a non-standard way, but if I don't know the term for something I must invent one.)
It is easy to see that the first and second definitions are equivalent because $p$ is a rencontre of the first kind iff $p^{-1}$ is a rencontre of the second kind.
But how come the second and third definitions are equivalent?.
Thoughts I have had, which seem not to lead to a proof:
For any function $f:\mathbb{Z}\mapsto\mathbb{Z}/m$, define $d(f)$ by $d(f)(r)\equiv f(r)-r\mod m$. Then $p$ is a rencontre of the second kind iff $d(p)$ never takes the same value twice in succession, and $p$ is a rencontre of the third kind iff $d(p)$ is never 0.
I can't see a bijection; a difficulty is that the former condition is $m-1$ inequalities on values of $d$; but the latter is $m$ inequalities. Admittedly one could define $\Sigma$ by $\Sigma(f)(0)=0$, $\Sigma(f)(r)=\Sigma(f)(r-1)+d(f)(r)$. Then $p$ is a rencontre of the third kind iff $d(p)$ is never 0 iff $\Sigma(p)$ never takes the same value twice in succession. But there's no guarantee that $\Sigma(p)=d(q)$ where $q$ is a permutation.
For any rencontre $p:\mathbb{Z}/m\mapsto\mathbb{Z}/m$ of the third kind, with fixed point $a$, define $e(p)$ by $e(p)(r)\equiv p(r+a+1)-a-1$. Then $e(p)(-1)\equiv p(a)-a-1\equiv a-a-1\equiv-1$ and $e|_{0,\dots,m-2}$ has no fixed points and is thus a derangement. Conversely, for every derangement $d$ of $0,\dots,m-2$, one may construct a rencontre $p:\mathbb{Z}/m\mapsto\mathbb{Z}/m$ of the third kind, with fixed point $a$, by $p(a)\equiv a$, and, for $r\ne a$, $p(r)\equiv d(r-a-1)+a+1$. There are $m$ options for $a$, and $!(m-1)$ options for $d$, and thus $m\cdot!(m-1)$ rencontres of the third kind.
For any rencontre $p:\mathbb{Z}\mapsto\mathbb{Z}/m$ of the second kind, define $g(p)$ by $g(p)(r)\equiv p(r)-p(m-1)-1$. Then $g$ is also a rencontre of the second kind, with $g(m-1)\equiv -1$. As $p$ permutes $\{0,\dots,m-1\}$, $g|_{0,\dots,m-2}$ permutes $\{0,\dots,m-2\}$. However, $g$ might not be a derangement. For example, if $m=4$ and $p=(12)=[0213]$, then $g(p)=p$ and has the fixed point 0.
My trouble is that I can't see any combinatorial link between the restriction on fixed points and the restriction on "up-steps" (occurrences of $p(r)=p(r-1)+1$).
If there is a proof, then one which is less complicated than the inclusion-exclusion principle would be preferable.