Estatísticas de permutação aleatória - Random permutation statistics

As estatísticas de permutações aleatórias , como a estrutura do ciclo de uma permutação aleatória, são de fundamental importância na análise de algoritmos , especialmente de algoritmos de ordenação, que operam em permutações aleatórias. Suponha, por exemplo, que estejamos usando quickselect (um primo de quicksort ) para selecionar um elemento aleatório de uma permutação aleatória. O Quickselect realizará uma classificação parcial no array, pois ele particiona o array de acordo com o pivô. Conseqüentemente, uma permutação ficará menos desordenada depois que a seleção rápida for realizada. A quantidade de desordem que permanece pode ser analisada com funções geradoras. Essas funções geradoras dependem fundamentalmente das funções geradoras das estatísticas de permutação aleatória. Portanto, é de vital importância computar essas funções geradoras.

O artigo sobre permutações aleatórias contém uma introdução às permutações aleatórias.

A relação fundamental

Permutações são conjuntos de ciclos rotulados. Usando o caso rotulado do teorema fundamental Flajolet-Sedgewick e escrevendo para o conjunto de permutações e para o conjunto singleton, temos ${\ displaystyle \ scriptstyle {\ mathcal {P}}}$${\ displaystyle \ scriptstyle {\ mathcal {Z}}}$

${\ displaystyle \ operatorname {SET} (\ operatorname {CYC} ({\ mathcal {Z}})) = {\ mathcal {P}}.}$

Traduzindo em funções geradoras exponenciais (EGFs), temos

${\ displaystyle \ exp \ left (\ log {\ frac {1} {1-z}} \ right) = {\ frac {1} {1-z}}}$

onde usamos o fato de que o EGF das espécies combinatórias de permutações (há n ! permutações de n elementos) é

${\ displaystyle \ sum _ {n \ geq 0} {\ frac {n!} {n!}} z ^ {n} = {\ frac {1} {1-z}}.}$

Esta única equação permite derivar um grande número de estatísticas de permutação. Em primeiro lugar, retirando os termos de , ou seja, exp, podemos restringir o número de ciclos que uma permutação contém, por exemplo, restringindo o EGF para obter permutações contendo dois ciclos. Em segundo lugar, observe que o EGF dos ciclos marcados, ou seja , é ${\ displaystyle \ scriptstyle \ operatorname {SET}}$${\ displaystyle \ scriptstyle \ operatorname {SET} _ {2}}$${\ displaystyle \ scriptstyle \ operatorname {CYC} ({\ mathcal {Z}})}$

${\ displaystyle \ sum _ {k \ geq 1} {\ frac {(k-1)! z ^ {k}} {k!}} = \ sum _ {k \ geq 1} {\ frac {z ^ { k}} {k}} = \ log {\ frac {1} {1-z}}}$

porque existem k! / k ciclos rotulados. Isso significa que, eliminando termos dessa função geradora, podemos restringir o tamanho dos ciclos que ocorrem em uma permutação e obter um EGF das permutações contendo apenas ciclos de um determinado tamanho.

Em vez de remover e selecionar ciclos, também se pode colocar pesos diferentes em ciclos de tamanhos diferentes. Se é uma função de peso que depende apenas do tamanho k do ciclo e por brevidade escrevemos ${\ displaystyle b: \ mathbb {N} \ rightarrow \ mathbb {R}}$

${\ displaystyle b (\ sigma) = \ sum _ {c \ in \ sigma} b (c),}$

definindo o valor de b para uma permutação como a soma de seus valores nos ciclos, então podemos marcar ciclos de comprimento k com u ^{b ( k )} e obter uma função geradora de duas variáveis ${\ displaystyle \ sigma}$

${\ displaystyle g (z, u) = 1 + \ sum _ {n \ geq 1} \ left (\ sum _ {\ sigma \ in S_ {n}} u ^ {b (\ sigma)} \ right) { \ frac {z ^ {n}} {n!}} = \ exp \ sum _ {k \ geq 1} u ^ {b (k)} {\ frac {z ^ {k}} {k}}}$

Esta é uma função geradora "mista": é uma função geradora exponencial em ze uma função geradora comum no parâmetro secundário u. Diferenciando e avaliando em u  = 1, temos

${\ displaystyle {\ frac {\ partial} {\ partial u}} g (z, u) {\ Bigg |} _ {u = 1} = {\ frac {1} {1-z}} \ sum _ { k \ geq 1} b (k) {\ frac {z ^ {k}} {k}} = \ sum _ {n \ geq 1} \ left (\ sum _ {\ sigma \ in S_ {n}} b (\ sigma) \ right) {\ frac {z ^ {n}} {n!}}}$

Esta é a função geradora de probabilidade da expectativa de b . Em outras palavras, o coeficiente de nesta série de potências é o valor esperado de b nas permutações em , dado que cada permutação é escolhida com a mesma probabilidade . ${\ displaystyle z ^ {n}}$${\ displaystyle S_ {n}}$${\ displaystyle 1 / n!}$

Este artigo usa o operador de extração de coeficiente [ z ⁿ ], documentado na página para séries de potências formais .

Número de permutações que são involuções

Uma involução é uma permutação σ de forma que σ ² = 1 sob a composição de permutação. Segue-se que σ pode conter apenas ciclos de comprimento um ou dois, ou seja, a função geradora exponencial g ( z ) dessas permutações é

${\ displaystyle g (z) = \ exp \ left (z + {\ frac {1} {2}} z ^ {2} \ right).}$

Isso dá a fórmula explícita para o número total de involuções entre as permutações σ ∈  S _n : ${\ displaystyle I (n)}$

${\ displaystyle I (n) = n! [z ^ {n}] g (z) = n! \ sum _ {a + 2b = n} {\ frac {1} {a! \; 2 ^ {b} \; b!}} = n! \ sum _ {b = 0} ^ {\ lfloor n / 2 \ rfloor} {\ frac {1} {(n-2b)! \; 2 ^ {b} \; b !}}.}$

Dividindo por n ! produz a probabilidade de que uma permutação aleatória seja uma involução. Esses números são conhecidos como números de telefone .

Número de permutações que são m th raízes da unidade

Isso generaliza o conceito de uma involução. Uma m- ésima raiz da unidade é uma permutação σ de modo que σ ^m = 1 sob a composição de permutação. Agora, toda vez que aplicamos σ, movemos um passo em paralelo ao longo de todos os seus ciclos. Um ciclo de comprimento d aplicado d vezes produz a permutação de identidade em d elementos ( d pontos fixos) ed é o menor valor para isso. Portanto, m deve ser um múltiplo de todos os tamanhos de ciclo d , ou seja, os únicos ciclos possíveis são aqueles cujo comprimento d é um divisor de m . Conclui-se que o EGF g ( x ) dessas permutações é

${\ displaystyle g (z) = \ exp \ left (\ sum _ {d \ mid m} {\ frac {z ^ {d}} {d}} \ right).}$

Quando m = p , onde p é primo, isso simplifica para

${\ displaystyle n! [z ^ {n}] g (z) = n! \ sum _ {a + pb = n} {\ frac {1} {a! \; p ^ {b} \; b!} } = n! \ sum _ {b = 0} ^ {\ lfloor n / p \ rfloor} {\ frac {1} {(n-pb)! \; p ^ {b} \; b!}}.}$

Número de permutações de ordem exatamente k

Isso pode ser feito por inversão de Möbius . Trabalhando com o mesmo conceito da entrada anterior, notamos que as espécies combinatórias de permutações cuja ordem divide k é dada por ${\ displaystyle {\ mathcal {Q}}}$

${\ displaystyle {\ mathcal {Q}} = \ operatorname {SET} \ left (\ sum _ {d \ mid k} \ operatorname {CYC} _ {= d} ({\ mathcal {Z}}) \ right) .}$

Traduzindo para funções geradoras exponenciais, obtemos o EGF de permutações cuja ordem divide k , que é

${\ displaystyle Q_ {k} (z) = \ exp \ left (\ sum _ {d \ mid k} {\ frac {z ^ {d}} {d}} \ right).}$

Agora podemos usar esta função geradora para contar permutações de ordem exatamente k . Seja o número de permutações em n cuja ordem é exatamente d e o número de permutações em n a contagem de permutação cuja ordem divide k . Então nós temos ${\ displaystyle p_ {n, d}}$${\ displaystyle q_ {n, k}}$

${\ displaystyle \ sum _ {d | k} p_ {n, d} = q_ {n, k}.}$

Segue-se pela inversão de Möbius que

${\ displaystyle \ sum _ {d | k} q_ {n, d} \ times \ mu (k / d) = p_ {n, k}.}$

Portanto, temos o EGF

${\ displaystyle Q (z) = \ sum _ {d \ mid k} \ mu (k / d) \ vezes Q_ {d} (z) = \ sum _ {d \ mid k} \ mu (k / d) \ exp \ left (\ sum _ {m \ mid d} {\ frac {z ^ {m}} {m}} \ right).}$

A contagem desejada é então fornecida por

${\ displaystyle n! [z ^ {n}] Q (z).}$

Esta fórmula produz, por exemplo, para k  = 6 o EGF

${\ displaystyle Q (z) = {\ rm {e}} ^ {z} - {\ rm {e}} ^ {z + 1/2 \, z ^ {2}} - {\ rm {e}} ^ {z + 1/3 \, z ^ {3}} + {\ rm {e}} ^ {z + 1/2 \, z ^ {2} +1/3 \, z ^ {3} +1 / 6 \, z ^ {6}}}$

com a sequência de valores começando em n  = 5

${\ displaystyle 20.240,1470,10640,83160,584640,4496030,42658440,371762820,3594871280, \ ldots}$(sequência A061121 no OEIS )

