4

How many permutations on a set $[n]$ does there exist such that :

$$\forall k \in [n]:\sigma(k) \ne k \;\;\;\text{and}\;\;\;\forall k \in [n]\setminus\left\{1\right\}: \sigma (k) \ne k-1\;\;\;\text{and}\;\;\;\sigma (1) \ne n$$

Indeed we are looking for the derangement such that there does not exist any elements mapped to the element before itself (with the assumption that $\sigma (1) \ne n$).

Define: $$\overline A_{}:=\left\{\sigma \in S_{n}:\forall k \in [n]:\sigma(k) \ne k\right\}$$ $$\overline B_{}:=\left\{\sigma \in S_{n}:\forall k \in [n]\setminus\left\{1\right\}:\sigma(k) \ne k-1 \;\;\;\text{and}\;\;\;\sigma (1) \ne n \right\}$$

What we want can be derived using inclusion-exclusion :

$$n!-\ \left| A_{} \cup B\right|$$ $$=n!-\left| A_{} \right|-\left| B_{} \right|+\left| A \cap B_{} \right|$$ $$=n!-\bigcup_{k=1}^{n}\left|A_k\right|-\bigcup_{k=1}^{n}\left|B_k\right|+\bigcup_{k=1}^{n}\left|A_k\right| \cap \bigcup_{k=1}^{n}\left|B_k\right|$$

Where $A_k,B_k$ is the set of permutations with their $k$th term fixed.

From the number of derangement we conclude that :

$$\bigcup_{k=1}^{n}\left|A_k\right|=n!\sum_{i=1}^{n}\frac{\left(-1\right)^{i+1}}{i!}=\bigcup_{k=1}^{n}\left|B_k\right|$$

However for $\bigcup_{k=1}^{n}\left|A_k\right| \cap \bigcup_{k=1}^{n}\left|B_k\right|$ I could not find any closed form,even I could not finish the computation,besides I'm not sure if I've done the other part correctly.

Note:

  • What the question wants is a special case of a double derangement with two permutations $\text{id}(k),\pi(k) \in S_n$ such that $\text{id}(k)=k$ and $\pi(k)=k-1$.

  • The other cases has been discussed earlier:

The number of derangements on $[n]$ such that $\sigma(n) \ne n-1$ is:

$$\frac{\left(n-2\right)D_{n}}{n-1}$$

The number of derangements on $[n]$ such that $\sigma(n) \ne n-1$ and $\sigma(n-1) \ne n-2$ is:

$$\frac{\left(n-3\right)D_{n}}{n-1}+\frac{D_{n-1}}{n-2}$$

The number of derangements on $[n]$ such that $\sigma(n) \ne n-1$ and $\sigma(n-1) \ne n-2$ and $\sigma(n-2) \ne n-3$ is:

$$\frac{\left(n-4\right)D_{n}}{n-1}+\frac{3D_{n-1}}{n-2}$$

Added: The question is exactly Professor Tait's Problem of Arrangement,but I Want to know does there exist any way to continue from my way? besides are the three partial cases helpful to derive a formula for the main problem?

