Como determino o número de perturbações de “segundo grau”?

Question

O número de desarranjos para um determinado conjunto significa o número total de maneiras possíveis de embaralhar os membros de forma que nenhum membro se sente em seu lugar original. Isso é dado pelo formulário fechado:

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

Agora, dado um conjunto S e um de seus desarranjos D1, quantas maneiras existem para encontrar um novo (digamos, segundo grau) desarranjamento D2 com membros que não estão no mesmo lugar que S e D1 ao mesmo tempo ...

Answer 1

(Corrigido e expandido, novamente!)

Conforme mencionado nos comentários, o número de terceiras permutações depende da relação entre as duas primeiras. Assintoticamente, o número de terceiras permutações é$\sim e^{-2} n!\, (1-1/n - 1/(2n^2)+O(n^{-3}))$independentemente das duas primeiras permutações. Para o número exato, siga a dica de Ira: Riordan, Introdução à Análise Combinatória , capítulo 8, parte 3.

Posso dar uma dica de quanto o número de terceiras permutações varia de acordo com as duas primeiras. Deixei$s$ser o número de intercalados nas duas primeiras permutações. (Um intercalado é duas posições onde as duas permutações têm as mesmas duas entradas em ordem oposta: onde um tem$ab$ o outro tem $ba$.) Uma vez que os intercalados não podem se sobrepor, o número deles não pode exceder $n/2$. Assintoticamente, o número de terceiras permutações que são uma perturbação das duas primeiras é$$ e^{-2} n!\, \Bigl( 1 - \frac 1n - \frac 1{2n^2} + \frac 1{3n^3} + \frac {s}{n^4} + O(n^{-4})\Bigr).$$

Este é de CD Godsil e BD McKay, Asymptotic enumeration of Latin rectangles, J. Combinatorial Theory, Ser. B, 48 (1990) 19-44. Versão corrigida .

Um triplo de permutações, cada uma das duas sendo desarranjos uma da outra, é um retângulo latino de 3 linhas. Há um somatório simples para o número deles devido a Yamamoto, consulte a página 18 na pesquisa de Stone .

Answer 2

A resposta depende da estrutura do ciclo de $D_1$. Deixei$n:=|S|$ e $c_i$ seja o número de ciclos de comprimento $i$ dentro $D_1$ (com $\sum_i ic_i=n$) Desde a$D_1$ é uma perturbação, nós temos $c_1=0$, mas o que se segue aplica-se bem a qualquer permutação (não necessariamente perturbação) $D_1$ do $S$.

O número de permutações $D_2$ que são perturbações em relação à permutação de identidade, bem como $D_1$ é igual a $$\sum_{j=0}^n (-1)^j\cdot (n-j)!\cdot [z^j]\ F(z),$$ Onde $[z^j]\ F(z)$ é o coeficiente de $z^j$ dentro $$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}.$$

Isso pode ser obtido com o método descrito em meu artigo (em particular, veja a fórmula (4) e o Lema 1).

Casos particulares:

• quando $c_1=n$ (ou seja, $D_1$ é a permutação de identidade), obtemos apenas o número de perturbações;
• quando $c_n=1$ (ou seja, $D_1$é uma permutação cíclica), obtemos o número menage A000179 (n);
• quando $n=2m$ e $c_2=m$ (ou seja, $D_1$é um desarranjo e uma involução), temos A000316 (m) = A000459 (m)$\cdot 2^m$.