Para k  = 8, obtemos o EGF

${\ displaystyle Q (z) = - {\ rm {e}} ^ {z + 1/2 \, z ^ {2} +1/4 \, z ^ {4}} + {\ rm {e}} ^ {z + 1/2 \, z ^ {2} +1/4 \, z ^ {4} +1/8 \, z ^ {8}}}$

com a sequência de valores começando em n  = 8

${\ displaystyle 5040,45360,453600,3326400,39916800,363242880,3874590720,34767532800, \ ldots}$(sequência A061122 no OEIS )

Finalmente, para k  = 12, obtemos o EGF

${\ displaystyle Q (z) = {\ rm {e}} ^ {z + 1/2 \, z ^ {2}} - {\ rm {e}} ^ {z + 1/2 \, z ^ { 2} +1/4 \, z ^ {4}} - {\ rm {e}} ^ {z + 1/2 \, z ^ {2} +1/3 \, {z} ^ {3} + 1/6 \, z ^ {6}} + {\ rm {e}} ^ {z + 1/2 \, z ^ {2} +1/3 \, z ^ {3} +1/4 \, z ^ {4} +1/6 \, z ^ {6} +1/12 \, z ^ {12}}}$

com a sequência de valores começando em n  = 7

${\ displaystyle 420,3360,30240,403200,4019400,80166240,965284320,12173441280,162850287600, \ ldots}$(sequência A061125 no OEIS )

Número de permutações que são desarranjos

Suponha que haja n pessoas em uma festa, cada uma trazendo um guarda-chuva. No final da festa, todos pegam um guarda-chuva da pilha de guarda-chuvas e folhas. Qual é a probabilidade de que ninguém tenha saído com seu guarda-chuva? Este problema é equivalente a contar permutações sem pontos fixos (chamadas de desarranjos ) e, portanto, o EGF, onde subtraímos pontos fixos (ciclos de comprimento 1) removendo o termo z da relação fundamental é

${\ displaystyle \ exp \ left (-z + \ sum _ {k \ geq 1} {\ frac {z ^ {k}} {k}} \ right) = {\ frac {e ^ {- z}} {1 -z}}.}$

A multiplicação por soma dos coeficientes de , portanto , o número total de desarranjos, é dado por: ${\ displaystyle 1 / (1-z)}$${\ displaystyle e ^ {- z}}$${\ displaystyle D (n)}$

${\ displaystyle D (n) = n! \ sum _ {k = 0} ^ {n} {\ frac {(-1) ^ {k}} {k!}} \; \ aprox \; {\ frac { n!} {e}}.}$

Portanto, há cerca de perturbações e a probabilidade de que uma permutação aleatória seja uma perturbação é${\ displaystyle n! / e}$${\ displaystyle 1 / e.}$

Este resultado também pode ser comprovado por inclusão-exclusão . Usando os conjuntos onde para designar o conjunto de permutações que fix p , temos ${\ displaystyle A_ {p}}$${\ displaystyle {\ begin {matriz} 1 \ leq p \ leq n \ end {matriz}}}$

${\ displaystyle \ left | \ bigcup _ {p} A_ {p} \ right | = \ sum _ {p} \ left | A_ {p} \ right | \; - \; \ sum _ {p <q} \ esquerda | A_ {p} \ cap A_ {q} \ direita | \; + \; \ sum _ {p <q <r} \ esquerda | A_ {p} \ cap A_ {q} \ cap A_ {r} \ direita | \; - \; \ cdots \; \ pm \; \ left | A_ {p} \ cap \; \ cdots \; \ cap A_ {s} \ right |.}$

Esta fórmula conta o número de permutações que possuem pelo menos um ponto fixo. As cardinalidades são as seguintes:

${\ displaystyle \ left | A_ {p} \ right | = (n-1)! \;, \; \; \ left | A_ {p} \ cap A_ {q} \ right | = (n-2)! \;, \; \; \ left | A_ {p} \ cap A_ {q} \ cap A_ {r} \ right | = (n-3)! \;, \; \ ldots}$

Portanto, o número de permutações sem ponto fixo é

${\ displaystyle n! \; \; - \; \; {n \ escolha 1} (n-1)! \; \; + \; \; {n \ escolha 2} (n-2)! \; \ ; - \; \; {n \ escolha 3} (n-3)! \; \; + \; \; \ cdots \; \; \ pm \; \; {n \ escolha n} (nn)!}$

ou

${\ displaystyle n! \ left (1 - {\ frac {1} {1!}} + {\ frac {1} {2!}} - {\ frac {1} {3!}} + \ cdots \ pm {\ frac {1} {n!}} \ right) = n! \ sum _ {k = 0} ^ {n} {\ frac {(-1) ^ {k}} {k!}}}$

e nós temos a reclamação.

Há uma generalização desses números, que é conhecida como números rencontres , ou seja, o número de permutações contendo m pontos fixos. O EGF correspondente é obtido marcando ciclos de tamanho um com a variável u , ou seja, escolhendo b ( k ) igual a um para e zero caso contrário, o que produz a função geradora do conjunto de permutações pelo número de pontos fixos: ${\ displaystyle D (n, m)}$${\ displaystyle [n]}$${\ displaystyle k = 1}$${\ displaystyle g (z, u)}$

${\ displaystyle g (z, u) = \ exp \ left (-z + uz + \ sum _ {k \ geq 1} {\ frac {z ^ {k}} {k}} \ right) = {\ frac { e ^ {- z}} {1-z}} e ^ {uz}.}$

Segue que

${\ displaystyle [u ^ {m}] g (z, u) = {\ frac {e ^ {- z}} {1-z}} {\ frac {z ^ {m}} {m!}}}$

e, portanto

${\ displaystyle D (n, m) = n! [z ^ {n}] [u ^ {m}] g (z, u) = {\ frac {n!} {m!}} [z ^ {nm }] {\ frac {e ^ {- z}} {1-z}} = {\ frac {n!} {m!}} \ sum _ {k = 0} ^ {nm} {\ frac {(- 1) ^ {k}} {k!}}.}$

Isso imediatamente implica que

${\ displaystyle D (n, m) = {n \ escolha m} D (nm, 0) \; \; {\ text {and}} \; \; {\ frac {D (n, m)} {n !}} \ approx {\ frac {e ^ {- 1}} {m!}}}$

para n grande, m fixo.

Ordem de uma permutação aleatória

Se P é uma permutação, a ordem de P é o menor inteiro positivo n para o qual é a permutação de identidade. Este é o menor múltiplo comum dos comprimentos dos ciclos de P . ${\ displaystyle P ^ {n}}$

Um teorema de Goh e Schmutz afirma que se é a ordem esperada de uma permutação aleatória de tamanho n , então ${\ displaystyle \ mu _ {n}}$

${\ displaystyle \ log \ mu _ {n} \ sim c {\ sqrt {\ frac {n} {\ log n}}}}$

onde a constante c é

${\ displaystyle 2 {\ sqrt {2 \ int _ {0} ^ {\ infty} \ log \ log \ left ({\ frac {e} {1-e ^ {- t}}} \ right) dt}} \ approx 1.1178641511899}$

Perturbações contendo um número par e ímpar de ciclos

Podemos usar a mesma construção da seção anterior para calcular o número de desarranjos contendo um número par de ciclos e o número contendo um número ímpar de ciclos. Para fazer isso, precisamos marcar todos os ciclos e subtrair pontos fixos, dando ${\ displaystyle D_ {0} (n)}$${\ displaystyle D_ {1} (n)}$

${\ displaystyle g (z, u) = \ exp \ left (-uz + u \ log {\ frac {1} {1-z}} \ right) = \ exp (-uz) \ left ({\ frac { 1} {1-z}} \ right) ^ {u}.}$

Agora, um raciocínio muito básico mostra que o EGF de é dado por ${\ displaystyle q (z)}$${\ displaystyle D_ {0} (n)}$

${\ displaystyle q (z) = {\ frac {1} {2}} \ times g (z, -1) + {\ frac {1} {2}} \ times g (z, 1) = {\ frac {1} {2}} \ exp (-z) {\ frac {1} {1-z}} + {\ frac {1} {2}} \ exp (z) (1-z).}$

Portanto, temos

${\ displaystyle D_ {0} (n) = n! [z ^ {n}] q (z) = {\ frac {1} {2}} n! \ sum _ {k = 0} ^ {n} { \ frac {(-1) ^ {k}} {k!}} + {\ frac {1} {2}} n! {\ frac {1} {n!}} - {\ frac {1} {2 }} n! {\ frac {1} {(n-1)!}}}$

qual é

${\ displaystyle {\ frac {1} {2}} n! \ sum _ {k = 0} ^ {n} {\ frac {(-1) ^ {k}} {k!}} + {\ frac { 1} {2}} (1-n) \ sim {\ frac {1} {2e}} n! + {\ Frac {1} {2}} (1-n).}$

Subtraindo de , encontramos ${\ displaystyle D_ {0} (n)}$${\ displaystyle D (n)}$

${\ displaystyle D_ {1} (n) = {\ frac {1} {2}} n! \ sum _ {k = 0} ^ {n} {\ frac {(-1) ^ {k}} {k !}} - {\ frac {1} {2}} (1-n).}$

A diferença entre esses dois ( e ) é${\ displaystyle D_ {0} (n)}$${\ displaystyle D_ {1} (n)}$${\ displaystyle n-1.}$

Cem prisioneiros