Community
  • 1
  • 1
    This is related to the ménage problem, and the sequence is listed in OEIS as A000179. The first ten values are therefore $$0, \quad 0, \quad 1, \quad 2, \quad 13, \quad 80, \quad 579, \quad 4738, \quad 43387, \quad 439792, \quad \cdots.$$ – Sangchul Lee May 16 '20 at 10:24
  • 1
    @SangchulLee,thanks,but I've already seen that,the problem is that I cannot find the formula. –  May 16 '20 at 10:32
  • 1
    According to John Riordan's Introduction to Combinatorial Analysis, the formula is $$\sum_{k=0}^{n}(-1)^k\frac{2n}{2n-k}\binom{2n-k}{k}(n-k)!, \qquad n \geq 2.$$ I am no expert on this subject, however, so I am not sure how I can obtain this by myself. – Sangchul Lee May 16 '20 at 10:34
  • 1
    @ SangchulLee,there is a book named Théorie des nombres by Lucas, Edouard, which has proved that :$$M_{n}=2\left(n!\right)H_{n}$$ Where $M_n$ is the nth menage number and $H_n$ is the number of such derangement on $[n]$,however the book is in French –  May 16 '20 at 10:35
  • 1
    Excuse me if this is a silly question: This question is exactly the menage problem, right? (Up to a factor of $n$, because circle vs a line.) And the wikipedia article gives a formula involving a summation, which is also quoted by @SangchulLee above. What exactly are you asking for? If you agree this is equivalent to menage, then are you asking for a closed form solution to Menage when wikipedia didn't list any? – antkam May 16 '20 at 20:41
  • 3
    @ antkam,This is not the menage problem,there is a relation related to menage problem which states $$M_n=2\left(n!\right)U_{n}$$ Where $U_n$ is the number of ways of seating men,and $M_n$ is the menage numbers.Lucas, in his book Th´eorie des nombres(page 495) gives a recurrence relation for $U_n$,on the other hand Cayley found another formula for the number of derangements $H_n$ on $[n]$ such that $$\pi(i) \ne i+1;;\text{mod (n)}\tag{$ \forall i \in [n]$}$$The formula was the same as Lucas',which implies $H_n=U_n$. –  May 17 '20 at 07:10
  • 2
    @ antkam as you see my question is not the same as the menage problem,it's just related to that problem,besides the book "Théorie des nombres" is in French,and I could not find any English version,so at this moment there does not exist any reference to learn about what Lucas has mentioned . –  May 17 '20 at 07:15
  • Have you seen The problème des ménages revisited by Lefteris Kirousis and Georgios Kontogeorgiou? It contains a fairly simple proof of the formula in Sangchul Lee's comment. I'm still a bit unclear on what you want to know. I assume you understand why the ménage problem and your problem differ by a factor of $2\cdot n!$? Many English-language books have proofs of Touchard's formula, so I'm not sure why you need to go back to Lucas, which doesn't contain that formula anyway. – Will Orrick May 17 '20 at 15:50
  • 3
    @ WillOrrick,thanks for the reference,but assume I'm a person who wants to explore the answer of the question without knowing the existence of menage problem,then what will happen?most of people will say there does not exist such way,but I disagree,Lucas and Cayley provide a recurrence which is as follows: $$(n-2)U_n= n(n − 2)U_{n−1} + nU_{n−2} + 4(−1)^{n+1}$$But where does that come from?well the only reference on the internet I've found is a French book I've mentioned before and I don't know French,besides I want to know does there exist to use my way or not (which I believe the answer is no –  May 17 '20 at 16:05
  • OK it seems to me (1) you agree that your problem differs from the Menage problem by just a factor, and therefore solving one equals solving the other; (2) you would like to see either the Menage problem, or your problem, solved in full, resulting in e.g. @SangchulLee's quoted formula (up to a factor), and (3) you would like to see the full solution because you cannot access the various French journals. Am I right? – antkam May 18 '20 at 01:23
  • @ankam Obviously I can't speak for the original poster, but based on their response just above your most recent comment and their edits to the post, it seems they want a derivation using inclusion-exclusion like the one one often sees for the usual derangements problem. They also want, if possible, a formula generalizing the three special formulas involving derangements at the end of their post. It also seems they are more interested in the recurrence for $U_n$ than in the Touchard formula. Finally, in asking to pretend they don't know about ménage, I'm guessing they want to avoid... – Will Orrick May 18 '20 at 01:56
  • ..analyses that bring in $2n$ items, preferring those that involve only $n$ items. There are ways of satisfying the letter of this last requirement while violating its spirit, by simply omitting mention of the $n$ intervening slots. I don't know if that would be acceptable. The first two requirements seem hard to me. Inclusion-exclusion seems much trickier to me when two requirements have to be imposed simultaneously, i.e. handling the $A\cap B$ term. – Will Orrick May 18 '20 at 02:01
  • There's a nice little paper on the menage problem by Bogart and Doyle called A non-sexist solution to the menage problem:

    https://math.dartmouth.edu/~doyle/docs/menage/menage/menage.html

    It is an inclusion/exclusion based approach, but not based on derangements. In the concluding discussion, they point out that approaches based on derangements appear fundamentally more difficult than the proof they outline (as of 1985). That said, I agree it would be interesting to find a direct proof of the summation formula without the $2 n!$ term.

     – Zach H May 21 '20 at 10:31
  • 2
    @ Zach,Thank you for the link, I've already read that,the second approach is nice,but it's clear we use $U_n$ to derive an explicit formula for menage numbers,not vice versa,this is the point,the only relation that is used to derive a formula for $U_n$,is the one which is a recurrence relation,I was trying to use the inclusion-exclusion principle to derive a formula (or maybe using some other partial cases,which is mentioned before),but it's so unlikely,as I know these kind of approaches are not used in combinatorics . –  May 21 '20 at 10:45
  • @Zach If you read the Bogart and Doyle article you should also read the Kirousis and Kontogeorgiou article I mentioned above. Here's the link again. The key insight in Bogart and Doyle's approach is the domino idea, not eliminating ladies-first. If you apply Bogart and Doyle's domino idea but stick with ladies-first you get an even easier derivation. In fact, once you have the domino idea the Touchard formula becomes a triviality and basically writes itself. – Will Orrick May 21 '20 at 13:10
  • @Zach Now that I compare the arguments in Kaplansky's 1943 article, Bogart and Doyle's 1985 article, and Kirousis and Kontogeorgiou's 2018 article, I can't say that I see any essentially differences among them. The essential mathematical idea is exactly the same; only style and presentation details differ. And I'm not sure why these don't count as finding "a direct proof of the summation formula without the $2n!$ term." – Will Orrick May 21 '20 at 15:46

0 Answers0