Comment déterminer le nombre de dérangements de «second degré»?

Question

Le nombre de dérangements pour un ensemble donné est le nombre total de façons possibles de mélanger les membres de telle sorte qu'aucun membre ne se trouve à sa place d'origine. Ceci est donné par la forme fermée:

$$!n = n! \cdot \sum_{k=0}^{n}\frac{(-1)^k}{k!}$$

Maintenant, étant donné un ensemble S et l'un de ses dérangements D1, combien de façons existe-t-il de trouver un nouveau dérangement (disons de second degré) D2 avec des membres qui ne sont pas au même endroit que S et D1 en même temps ...

Answer 1

(Corrigé et développé, encore une fois!)

Comme mentionné dans les commentaires, le nombre de troisièmes permutations dépend de la relation entre les deux premières. De manière asymptotique, le nombre de troisièmes permutations est$\sim e^{-2} n!\, (1-1/n - 1/(2n^2)+O(n^{-3}))$indépendamment des deux premières permutations. Pour le nombre exact, suivez l'indice d'Ira: Riordan, Introduction à l'analyse combinatoire , chapitre 8, partie 3.

Je peux vous donner une idée de la variation du nombre de troisièmes permutations en fonction des deux premières. Laisser$s$être le nombre d'intercalations dans les deux premières permutations. (Un intercalaire est deux positions où les deux permutations ont les mêmes deux entrées dans l'ordre opposé: où l'on a$ab$ l'autre a $ba$.) Comme les intercalaires ne peuvent pas se chevaucher, leur nombre ne peut pas dépasser $n/2$. De manière asymptotique, le nombre de troisièmes permutations qui sont un dérangement des deux premières est$$ e^{-2} n!\, \Bigl( 1 - \frac 1n - \frac 1{2n^2} + \frac 1{3n^3} + \frac {s}{n^4} + O(n^{-4})\Bigr).$$

Ceci est tiré de CD Godsil et BD McKay, Asymptotic Enumeration of Latin rectangles, J. Combinatorial Theory, Ser. B, 48 (1990) 19-44. Version corrigée .

Un triple de permutations, dont deux sont des dérangements l'un de l'autre, est un rectangle latin de 3 rangées. Il y a une simple addition pour le nombre d'entre eux dus à Yamamoto, voir page 18 dans l'enquête de Stone .

Answer 2

La réponse dépend de la structure du cycle de $D_1$. Laisser$n:=|S|$ et $c_i$ être le nombre de cycles de longueur $i$ dans $D_1$ (avec $\sum_i ic_i=n$). Depuis$D_1$ est un dérangement, nous avons $c_1=0$, mais ce qui suit s'applique bien à toute permutation (pas forcément dérangement) $D_1$ de $S$.

Le nombre de permutations $D_2$ qui sont un dérangement par rapport à la permutation d'identité ainsi que par rapport à $D_1$ équivaut à $$\sum_{j=0}^n (-1)^j\cdot (n-j)!\cdot [z^j]\ F(z),$$ où $[z^j]\ F(z)$ est le coefficient de $z^j$ dans $$F(z) := (1+z)^{c_1}\cdot \prod_{i=2}^n \left( \left(\frac{1+\sqrt{1+4z}}2\right)^{2i} + \left(\frac{1-\sqrt{1+4z}}2\right)^{2i} \right)^{c_i}.$$

Ceci peut être obtenu avec la méthode décrite dans mon article (en particulier, voir la formule (4) et le lemme 1).

Cas particuliers:

• quand $c_1=n$ (c'est à dire, $D_1$ est la permutation d'identité), nous obtenons juste le nombre de dérangements;
• quand $c_n=1$ (c'est à dire, $D_1$est une permutation cyclique), on obtient le numéro de menage A000179 (n);
• quand $n=2m$ et $c_2=m$ (c'est à dire, $D_1$est un dérangement et une involution), on obtient A000316 (m) = A000459 (m)$\cdot 2^m$.