Um diretor da prisão quer abrir espaço em sua prisão e está considerando a libertação de cem prisioneiros, libertando assim cem celas. Ele, portanto, reúne cem prisioneiros e pede-lhes que joguem o seguinte jogo: ele alinha cem urnas em uma fileira, cada uma contendo o nome de um prisioneiro, onde o nome de cada prisioneiro ocorre exatamente uma vez. O jogo é jogado da seguinte forma: cada prisioneiro tem permissão para olhar dentro de cinquenta urnas. Se ele ou ela não encontrar seu nome em uma das cinquenta urnas, todos os presos serão executados imediatamente, caso contrário o jogo continua. Os presos têm alguns momentos para decidir a estratégia, sabendo que uma vez iniciado o jogo, eles não poderão se comunicar, marcar as urnas de forma alguma ou movimentar as urnas ou os nomes dentro delas. Escolhendo urnas ao acaso, suas chances de sobrevivência são quase zero, mas existe uma estratégia que lhes dá 30% de chance de sobrevivência, supondo que os nomes sejam atribuídos às urnas aleatoriamente - o que é?

Em primeiro lugar, a probabilidade de sobrevivência usando escolhas aleatórias é

${\ displaystyle \ left ({\ frac {99 \ escolha 49} {100 \ escolha 50}} \ right) ^ {100} = {\ frac {1} {2 ^ {100}}},}$

então esta definitivamente não é uma estratégia prática.

A estratégia de sobrevivência de 30% é considerar o conteúdo das urnas como uma permutação dos prisioneiros e ciclos transversais. Para manter a notação simples, atribua um número a cada prisioneiro, por exemplo, classificando seus nomes em ordem alfabética. Posteriormente, as urnas podem ser consideradas como contendo números em vez de nomes. Agora, claramente, o conteúdo das urnas define uma permutação. O primeiro prisioneiro abre a primeira urna. Se ele encontrar seu nome, ele terminou e sobreviveu. Caso contrário, ele abre a urna com o número que encontrou na primeira urna. O processo se repete: o preso abre uma urna e sobrevive se encontrar seu nome, caso contrário, abre a urna com o número que acabou de recuperar, até o limite de cinquenta urnas. O segundo prisioneiro começa com a urna número dois, o terceiro com a urna número três e assim por diante. Essa estratégia é precisamente equivalente a uma travessia dos ciclos da permutação representada pelas urnas. Cada prisioneiro começa com a urna com seu número e segue percorrendo seu ciclo até o limite de cinquenta urnas. O número da urna que contém seu número é a pré-imagem desse número sob a permutação. Conseqüentemente, os prisioneiros sobrevivem se todos os ciclos da permutação contiverem no máximo cinquenta elementos. Temos que mostrar que essa probabilidade é de pelo menos 30%.

Observe que isso pressupõe que o diretor escolhe a permutação aleatoriamente; se o diretor antecipar essa estratégia, ele pode simplesmente escolher uma permutação com um ciclo de 51. Para superar isso, os prisioneiros podem concordar previamente com uma permutação aleatória de seus nomes.

Consideramos o caso geral de presos e urnas sendo abertas. Primeiro calculamos a probabilidade complementar, ou seja, que existe um ciclo de mais de elementos. Com isso em mente, apresentamos ${\ displaystyle 2n}$${\ displaystyle n}$${\ displaystyle n}$

${\ displaystyle g (z, u) = \ exp \ left (z + {\ frac {z ^ {2}} {2}} + {\ frac {z ^ {3}} {3}} + \ cdots + u {\ frac {z ^ {n + 1}} {n + 1}} + u {\ frac {z ^ {n + 2}} {n + 2}} + \ cdots \ right)}$

ou

${\ displaystyle {\ frac {1} {1-z}} \ exp \ left ((u-1) \ left ({\ frac {z ^ {n + 1}} {n + 1}} + {\ frac {z ^ {n + 2}} {n + 2}} + \ cdots \ direita) \ direita),}$

de modo que a probabilidade desejada seja

${\ displaystyle [z ^ {2n}] [u] g (z, u),}$

porque o ciclo de mais do que elementos será necessariamente único. Usando o fato de que , descobrimos que ${\ displaystyle n}$${\ displaystyle 2 (n + 1)> 2n}$

${\ displaystyle [z ^ {2n}] [u] g (z, u) = [z ^ {2n}] [u] {\ frac {1} {1-z}} \ left (1+ (u- 1) \ left ({\ frac {z ^ {n + 1}} {n + 1}} + {\ frac {z ^ {n + 2}} {n + 2}} + \ cdots \ right) \ right ),}$

que produz

${\ displaystyle [z ^ {2n}] [u] g (z, u) = [z ^ {2n}] {\ frac {1} {1-z}} \ left ({\ frac {z ^ {n +1}} {n + 1}} + {\ frac {z ^ {n + 2}} {n + 2}} + \ cdots \ direita) = \ sum _ {k = n + 1} ^ {2n} {\ frac {1} {k}} = H_ {2n} -H_ {n}.}$

Finalmente, usando uma estimativa integral, como a soma de Euler-Maclaurin , ou a expansão assintótica do n- ésimo número harmônico , obtemos

${\ displaystyle H_ {2n} -H_ {n} \ sim \ log 2 - {\ frac {1} {4n}} + {\ frac {1} {16n ^ {2}}} - {\ frac {1} {128n ^ {4}}} + {\ frac {1} {256n ^ {6}}} - {\ frac {17} {4096n ^ {8}}} + \ cdots,}$

de modo a

${\ displaystyle [z ^ {2n}] [u] g (z, u) <\ log 2 \ quad {\ mbox {e}} \ quad 1- [z ^ {2n}] [u] g (z, u)> 1- \ log 2 = 0,30685281,}$

ou pelo menos 30%, conforme reivindicado.

Um resultado relacionado é que assintoticamente, o comprimento esperado do ciclo mais longo é λn, onde λ é a constante de Golomb-Dickman , aproximadamente 0,62.

Este exemplo é devido a Anna Gál e Peter Bro Miltersen; consulte o artigo de Peter Winkler para obter mais informações e veja a discussão em Les-Mathematiques.net . Consulte as referências sobre 100 prisioneiros para obter links para essas referências.

O cálculo acima pode ser executado de uma forma mais simples e direta, como segue: primeiro observe que uma permutação de elementos contém no máximo um ciclo de comprimento estritamente maior que . Assim, se denotarmos ${\ displaystyle 2n}$${\ displaystyle n}$

${\ displaystyle p_ {k} = \ Pr [{\ mbox {há um ciclo de comprimento}} k],}$

então

${\ displaystyle \ Pr [{\ mbox {há um ciclo de comprimento}}> n] = \ sum _ {k = n + 1} ^ {2n} p_ {k}.}$

Pois , o número de permutações que contêm um ciclo de comprimento exatamente é ${\ displaystyle k> n}$${\ displaystyle k}$

${\ displaystyle {{2n} \ escolha k} \ cdot {\ frac {k!} {k}} \ cdot (2n-k) !.}$

Explicação: é a quantidade de maneiras de escolher os elementos que compõem o ciclo; é o número de maneiras de organizar os itens em um ciclo; e é o número de maneiras de permutar os elementos restantes. Não existe dupla contagem aqui porque não há no máximo um ciclo de comprimento quando . Desse modo, ${\ displaystyle {{2n} \ escolha k}}$${\ displaystyle k}$${\ displaystyle {\ frac {k!} {k}}}$${\ displaystyle k}$${\ displaystyle (2n-k)!}$${\ displaystyle k}$${\ displaystyle k> n}$

${\ displaystyle p_ {k} = {\ frac {{{2n} \ escolha k} \ cdot {\ frac {k!} {k}} \ cdot (2n-k)!} {(2n)!}} = {\ frac {1} {k}}.}$

Concluimos que

${\ displaystyle \ Pr [{\ mbox {há um ciclo de comprimento}}> n] = \ sum _ {k = n + 1} ^ {2n} {\ frac {1} {k}} = H_ {2n } -H_ {n}.}$

Uma variação do problema dos 100 prisioneiros (chaves e caixas)

Existe um problema intimamente relacionado que se ajusta perfeitamente ao método apresentado aqui. Digamos que você tenha n caixas encomendadas. Cada caixa contém uma chave para alguma outra caixa ou possivelmente ela mesma dando uma permutação das chaves. Você tem permissão para selecionar k dessas n caixas todas de uma vez e abri-las simultaneamente, obtendo acesso às teclas k . Qual é a probabilidade de que usando essas chaves você possa abrir todas as n caixas, onde você usa uma chave encontrada para abrir a caixa a que pertence e repetir.

O enunciado matemático desse problema é o seguinte: escolha uma permutação aleatória em n elementos e k valores na faixa de 1 a n , também aleatoriamente, chame essas marcas. Qual é a probabilidade de haver pelo menos uma marca em cada ciclo da permutação? A alegação é que essa probabilidade é k / n .

As espécies de permutações por ciclos com algum subconjunto não vazio de cada ciclo sendo marcado tem a especificação ${\ displaystyle {\ mathcal {Q}}}$

${\ displaystyle {\ mathcal {Q}} = \ operatorname {SET} \ left (\ sum _ {q \ geq 1} \ operatorname {CYC} _ {= q} ({\ mathcal {Z}}) \ times \ soma _ {p = 1} ^ {q} {q \ escolha p} {\ mathcal {U}} ^ {p} \ right).}$

O índice na soma interna começa em um porque devemos ter pelo menos uma marca em cada ciclo.

Traduzindo a especificação para funções geradoras, obtemos a função geradora bivariada

${\ displaystyle G (z, u) = \ exp \ left (\ sum _ {q \ geq 1} {\ frac {z ^ {q}} {q}} \ sum _ {p = 1} ^ {q} {q \ escolha p} u ^ {p} \ right).}$

Isso simplifica para

${\ displaystyle \ exp \ left (\ sum _ {q \ geq 1} {\ frac {z ^ {q}} {q}} (u + 1) ^ {q} - \ sum _ {q \ geq 1} {\ frac {z ^ {q}} {q}} \ right)}$

ou

${\ displaystyle \ exp \ left (\ log {\ frac {1} {1- (u + 1) z}} - \ log {\ frac {1} {1-z}} \ right) = {\ frac { 1-z} {1- (u + 1) z}}.}$

A fim de extrair coeficientes desta reescrita assim

${\ displaystyle (1-z) \ sum _ {q \ geq 0} (u + 1) ^ {q} z ^ {q}.}$

Segue-se agora que

${\ displaystyle [z ^ {n}] G (z, u) = (u + 1) ^ {n} - (u + 1) ^ {n-1}}$

e, portanto

${\ displaystyle [u ^ {k}] [z ^ {n}] G (z, u) = {n \ escolha k} - {n-1 \ escolha k}.}$

Divida por para obter ${\ displaystyle {n \ escolha k}}$

${\ displaystyle 1 - {\ frac {(n-1)!} {k! (n-1-k)!}} {\ frac {k! (nk)!} {n!}} = 1 - {\ frac {nk} {n}} = {\ frac {k} {n}}.}$

Não precisamos dividir por n! porque é exponencial em z . ${\ displaystyle G (z, u)}$

Número de permutações contendo m ciclos

Aplicando o teorema fundamental de Flajolet-Sedgewick , ou seja, o teorema de enumeração rotulado com , ao conjunto ${\ displaystyle G = S_ {m}}$

${\ displaystyle \ operatorname {SET} _ {= m} (\ operatorname {CYC} ({\ mathcal {Z}}))}$

nós obtemos a função geradora

${\ displaystyle g_ {m} (z) = {\ frac {1} {| S_ {m} |}} \ left (\ log {\ frac {1} {1-z}} \ right) ^ {m} = {\ frac {1} {m!}} \ left (\ log {\ frac {1} {1-z}} \ right) ^ {m}.}$

O termo

${\ displaystyle (-1) ^ {n + m} n! \; [z ^ {n}] g_ {m} (z) = s (n, m)}$

produz os números de Stirling assinados do primeiro tipo e é o EGF dos números de Stirling não assinados do primeiro tipo, ou seja, ${\ displaystyle g_ {m} (z)}$

${\ displaystyle n! [z ^ {n}] g_ {m} (z) = \ left [{\ begin {matrix} n \\ m \ end {matrix}} \ right].}$

Podemos calcular o OGF dos números de Stirling assinados para n fixos, ou seja,

${\ displaystyle s_ {n} (w) = \ sum _ {m = 0} ^ {n} s (n, m) w ^ {m}.}$

Começar com

${\ displaystyle g_ {m} (z) = \ sum _ {n \ geq m} {\ frac {(-1) ^ {n + m}} {n!}} s (n, m) z ^ {n }}$

que produz

${\ displaystyle (-1) ^ {m} g_ {m} (z) w ^ {m} = \ sum _ {n \ geq m} {\ frac {(-1) ^ {n}} {n!} } s (n, m) w ^ {m} z ^ {n}.}$

Somando isso, obtemos

${\ displaystyle \ sum _ {m \ geq 0} (- 1) ^ {m} g_ {m} (z) w ^ {m} = \ sum _ {m \ geq 0} \ sum _ {n \ geq m } {\ frac {(-1) ^ {n}} {n!}} s (n, m) w ^ {m} z ^ {n} = \ sum _ {n \ geq 0} {\ frac {( -1) ^ {n}} {n!}} Z ^ {n} \ sum _ {m = 0} ^ {n} s (n, m) w ^ {m}.}$

Usando a fórmula envolvendo o logaritmo para à esquerda, a definição de à direita e o teorema binomial , obtemos ${\ displaystyle g_ {m} (z)}$${\ displaystyle s_ {n} (w)}$

${\ displaystyle (1-z) ^ {w} = \ sum _ {n \ geq 0} {w \ escolher n} (- 1) ^ {n} z ^ {n} = \ sum _ {n \ geq 0 } {\ frac {(-1) ^ {n}} {n!}} s_ {n} (w) z ^ {n}.}$

Comparando os coeficientes de , e usando a definição do coeficiente binomial , finalmente temos ${\ displaystyle z ^ {n}}$

${\ displaystyle s_ {n} (w) = w \; (w-1) \; (w-2) \; \ cdots \; (w- (n-1)) = (w) _ {n}, }$

um fatorial decrescente . O cálculo do OGF dos números de Stirling não assinados do primeiro tipo funciona de maneira semelhante.

Número esperado de ciclos de um determinado tamanho m

Neste problema, usamos uma função geradora bivariada g ( z ,  u ) conforme descrito na introdução. O valor de b para um ciclo de tamanho m é zero e um para um ciclo de tamanho m . Nós temos

${\ displaystyle {\ frac {\ partial} {\ partial u}} g (z, u) {\ Bigg |} _ {u = 1} = {\ frac {1} {1-z}} \ sum _ { k \ geq 1} b (k) {\ frac {z ^ {k}} {k}} = {\ frac {1} {1-z}} {\ frac {z ^ {m}} {m}} }$

ou

${\ displaystyle {\ frac {1} {m}} z ^ {m} \; + \; {\ frac {1} {m}} z ^ {m + 1} \; + \; {\ frac {1 } {m}} z ^ {m + 2} \; + \; \ cdots}$

Isso significa que o número esperado de ciclos de tamanho m em uma permutação de comprimento n menor que m é zero (obviamente). Uma permutação aleatória de comprimento de pelo menos m contém em média 1 / m ciclos de comprimento m . Em particular, uma permutação aleatória contém cerca de um ponto fixo.

O OGF do número esperado de ciclos de comprimento menor ou igual a m é, portanto,

${\ displaystyle {\ frac {1} {1-z}} \ sum _ {k = 1} ^ {m} {\ frac {z ^ {k}} {k}} {\ mbox {and}} [z ^ {n}] {\ frac {1} {1-z}} \ sum _ {k = 1} ^ {m} {\ frac {z ^ {k}} {k}} = H_ {m} {\ mbox {para}} n \ geq m}$

onde H _m é o m- ésimo número harmônico . Conseqüentemente, o número esperado de ciclos de comprimento no máximo m em uma permutação aleatória é cerca de ln  m .

Momentos de pontos fixos

O GF misto do conjunto de permutações pelo número de pontos fixos é ${\ displaystyle g (z, u)}$

${\ displaystyle g (z, u) = \ exp \ left (-z + uz + \ log {\ frac {1} {1-z}} \ right) = {\ frac {1} {1-z}} \ exp (-z + uz).}$

Seja a variável aleatória X o número de pontos fixos de uma permutação aleatória. Usando números de Stirling de segundo tipo , temos a seguinte fórmula para o m- ésimo momento de X :

${\ displaystyle E (X ^ {m}) = E \ left (\ sum _ {k = 0} ^ {m} \ left \ {{\ begin {matrix} m \\ k \ end {matrix}} \ right \} (X) _ {k} \ right) = \ sum _ {k = 0} ^ {m} \ left \ {{\ begin {matrix} m \\ k \ end {matrix}} \ right \} E ((X) _ {k}),}$

onde está um fatorial decrescente . Usando , temos ${\ displaystyle (X) _ {k}}$${\ displaystyle g (z, u)}$

${\ displaystyle E ((X) _ {k}) = [z ^ {n}] \ left ({\ frac {d} {du}} \ right) ^ {k} g (z, u) {\ Bigg |} _ {u = 1} = [z ^ {n}] {\ frac {z ^ {k}} {1-z}} \ exp (-z + uz) {\ Bigg |} _ {u = 1 } = [z ^ {n}] {\ frac {z ^ {k}} {1-z}},}$

que é zero quando , e um caso contrário. Portanto, apenas os termos com contribuem para a soma. Isso produz ${\ displaystyle k> n}$${\ displaystyle k <= n}$

${\ displaystyle E (X ^ {m}) = \ sum _ {k = 0} ^ {n} \ left \ {{\ begin {matrix} m \\ k \ end {matrix}} \ right \}.}$

Número esperado de pontos fixos em permutação aleatória elevado a alguma potência k

Suponha que você escolha uma permutação aleatória e a eleve a alguma potência , com um inteiro positivo, e pergunte sobre o número esperado de pontos fixos no resultado. Denote esse valor por . ${\ displaystyle \ sigma}$${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle E [F_ {k}]}$

Para cada divisor de um ciclo de comprimento se divide em pontos fixos quando elevado à potência. Portanto, precisamos marcar esses ciclos com. Para ilustrar isso, considere${\ displaystyle d}$${\ displaystyle k}$${\ displaystyle d}$${\ displaystyle d}$${\ displaystyle k.}$${\ displaystyle u ^ {d}.}$${\ displaystyle E [F_ {6}].}$

Nós temos

${\ displaystyle g (z, u) = \ exp \ left (uz-z + u ^ {2} {\ frac {z ^ {2}} {2}} - {\ frac {z ^ {2}} { 2}} + u ^ {3} {\ frac {z ^ {3}} {3}} - {\ frac {z ^ {3}} {3}} + u ^ {6} {\ frac {z ^ {6}} {6}} - {\ frac {z ^ {6}} {6}} + \ log {\ frac {1} {1-z}} \ right)}$

qual é

${\ displaystyle {\ frac {1} {1-z}} \ exp \ left (uz-z + u ^ {2} {\ frac {z ^ {2}} {2}} - {\ frac {z ^ {2}} {2}} + u ^ {3} {\ frac {z ^ {3}} {3}} - {\ frac {z ^ {3}} {3}} + u ^ {6} { \ frac {z ^ {6}} {6}} - {\ frac {z ^ {6}} {6}} \ right).}$

Mais uma vez continuando conforme descrito na introdução, encontramos

${\ displaystyle \ left. {\ frac {\ partial} {\ partial u}} g (z, u) \ right | _ {u = 1} = \ left. {\ frac {z + z ^ {2} + z ^ {3} + z ^ {6}} {1-z}} \ exp \ left (uz-z + u ^ {2} {\ frac {z ^ {2}} {2}} - {\ frac {z ^ {2}} {2}} + u ^ {3} {\ frac {z ^ {3}} {3}} - {\ frac {z ^ {3}} {3}} + u ^ { 6} {\ frac {z ^ {6}} {6}} - {\ frac {z ^ {6}} {6}} \ right) \ right | _ {u = 1}}$

qual é

${\ displaystyle {\ frac {z + z ^ {2} + z ^ {3} + z ^ {6}} {1-z}}.}$

A conclusão é que para e há quatro pontos fixos em média. ${\ displaystyle E [F_ {6}] = 4}$${\ displaystyle n \ geq 6}$

O procedimento geral é

${\ displaystyle g (z, u) = \ exp \ left (\ sum _ {d \ mid k} \ left (u ^ {d} {\ frac {z ^ {d}} {d}} - {\ frac {z ^ {d}} {d}} \ right) + \ log {\ frac {1} {1-z}} \ right) = {\ frac {1} {1-z}} \ exp \ left ( \ sum _ {d \ mid k} \ left (u ^ {d} {\ frac {z ^ {d}} {d}} - {\ frac {z ^ {d}} {d}} \ right) \ certo).}$

Mais uma vez continuando como antes, encontramos

${\ displaystyle \ left. {\ frac {\ partial} {\ partial u}} g (z, u) \ right | _ {u = 1} = \ left. {\ frac {\ sum _ {d \ mid k } z ^ {d}} {1-z}} \ exp \ left (\ sum _ {d \ mid k} \ left (u ^ {d} {\ frac {z ^ {d}} {d}} - {\ frac {z ^ {d}} {d}} \ right) \ right) \ right | _ {u = 1} = {\ frac {\ sum _ {d \ mid k} z ^ {d}} { 1-z}}.}$

Mostramos que o valor de é igual a (o número de divisores de ) assim que começa em for e aumenta em um cada vez que atinge um divisor de até e incluindo a si mesmo. ${\ displaystyle E [F_ {k}]}$${\ displaystyle \ tau (k)}$${\ displaystyle k}$${\ displaystyle n \ geq k.}$${\ displaystyle 1}$${\ displaystyle n = 1}$${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle k}$

Número esperado de ciclos de qualquer comprimento de uma permutação aleatória

Construímos a função geradora bivariada usando , onde é um para todos os ciclos (cada ciclo contribui com um para o número total de ciclos). ${\ displaystyle g (z, u)}$${\ displaystyle b (k)}$${\ displaystyle b (k)}$

Observe que tem o formulário fechado ${\ displaystyle g (z, u)}$

${\ displaystyle g (z, u) = \ left ({\ frac {1} {1-z}} \ right) ^ {u}}$

e gera os números de Stirling não assinados do primeiro tipo .

Nós temos

${\ displaystyle {\ frac {\ partial} {\ partial u}} g (z, u) {\ Bigg |} _ {u = 1} = {\ frac {1} {1-z}} \ sum _ { k \ geq 1} b (k) {\ frac {z ^ {k}} {k}} = {\ frac {1} {1-z}} \ sum _ {k \ geq 1} {\ frac {z ^ {k}} {k}} = {\ frac {1} {1-z}} \ log {\ frac {1} {1-z}}.}$

Conseqüentemente, o número esperado de ciclos é o número harmônico , ou cerca de . ${\ displaystyle H_ {n}}$${\ displaystyle \ log n}$

Número de permutações com um ciclo de comprimento maior que n / 2

(Observe que a Seção Cem prisioneiros contém exatamente o mesmo problema com um cálculo muito semelhante, além de uma prova elementar mais simples.)

Mais uma vez, comece com a função geradora exponencial , desta vez da classe de permutações de acordo com o tamanho onde os ciclos de comprimento mais do que são marcados com a variável : ${\ displaystyle g (z, u)}$${\ displaystyle {\ mathcal {P}}}$${\ displaystyle n / 2}$${\ displaystyle u}$

${\ displaystyle g (z, u) = \ exp \ left (u \ sum _ {k> \ lfloor {\ frac {n} {2}} \ rfloor} ^ {\ infty} {\ frac {z ^ {k }} {k}} + \ sum _ {k = 1} ^ {\ lfloor {\ frac {n} {2}} \ rfloor} {\ frac {z ^ {k}} {k}} \ right). }$

Só pode haver um ciclo de comprimento a mais , portanto, a resposta à pergunta é dada por ${\ displaystyle {\ frac {n} {2}}}$

${\ displaystyle n! [uz ^ {n}] g (z, u) = n! [z ^ {n}] \ exp \ left (\ sum _ {k = 1} ^ {\ lfloor {\ frac {n } {2}} \ rfloor} {\ frac {z ^ {k}} {k}} \ right) \ sum _ {k> \ lfloor {\ frac {n} {2}} \ rfloor} ^ {\ infty } {\ frac {z ^ {k}} {k}}}$

ou

${\ displaystyle n! [z ^ {n}] \ exp \ left (\ log {\ frac {1} {1-z}} - \ sum _ {k> \ lfloor {\ frac {n} {2}} \ rfloor} ^ {\ infty} {\ frac {z ^ {k}} {k}} \ right) \ sum _ {k> \ lfloor {\ frac {n} {2}} \ rfloor} ^ {\ infty } {\ frac {z ^ {k}} {k}}}$

qual é

${\ displaystyle n! [z ^ {n}] {\ frac {1} {1-z}} \ exp \ left (- \ sum _ {k> \ lfloor {\ frac {n} {2}} \ rfloor } ^ {\ infty} {\ frac {z ^ {k}} {k}} \ right) \ sum _ {k> \ lfloor {\ frac {n} {2}} \ rfloor} ^ {\ infty} { \ frac {z ^ {k}} {k}} = n! [z ^ {n}] {\ frac {1} {1-z}} \ sum _ {m = 0} ^ {\ infty} {\ frac {(-1) ^ {m}} {m!}} \ left (\ sum _ {k> \ lfloor {\ frac {n} {2}} \ rfloor} ^ {\ infty} {\ frac {z ^ {k}} {k}} \ right) ^ {m + 1}}$

O expoente de no termo sendo elevado à potência é maior do que e, portanto, nenhum valor para pode possivelmente contribuir para${\ displaystyle z}$${\ displaystyle m + 1}$${\ displaystyle \ lfloor {\ frac {n} {2}} \ rfloor}$${\ displaystyle m> 0}$${\ displaystyle [z ^ {n}].}$

Conclui-se que a resposta é

${\ displaystyle n! [z ^ {n}] {\ frac {1} {1-z}} \ sum _ {k> \ lfloor {\ frac {n} {2}} \ rfloor} ^ {\ infty} {\ frac {z ^ {k}} {k}} = n! \ sum _ {k = \ lfloor {\ frac {n} {2}} \ rfloor +1} ^ {n} {\ frac {1} {k}}.}$

A soma tem uma representação alternativa que se encontra, por exemplo, no OEIS OEIS :  A024167 .

${\ displaystyle \ sum _ {k = 1} ^ {n} {\ frac {1} {k}} - \ sum _ {k = 1} ^ {\ lfloor {\ frac {n} {2}} \ rfloor } {\ frac {1} {k}} = \ sum _ {k = 1} ^ {n} {\ frac {1} {k}} - 2 \ sum _ {k = 1} ^ {\ lfloor {\ frac {n} {2}} \ rfloor} {\ frac {1} {2k}} = \ sum _ {k = 1 \ sobre k \; {\ text {even}}} ^ {n} (1-2 ) {\ frac {1} {k}} + \ sum _ {k = 1 \ no topo de k \; {\ text {ímpar}}} ^ {n} {\ frac {1} {k}}}$

finalmente dando

${\ displaystyle n! \ sum _ {k = 1} ^ {n} {\ frac {(-1) ^ {k + 1}} {k}} \ sim n! \ log 2.}$

Número esperado de transposições de uma permutação aleatória

Podemos usar a decomposição de ciclo disjunto de uma permutação para fatorá-la como um produto de transposições, substituindo um ciclo de comprimento k por k  - 1 transposições. Por exemplo, os fatores de ciclo como . A função para ciclos é igual a e obtemos ${\ displaystyle (1 \; 2 \; 34)}$${\ displaystyle (1 \; 2) \; (2 \; 3) \; (3 \; 4)}$${\ displaystyle b (k)}$${\ displaystyle k-1}$

${\ displaystyle g (z, u) = \ left ({\ frac {1} {1-uz}} \ right) ^ {1 / u}}$

e

${\ displaystyle {\ frac {\ partial} {\ partial u}} g (z, u) {\ Bigg |} _ {u = 1} = {\ frac {1} {1-z}} \ sum _ { k \ geq 1} (k-1) {\ frac {z ^ {k}} {k}} = {\ frac {z} {(1-z) ^ {2}}} - {\ frac {1} {1-z}} \ log {\ frac {1} {1-z}}.}$

Portanto, o número esperado de transposições é ${\ displaystyle T (n)}$

${\ displaystyle T (n) = n-H_ {n}}$

onde está o número Harmônico . Também poderíamos ter obtido essa fórmula observando que o número de transposições é obtido somando os comprimentos de todos os ciclos (o que dá n ) e subtraindo um para cada ciclo (o que dá pela seção anterior). ${\ displaystyle H_ {n}}$${\ displaystyle n ^ {th}}$ ${\ displaystyle \ log n}$

Observe que novamente gera os números de Stirling sem sinal do primeiro tipo , mas na ordem inversa. Mais precisamente, temos ${\ displaystyle g (z, u)}$

${\ displaystyle (-1) ^ {m} n! \; [z ^ {n}] [u ^ {m}] g (z, u) = \ left [{\ begin {matrix} n \\ nm \ fim {matriz}} \ direita]}$

Para ver isso, observe que o acima é equivalente a

${\ displaystyle (-1) ^ {n + m} n! \; [z ^ {n}] [u ^ {m}] g (z, u) | _ {u = 1 / u} | _ {z = uz} = \ left [{\ begin {matrix} n \\ m \ end {matrix}} \ right]}$

e essa

${\ displaystyle [u ^ {m}] g (z, u) | _ {u = 1 / u} | _ {z = uz} = [u ^ {m}] \ left ({\ frac {1} { 1-z}} \ right) ^ {u} = {\ frac {1} {m!}} \ Left (\ log {\ frac {1} {1-z}} \ right) ^ {m},}$

que vimos ser o EGF dos números de Stirling sem sinal do primeiro tipo na seção sobre permutações consistindo em precisamente m ciclos.

Tamanho de ciclo esperado de um elemento aleatório

Selecionamos um elemento aleatório q de uma permutação aleatória e perguntamos sobre o tamanho esperado do ciclo que contém q . Aqui, a função é igual a , porque um ciclo de comprimento k contribui com k elementos que estão em ciclos de comprimento k . Observe que, ao contrário dos cálculos anteriores, precisamos calcular a média desse parâmetro depois de extraí-lo da função geradora (dividir por n ). Nós temos ${\ displaystyle \ sigma}$${\ displaystyle b (k)}$${\ displaystyle k ^ {2}}$

${\ displaystyle {\ frac {\ partial} {\ partial u}} g (z, u) {\ Bigg |} _ {u = 1} = {\ frac {1} {1-z}} \ sum _ { k \ geq 1} k ^ {2} {\ frac {z ^ {k}} {k}} = {\ frac {1} {1-z}} {\ frac {z} {(1-z) ^ {2}}} = {\ frac {z} {(1-z) ^ {3}}}.}$

Portanto, a duração esperada do ciclo que contém q é

${\ displaystyle {\ frac {1} {n}} [z ^ {n}] {\ frac {z} {(1-z) ^ {3}}} = {\ frac {1} {n}} { \ frac {1} {2}} n (n + 1) = {\ frac {1} {2}} (n + 1).}$

Probabilidade de que um elemento aleatório se encontre em um ciclo de tamanho m

Este parâmetro médio representa a probabilidade de que se selecionarmos novamente um elemento aleatório de de uma permutação aleatória, o elemento encontra-se em um ciclo de tamanho m . A função é igual a para e zero caso contrário, porque apenas os ciclos de comprimento m contribuem, ou seja, m elementos que estão em um ciclo de comprimento m . Nós temos ${\ displaystyle [n]}$${\ displaystyle b (k)}$${\ displaystyle m}$${\ displaystyle m = k}$

${\ displaystyle {\ frac {\ partial} {\ partial u}} g (z, u) {\ Bigg |} _ {u = 1} = {\ frac {1} {1-z}} \ sum _ { k \ geq 1} b (k) {\ frac {z ^ {k}} {k}} = {\ frac {1} {1-z}} \; m \; {\ frac {z ^ {m} } {m}} = {\ frac {z ^ {m}} {1-z}}.}$

Segue-se que a probabilidade de que um elemento aleatório se encontre em um ciclo de comprimento m é

${\ displaystyle {\ frac {1} {n}} [z ^ {n}] {\ frac {z ^ {m}} {1-z}} = {\ begin {cases} {\ frac {1} { n}}, & {\ mbox {if}} n \ geq m \\ 0, & {\ mbox {caso contrário.}} \ end {cases}}}$

Probabilidade de que um subconjunto aleatório de [ n ] esteja no mesmo ciclo

Selecione um subconjunto aleatório Q de [ n ] contendo m elementos e uma permutação aleatória e pergunte sobre a probabilidade de que todos os elementos de Q estejam no mesmo ciclo. Este é outro parâmetro médio. A função b ( k ) é igual a , porque um ciclo de comprimento k contribui com subconjuntos de tamanho m , onde para k < m . Isso produz ${\ displaystyle {\ begin {matriz} {k \ choose m} \ end {matrix}}}$${\ displaystyle {\ begin {matriz} {k \ choose m} \ end {matrix}}}$${\ displaystyle {\ begin {matriz} {k \ choose m} = 0 \ end {matriz}}}$

${\ displaystyle {\ frac {\ partial} {\ partial u}} g (z, u) {\ Bigg |} _ {u = 1} = {\ frac {1} {1-z}} \ sum _ { k \ geq m} {k \ escolher m} {\ frac {z ^ {k}} {k}} = {\ frac {1} {1-z}} {\ frac {1} {m}} {\ frac {z ^ {m}} {(1-z) ^ {m}}} = {\ frac {1} {m}} {\ frac {z ^ {m}} {(1-z) ^ {m +1}}}.}$

Calculando a média, obtemos que a probabilidade dos elementos de Q estarem no mesmo ciclo é

${\ displaystyle {n \ escolha m} ^ {- 1} [z ^ {n}] {\ frac {1} {m}} {\ frac {z ^ {m}} {(1-z) ^ {m +1}}} = {n \ escolha m} ^ {- 1} {\ frac {1} {m}} [z ^ {nm}] {\ frac {1} {(1-z) ^ {m + 1}}}}$

ou

${\ displaystyle {\ frac {1} {m}} {n \ escolha m} ^ {- 1} {(nm) \; + \; m \ escolha m} = {\ frac {1} {m}}. }$

Em particular, a probabilidade de que dois elementos p < q estejam no mesmo ciclo é 1/2.

Número de permutações contendo um número par de ciclos pares

Podemos usar o teorema fundamental de Flajolet-Sedgewick diretamente e calcular estatísticas de permutação mais avançadas. (Verifique nessa página uma explicação de como os operadores que usaremos são calculados.) Por exemplo, o conjunto de permutações contendo um número par de ciclos pares é dado por

${\ displaystyle \ operatorname {SET} (\ operatorname {CYC} _ {\ operatorname {ímpar}} ({\ mathcal {Z}})) \ operatorname {SET} _ {\ operatorname {even}} (\ operatorname {CYC } _ {\ operatorname {even}} ({\ mathcal {Z}})).}$

Traduzindo para funções geradoras exponenciais (EGFs), obtemos

${\ displaystyle \ exp \ left ({\ frac {1} {2}} \ log {\ frac {1 + z} {1-z}} \ right) \ cosh \ left ({\ frac {1} {2 }} \ log {\ frac {1} {1-z ^ {2}}} \ right)}$

ou

${\ displaystyle {\ frac {1} {2}} \ exp \ left ({\ frac {1} {2}} \ left (\ log {\ frac {1 + z} {1-z}} + \ log {\ frac {1} {1-z ^ {2}}} \ right) \ right) + {\ frac {1} {2}} \ exp \ left ({\ frac {1} {2}} \ left (\ log {\ frac {1 + z} {1-z}} - \ log {\ frac {1} {1-z ^ {2}}} \ direita) \ direita).}$

Isso simplifica para

${\ displaystyle {\ frac {1} {2}} \ exp \ left ({\ frac {1} {2}} \ log {\ frac {1} {(1-z) ^ {2}}} \ right ) + {\ frac {1} {2}} \ exp \ left ({\ frac {1} {2}} \ log (1 + z) ^ {2} \ right)}$

ou

${\ displaystyle {\ frac {1} {2}} {\ frac {1} {1-z}} + {\ frac {1} {2}} (1 + z) = 1 + z + {\ frac {1 } {2}} {\ frac {z ^ {2}} {1-z}}.}$

Isso diz que há uma permutação de tamanho zero contendo um número par de ciclos pares (a permutação vazia, que contém zero ciclos de comprimento par), uma tal permutação de tamanho um (o ponto fixo, que também contém zero ciclos de comprimento par ), e para isso , existem tais permutações. ${\ displaystyle n \ geq 2}$${\ displaystyle n! / 2}$

Permutações que são quadrados

Considere o que acontece quando elevamos ao quadrado uma permutação. Os pontos fixos são mapeados para pontos fixos. Ciclos ímpares são mapeados para ciclos ímpares em uma correspondência um a um, por exemplo, se transforma em . Mesmo os ciclos se dividem em dois e produzem um par de ciclos com metade do tamanho do ciclo original, por exemplo, se transforma em . Portanto, as permutações que são quadrados podem conter qualquer número de ciclos ímpares e um número par de ciclos de tamanho dois, um número par de ciclos de tamanho quatro etc., e são dadas por ${\ displaystyle (1 \; 8 \; 9 \; 11 \; 13)}$${\ displaystyle (1 \; 9 \; 13 \; 8 \; 11)}$${\ displaystyle (5 \; 13 \; 6 \; 9)}$${\ displaystyle (5 \; 6) \; (9 \; 13)}$

${\ displaystyle \ operatorname {SET} (\ operatorname {CYC} _ {\ operatorname {ímpar}} ({\ mathcal {Z}})) \ operatorname {SET} _ {\ operatorname {even}} (\ operatorname {CYC } _ {= 2} ({\ mathcal {Z}})) \ operatorname {SET} _ {\ operatorname {even}} (\ operatorname {CYC} _ {= 4} ({\ mathcal {Z}})) \ operatorname {SET} _ {\ operatorname {even}} (\ operatorname {CYC} _ {= 6} ({\ mathcal {Z}})) \ cdots}$

que produz o EGF

${\ displaystyle \ exp \ left ({\ frac {1} {2}} \ log {\ frac {1 + z} {1-z}} \ right) \ prod _ {m \ geq 1} \ cosh {\ frac {z ^ {2m}} {2m}} = {\ sqrt {\ frac {1 + z} {1-z}}} \ prod _ {m \ geq 1} \ cosh {\ frac {z ^ {2m }} {2m}}.}$

Invariantes de ciclo ímpar

Os tipos de permutações apresentadas nas duas seções anteriores, ou seja, permutações contendo um número par de ciclos pares e permutações que são quadrados, são exemplos dos chamados invariantes de ciclo ímpar , estudados por Sung e Zhang (ver links externos ). O termo invariante de ciclo ímpar significa simplesmente que a pertença à respectiva classe combinatória é independente do tamanho e do número de ciclos ímpares que ocorrem na permutação. Na verdade, podemos provar que todos os invariantes de ciclo ímpar obedecem a uma recorrência simples, que derivaremos. Primeiro, aqui estão mais alguns exemplos de invariantes de ciclo ímpar.

Permutações onde a soma dos comprimentos dos ciclos pares é de seis

Esta classe tem a especificação

${\ displaystyle \ operatorname {SET} (\ operatorname {CYC} _ {\ operatorname {odd}} ({\ mathcal {Z}})) \ left (\ operatorname {SET} _ {= 3} (\ operatorname {CYC } _ {= 2} ({\ mathcal {Z}})) + \ operatorname {CYC} _ {= 2} ({\ mathcal {Z}}) \ operatorname {CYC} _ {= 4} ({\ mathcal {Z}}) + \ operatorname {CYC} _ {= 6} ({\ mathcal {Z}}) \ right)}$

e a função geradora

${\ displaystyle {\ sqrt {\ frac {1 + z} {1-z}}} \ left ({\ frac {1} {6}} \ left ({\ frac {z ^ {2}} {2} } \ right) ^ {3} + {\ frac {z ^ {2}} {2}} {\ frac {z ^ {4}} {4}} + {\ frac {z ^ {6}} {6 }} \ direita) = {\ frac {5} {16}} z ^ {6} {\ sqrt {\ frac {1 + z} {1-z}}}.}$

Os primeiros valores são

${\ displaystyle 0,0,0,0,0,225,1575,6300,56700,425250,4677750,46777500,608107500, \ ldots}$

Permutações onde todos os ciclos pares têm a mesma duração

Esta classe tem a especificação

${\ displaystyle \ operatorname {SET} (\ operatorname {CYC} _ {\ operatorname {odd}} ({\ mathcal {Z}})) \ left (\ operatorname {SET} _ {\ geq 1} (\ operatorname { CYC} _ {= 2} ({\ mathcal {Z}})) + \ operatorname {SET} _ {\ geq 1} (\ operatorname {CYC} _ {= 4} ({\ mathcal {Z}})) + \ operatorname {SET} _ {\ geq 1} (\ operatorname {CYC} _ {= 6} ({\ mathcal {Z}})) + \ cdots \ right)}$

e a função geradora

${\ displaystyle {\ sqrt {\ frac {1 + z} {1-z}}} \ left (\ exp \ left ({\ frac {z ^ {2}} {2}} \ right) -1 \, + \, \ exp \ left ({\ frac {z ^ {4}} {4}} \ right) -1 \, + \, \ exp \ left ({\ frac {z ^ {6}} {6} } \ right) -1 \, + \, \ cdots \ right).}$

Há uma nuance semântica aqui. Poderíamos considerar permutações que não contêm ciclos pares como pertencentes a essa classe, uma vez que zero é par . Os primeiros valores são

${\ displaystyle 0,1,3,15,75,405,2835,22155,199395,1828575, \ ldots}$

Permutações onde o comprimento máximo de um ciclo par é quatro

Esta classe tem a especificação

${\ displaystyle \ operatorname {SET} (\ operatorname {CYC} _ {\ operatorname {odd}} ({\ mathcal {Z}})) \ operatorname {SET} (\ operatorname {CYC} _ {= 2} ({ \ mathcal {Z}}) + \ operatorname {CYC} _ {= 4} ({\ mathcal {Z}}))}$

e a função geradora

${\ displaystyle {\ sqrt {\ frac {1 + z} {1-z}}} \ exp \ left ({\ frac {z ^ {2}} {2}} + {\ frac {z ^ {4} } {4}} \ right).}$

Os primeiros valores são

${\ displaystyle 1,2,6,24,120,600,4200,28560,257040,2207520,24282720,258128640, \ ldots}$

A recorrência

Observe cuidadosamente como as especificações do componente de ciclo uniforme são construídas. É melhor pensar neles em termos de árvores de análise. Essas árvores têm três níveis. Os nós no nível mais baixo representam somas de produtos de ciclos de comprimento par do singleton . Os nós no nível intermediário representam restrições do operador de conjunto. Finalmente, o nó no nível superior soma os produtos das contribuições do nível médio. Observe que as restrições do operador de conjunto, quando aplicadas a uma função geradora que seja par, preservarão esse recurso, ou seja, produzirão outra função geradora par. Mas todas as entradas para os operadores de conjunto são uniformes, uma vez que surgem de ciclos de comprimento uniforme. O resultado é que todas as funções geradoras envolvidas têm a forma ${\ displaystyle {\ mathcal {Z}}}$

${\ displaystyle g (z) = h (z) {\ sqrt {\ frac {1 + z} {1-z}}},}$

onde está uma função par. Isso significa que ${\ displaystyle h (z)}$

${\ displaystyle {\ frac {1} {1 + z}} \; g (z) = h (z) \; {\ frac {1} {\ sqrt {1-z ^ {2}}}}}$

é igual também e, portanto,

${\ displaystyle {\ frac {1} {1 + z}} \; g (z) = {\ frac {1} {1-z}} \; g (-z) \ quad {\ mbox {ou}} \ quad (1-z) \; g (z) = (1 + z) \; g (-z).}$

Deixando e extraindo coeficientes, descobrimos que ${\ displaystyle g_ {n} = [z ^ {n}] g (z)}$

${\ displaystyle {\ frac {g_ {2m + 1}} {(2m + 1)!}} - {\ frac {g_ {2m}} {(2m)!}} = - {\ frac {g_ {2m + 1}} {(2m + 1)!}} + {\ Frac {g_ {2m}} {(2m)!}} \ Quad {\ mbox {ou}} \ quad 2 {\ frac {g_ {2m + 1 }} {(2m + 1)!}} = 2 {\ frac {g_ {2m}} {(2m)!}}}$

que produz a recorrência

${\ displaystyle g_ {2m + 1} = (2m + 1) g_ {2m} \ ,.}$

Um problema da competição Putnam de 2005

Um link para o site da competição Putnam aparece na seção Links externos . O problema pede uma prova de que

${\ displaystyle \ sum _ {\ pi \ in S_ {n}} {\ frac {\ sigma (\ pi)} {\ nu (\ pi) +1}} = (- 1) ^ {n + 1} { \ frac {n} {n + 1}},}$

onde a soma é sobre todas as permutações de , é o sinal de , isto é , se é par e se é ímpar, e é o número de pontos fixos de . ${\ displaystyle n!}$${\ displaystyle [n]}$${\ displaystyle \ sigma (\ pi)}$${\ displaystyle \ pi}$${\ displaystyle \ sigma (\ pi) = 1}$${\ displaystyle \ pi}$${\ displaystyle \ sigma (\ pi) = - 1}$${\ displaystyle \ pi}$${\ displaystyle \ nu (\ pi)}$${\ displaystyle \ pi}$

Agora o sinal de é dado por ${\ displaystyle \ pi}$

${\ displaystyle \ sigma (\ pi) = \ prod _ {c \ in \ pi} (- 1) ^ {| c | -1},}$

onde o produto está em todos os ciclos c de , como explicado, por exemplo, na página em permutações pares e ímpares . ${\ displaystyle \ pi}$

Portanto, consideramos a classe combinatória

${\ displaystyle \ operatorname {SET} (- {\ mathcal {Z}} + {\ mathcal {V}} {\ mathcal {Z}} + \ operatorname {CYC} _ {= 1} ({\ mathcal {Z} }) + {\ mathcal {U}} \ operatorname {CYC} _ {= 2} ({\ mathcal {Z}}) + {\ mathcal {U}} ^ {2} \ operatorname {CYC} _ {= 3 } ({\ mathcal {Z}}) + {\ mathcal {U}} ^ {3} \ operatorname {CYC} _ {= 4} ({\ mathcal {Z}}) + \ cdots)}$

onde marca um menos a duração de um ciclo de contribuição e marca pontos fixos. Traduzindo para funções geradoras, obtemos ${\ displaystyle {\ mathcal {U}}}$${\ displaystyle {\ mathcal {V}}}$

${\ displaystyle g (z, u, v) = \ exp \ left (-z + vz + \ sum _ {k \ geq 1} u ^ {k-1} {\ frac {z ^ {k}} {k} }\certo)}$

ou

${\ displaystyle \ exp \ left (-z + vz + {\ frac {1} {u}} \ log {\ frac {1} {1-uz}} \ right) = \ exp (-z + vz) \ left ({\ frac {1} {1-uz}} \ right) ^ {1 / u}.}$

Agora temos

${\ displaystyle n! [z ^ {n}] g (z, -1, v) = n! [z ^ {n}] \ exp (-z + vz) (1 + z) = \ sum _ {\ pi \ in S_ {n}} \ sigma (\ pi) v ^ {\ nu (\ pi)}}$

e, portanto, a quantidade desejada é dada por

${\ displaystyle n! [z ^ {n}] \ int _ {0} ^ {1} g (z, -1, v) dv = \ sum _ {\ pi \ in S_ {n}} {\ frac { \ sigma (\ pi)} {\ nu (\ pi) +1}}.}$

Fazendo o cálculo, obtemos

${\ displaystyle \ int _ {0} ^ {1} g (z, -1, v) dv = \ exp (-z) (1 + z) \ left ({\ frac {1} {z}} \ exp (z) - {\ frac {1} {z}} \ right)}$

ou

${\ displaystyle \ left ({\ frac {1} {z}} + 1 \ right) \ left (1- \ exp (-z) \ right) = {\ frac {1} {z}} + 1- \ exp (-z) - {\ frac {1} {z}} \ exp (-z).}$

Extraindo os coeficientes, descobrimos que o coeficiente de é zero. A constante é um, o que não concorda com a fórmula (deveria ser zero). Para positivo, no entanto, obtemos ${\ displaystyle 1 / z}$${\ displaystyle n}$

${\ displaystyle n! [z ^ {n}] \ left (- \ exp (-z) - {\ frac {1} {z}} \ exp (-z) \ right) = n! \ left (- ( -1) ^ {n} {\ frac {1} {n!}} - (- 1) ^ {n + 1} {\ frac {1} {(n + 1)!}} \ Direita)}$

ou

${\ displaystyle (-1) ^ {n + 1} \ left (1 - {\ frac {1} {n + 1}} \ right) = (- 1) ^ {n + 1} {\ frac {n} {n + 1}},}$

qual é o resultado desejado.

Como um aparte interessante, observamos que pode ser usado para avaliar o seguinte determinante de uma matriz: ${\ displaystyle g (z, u, v)}$${\ displaystyle n \ times n}$

${\ displaystyle d (n) = \ det (A_ {n}) = {\ begin {vmatrix} a && b && b && \ cdots && b \\ b && a && b && \ cdots && b \\ b && b && a && \ cdots && b \\\ vdots && \ vdots && \ vdots && \ ddots && \ vdots \\ b && b && b && \ cdots && a \ end {vmatrix}}.}$

onde . Lembre-se da fórmula para o determinante: ${\ displaystyle a, b \ neq 0}$

${\ displaystyle \ det (A) = \ sum _ {\ pi \ in S_ {n}} \ sigma (\ pi) \ prod _ {i = 1} ^ {n} A_ {i, \ pi (i)} .}$

Agora, o valor do produto à direita para uma permutação é , onde f é o número de pontos fixos de . Por isso ${\ displaystyle \ pi}$${\ displaystyle a ^ {f} b ^ {nf}}$${\ displaystyle \ pi}$

${\ displaystyle d (n) = b ^ {n} n! [z ^ {n}] g \ left (z, -1, {\ frac {a} {b}} \ right) = b ^ {n} n! [z ^ {n}] \ exp \ left ({\ frac {ab} {b}} z \ right) (1 + z)}$

que produz

${\ displaystyle b ^ {n} \ left ({\ frac {ab} {b}} \ right) ^ {n} + b ^ {n} n \ left ({\ frac {ab} {b}} \ right ) ^ {n-1} = (ab) ^ {n} + nb (ab) ^ {n-1}}$

e finalmente

${\ displaystyle d (n) = (a + (n-1) b) (ab) ^ {n-1} \,}$

A diferença entre o número de ciclos em permutações pares e ímpares

Aqui procuramos mostrar que essa diferença é dada por

${\ displaystyle (-1) ^ {n} (n-2)!}$

Lembre-se de que o sinal de uma permutação é dado por ${\ displaystyle \ sigma (\ pi)}$${\ displaystyle \ pi}$

${\ displaystyle \ sigma (\ pi) = \ prod _ {c \ in \ pi} (- 1) ^ {| c | -1}}$

onde o produto varia ao longo dos ciclos c da composição do ciclo disjunto de . ${\ displaystyle \ pi}$

Segue-se que a espécie combinatória que reflete os sinais e a contagem do ciclo do conjunto de permutações é dada por ${\ displaystyle {\ mathcal {Q}}}$

${\ displaystyle {\ mathcal {Q}} = \ operatorname {SET} ({\ mathcal {V}} \ operatorname {CYC} _ {1} ({\ mathcal {Z}}) + {\ mathcal {U}} {\ mathcal {V}} \ operatorname {CYC} _ {= 2} ({\ mathcal {Z}})) + {\ mathcal {U}} ^ {2} {\ mathcal {V}} \ operatorname {CYC } _ {= 3} ({\ mathcal {Z}}) + {\ mathcal {U}} ^ {3} {\ mathcal {V}} \ operatorname {CYC} _ {= 4} ({\ mathcal {Z }}) + {\ mathcal {U}} ^ {4} {\ mathcal {V}} \ operatorname {CYC} _ {= 5} ({\ mathcal {Z}}) + \ cdots)}$

onde usamos para marcar sinais e para a contagem do ciclo. ${\ displaystyle {\ mathcal {U}}}$${\ displaystyle {\ mathcal {V}}}$

Traduzindo para funções geradoras que temos

${\ displaystyle Q (z, u, v) = \ exp \ left (v {\ frac {z} {1}} + vu {\ frac {z ^ {2}} {2}} + vu ^ {2} {\ frac {z ^ {3}} {3}} + vu ^ {3} {\ frac {z ^ {4}} {4}} + vu ^ {4} {\ frac {z ^ {5}} {5}} + \ cdots \ direita).}$

Isso simplifica para

${\ displaystyle Q (z, u, v) = \ exp \ left ({\ frac {v} {u}} \ left ({\ frac {zu} {1}} + {\ frac {z ^ {2} u ^ {2}} {2}} + {\ frac {z ^ {3} u ^ {3}} {3}} + {\ frac {z ^ {4} u ^ {4}} {4}} + {\ frac {z ^ {5} u ^ {5}} {5}} + \ cdots \ right) \ right)}$

qual é

${\ displaystyle \ exp \ left ({\ frac {v} {u}} \ log {\ frac {1} {1-uz}} \ right) = \ left ({\ frac {1} {1-uz} } \ right) ^ {\ frac {v} {u}}.}$

Agora, as duas funções geradoras e de permutações pares e ímpares por contagem de ciclo são dadas por ${\ displaystyle Q_ {1} (z, v)}$${\ displaystyle Q_ {2} (z, v)}$

${\ displaystyle Q_ {1} (z, v) = {\ frac {1} {2}} Q (z, + 1, v) + {\ frac {1} {2}} Q (z, -1, v) = {\ frac {1} {2}} \ left ({\ frac {1} {1-z}} \ right) ^ {v} + {\ frac {1} {2}} \ left ({ \ frac {1} {1 + z}} \ right) ^ {- v}}$

e

${\ displaystyle Q_ {2} (z, v) = {\ frac {1} {2}} Q (z, + 1, v) - {\ frac {1} {2}} Q (z, -1, v) = {\ frac {1} {2}} \ left ({\ frac {1} {1-z}} \ right) ^ {v} - {\ frac {1} {2}} \ left ({ \ frac {1} {1 + z}} \ right) ^ {- v}.}$

Exigimos a quantidade

${\ displaystyle G (z, v) = \ left. {\ frac {d} {dv}} (Q_ {1} (z, v) -Q_ {2} (z, v)) \ right | _ {v = 1}}$

qual é

${\ displaystyle \ left. {\ frac {d} {dv}} \ left ({\ frac {1} {1 + z}} \ right) ^ {- v} \ right | _ {v = 1} = - \ left. \ log {\ frac {1} {1 + z}} \ left ({\ frac {1} {1 + z}} \ right) ^ {- v} \ right | _ {v = 1} = - (1 + z) \ log {\ frac {1} {1 + z}}.}$

Finalmente, extraindo coeficientes desta função geradora, obtemos

${\ displaystyle -n! [z ^ {n}] (1 + z) \ log {\ frac {1} {1 + z}} = - n! \ left ({\ frac {(-1) ^ {n }} {n}} + {\ frac {(-1) ^ {n-1}} {n-1}} \ direita)}$

qual é

${\ displaystyle -n! (- 1) ^ {n-1} \ left (- {\ frac {1} {n}} + {\ frac {1} {n-1}} \ right) = n! ( -1) ^ {n} {\ frac {n- (n-1)} {n (n-1)}}}$

que é por sua vez

${\ displaystyle n! (- 1) ^ {n} {\ frac {1} {n (n-1)}} = (- 1) ^ {n} (n-2)!}$

Isso conclui a prova.

Veja também

• Constante de Golomb-Dickman

Referências

links externos

• Panholzer, Alois; Prodinger, Helmut; Riedel, Marko. "Medindo transtorno pós-seleção rápida" (PDF) . Citar diário requer |journal=( ajuda )
• Arquivo da competição William Lowell Putnam
• Sung, Philip; Zhang, Yan. "Recurring Recurrences in Counting Permutations". CiteSeerX  10.1.1.91.1088 . Citar diário requer |journal=( ajuda )
• Marko Riedel et al., A diferença do número de ciclos de permutações pares e ímpares
• Marko Riedel et al., Chaves dentro de caixas fechadas, uma questão sobre probabilidade

100 prisioneiros

• Anna Gál, Peter Bro Miltersen, A complexidade da sonda celular de estruturas de dados sucintas
• Vários autores, Permutações com um ciclo> n / 2
• Vários autores, uma propriedade de perturbações
• Vários autores, número esperado de pontos fixos
• Peter Winkler, Sete quebra-cabeças que você acha que não deve ter ouvido corretamente
• Vários autores, Les-Mathematiques.net . Cent prisonniers (em francês)