Permutação

Em vários campos da matemática , o termo é usado com permutação diferentes, mas estreitamente relacionados significados. Todos eles se relacionam com a noção de (re) organizar elementos de uma dada finito definido em uma seqüência .

Definições

O conceito geral de permutação pode ser definido mais formalmente em diferentes contextos:

Na análise combinatória

Em combinatória , uma permutação é geralmente entendido como sendo uma sequência contendo cada elemento a partir de um conjunto finito uma vez e apenas uma vez. O conceito de sequência é distinta da de um conjunto, em que os elementos de uma sequência de aparecer em qualquer ordem: a sequência tem um primeiro elemento (a menos que ela está vazia), um segundo elemento (a menos que o seu comprimento é inferior a 2), e assim por diante. Em contraste, os elementos de um conjunto não têm fim; {1, 2, 3} e {3, 2, 1} são diferentes maneiras de identificar o mesmo conjunto.

No entanto, há também um significado mais geral tradicional do termo "permutação" utilizado no combinatória. Neste sentido mais geral, estas permutações são sequências em que, como anteriormente, cada elemento ocorre no máximo uma vez, mas nem todos os elementos do conjunto de dados precisam de ser usados.

Para uma noção relacionada na qual a ordenação dos elementos selecionados formam um conjunto, em que o ordenante é irrelevante, ver Combinação.

Em teoria dos grupos

Em teoria grupo e áreas afins, os elementos de uma permutação não necessita de ser dispostos numa ordem linear, ou mesmo em qualquer ordem em tudo. De acordo com esta definição refinado, uma permutação é uma bijection de um finito definir sobre si própria. Isto permite a definição dos grupos de permutações; ver Do grupo de permutações.

Contando permutações

Em apenas esta seção, a definição tradicional de análise combinatória é usado: uma permutação é uma seqüência ordenada de elementos seleccionados a partir de um determinado conjunto finito, sem repetições, e não necessariamente usar todos os elementos do conjunto dado. Por exemplo, dado o conjunto de cartas {C, E, G, I, N, R}, algumas permutações são ANEL, ARROZ, mais agradável, GOVERNO e encolher, mas também RNCGI -. A sequência não é preciso soletrar uma palavra já existente MOTOR , por outro lado, não é uma permutação, porque utiliza os elementos e e n duas vezes.

Se n indica o tamanho do conjunto - o número de elementos disponíveis para selecção - e apenas permutações são considerados todos os elementos que usam N, então o número total de permutações possíveis é igual a n, em que! "!" é o fatorial operador. Isto pode ser demonstrado como se segue informalmente. Na construção de uma permutação, n existem escolhas possíveis para o primeiro elemento da sequência. Uma vez que tenha sido escolhido,

elementos são deixados, assim, para o segundo elemento não são apenas

escolhas possíveis. Para os dois primeiros elementos juntos, que nos dá

n × (n - 1) permutações possíveis.

Para seleccionar o terceiro elemento, há então

elementos para a esquerda, dando, para os primeiros três elementos juntos,

n × (n - 1) x (n - 2) permutações possíveis.

Continuando desta maneira até que há apenas 2 elementos restantes, há duas escolhas, dando para o número de permutações possíveis consistem em

elementos:

n X (n - 1) x (n - 2) ... × 2 ×.

A última escolha é agora forçado, já que há exatamente um elemento à esquerda. Numa fórmula, isto é o número

n X (n - 1) x (n - 2) × ... × 2 × 1

(Que é a mesma que antes, porque o factor 1 não faz diferença). Este número é, por definição, o mesmo que n!.

Em geral, o número de permutações é indicado por P (N, r), _{P R,} ou, por vezes, , Onde:

• n é o número de elementos disponíveis para selecção, e
• r é o número de elementos a serem seleccionados (0 ≤ r ≤ n).

Para o caso onde

tem sido mostrado que apenas

. O processo geral é dada pela fórmula:

Tal como antes, isto pode ser mostrado por informalmente considerando a construção de uma permutação arbitrária, mas este tempo de paragem quando o comprimento r tiver sido atingido. A construção procede inicialmente como acima, mas pára em comprimento r. O número de permutações possíveis que foi, em seguida, é alcançado:

P (n, r) = n × (n - 1) x (n - 2) x ... x (n - r + 1).

Assim:

n! = N x (n - 1) x (n - 2) × ... × 2 × 1

= N x (n - 1) x (n - 2) x ... x (n - r + 1) x (n - r) × ... × 2 × 1

P = (n, r) x (n - r) × ... × 2 × 1

P = (n, r) x (n - r) !.

Mas se n! P = (n, r) x (n - r) !, então

. Por exemplo, se existe um total de 10 elementos e a seleccionar uma sequência de três elementos a partir deste conjunto, então a primeira é uma selecção a partir de 10 elementos, a partir de um lado os restantes 9, e, finalmente, do restante 8, dando

. Neste caso, n = 10, e r = 3. Usando a fórmula para calcular P (10,3),

No caso especial em que n = r a fórmula acima simplifica a:

A razão pela qual 0! = 1 0 que é! é um produto vazio, que é sempre igual a 1.

No exemplo dado no cabeçalho deste artigo, com 6 números inteiros {1..6}, esta seria: P (6,6) = 6! / (6/6)! = (1 × 2 × 3 × 4 × 5 × 6) / 0! = 720/1 = 720.

Outras notações, mais velhos incluem ⁿ P _r, P _{n, r,} ou _n P _r. Uma notação moderna comum é (n) _r que é chamado de caindo fatorial. No entanto, a mesma notação é usada para o subindo fatorial (também chamado Símbolo Pochhammer)

n (n + 1) (n + 2) ⋯ (n + r - 1) r.

Com a notação fatorial aumentar, o número de permutações é (n - r + 1) _r.

Permutações em teoria dos grupos

Como explicado em uma seção anterior, em teoria grupo, o termo permutação (de um conjunto) é reservado para um mapa bijective ( bijection) a partir de um conjunto finito sobre si mesmo. O exemplo anterior, da tomada de permutações de números de 1 a 10, seria traduzido como um mapa a partir do conjunto {1, ..., 10} para si.

Notação

Existem dois principais notações para tais permutações. Na notação relação, pode-se apenas organizar a ordem "natural" dos elementos a ser permutada em uma linha, ea nova ordenação em outra linha:

meios de permutação do s do conjunto {1,2,3,4,5} definida por s (1) = 2, S (2) = 5, S (3) = 4, S (4) = 3, S (5) = 1.

Se temos um conjunto finito de E n elementos, é, por definição, bijection com o conjunto {1, ..., n}, onde este bijeção f corresponde apenas a numeração dos elementos. Uma vez que eles são numeradas, podemos identificar as permutações do conjunto E com permutações do conjunto {1, ..., n}. (Em termos matemáticos mais, a função que mapeia uma permutação s de E para a permutação de fosof ^-1 {1, ..., n} é um morfismo da grupo simétrico de E em que de {1, ..., n}, ver abaixo).

Como alternativa, pode-se escrever a permutação em termos de como os elementos mudam quando a permutação é aplicada sucessivamente. Isto é referido como a decomposição de permutação de um produto de disjuntos ciclos. Ele funciona da seguinte forma: a partir de um elemento x, nós escrevemos a seqüência (x s (x) s ² (x) ...) até voltarmos o elemento de partida (em que ponto vamos fechar o parêntese sem escrevê-lo pela segunda vez ). Isso é chamado de ciclo associada a x 's orbitar seguinte s. Então tomamos um elemento que não escrever ainda e fazer a mesma coisa, até que tenhamos todos os elementos considerados. No exemplo acima, obtém-se: s = (2 1 5) (3 4).

Cada ciclo (x ₁ x ₂ ... x _L) representa a permutação que mapas x _i x _i na ₁ (i = 1 ... L-1) e x x _L em _1, e deixa todos os outros elementos invariante. G é chamada a duração do ciclo. Uma vez que estes ciclos têm por construção disjuntos suportes (isto é, eles agem não-trivial em subconjuntos disjuntos de E), que fazem comutar (por exemplo, (1 2 5) (3 4) = (3 4) (2 1 5)). A ordem dos ciclos na (composição) do produto não importa, enquanto a ordem dos elementos em cada ciclos importa ( até a mudança cíclica; Veja também ciclos e pontos fixos).

Obviamente, a 1 ciclo (ciclo de comprimento 1) é o mesmo que a fixação do elemento contido nele, por isso não há uso em escrevê-lo explicitamente. Definição de um ciclo de alguns autores não incluem ciclos de comprimento 1.

Ciclos de comprimento dois são chamados transposições; tais permutações meramente trocar o lugar de dois elementos. (Por outro lado, uma transposição de matriz é em si um importante exemplo de uma permutação.)

Produto e inversa de permutações

Pode-se definir o produto de dois permutações do seguinte modo. Se tivermos duas permutações, P e Q, a primeira acção de P e realizando então Q será o mesmo que executar alguma permutação R único. O produto de P e Q é então definido como sendo que R permutação. Visualizando permutações como bijeções, o produto de dois permutações é, portanto, o mesmo que a sua composição como funções. Não há nenhuma notação universalmente acordado para a operação do produto entre permutações, e dependendo do autor uma fórmula como PQ pode significar tanto P ∘ Q ou Q ∘ P. Desde composição função é associativa , por isso é a operação do produto em permutações: (P ∘ Q) ∘ R = P ∘ (Q ∘ R).

Da mesma forma, uma vez bijeções têm inversas , então, fazer permutações, e ambos P ∘ ^{P-1 e} P ^-1 ∘ P são a "permutação identidade" (veja abaixo) que deixa todas as posições inalteradas. Assim, pode ser visto que permutações formar um grupo .

Tal como para qualquer grupo, há um grupo isomorfismo em grupos de permutação, obtidos mediante a atribuição a cada permutação seu inverso, e isso é um isomorfismo involução, dando um duplo ponto de vista sobre qualquer resultado abstrato. Desde (P ∘ Q) ^-1 = Q ^-1 ∘ ^P-1, de um ponto de vista abstrato, é irrelevante que PQ representa "P antes Q" ou "P após Q". Para permutações de betão, a distinção é, naturalmente, bastante material.

Permutações especiais

Se se pensar que uma permutação de "alterações" na posição do primeiro elemento com o primeiro elemento, o segundo ao segundo, e assim por diante, que realmente não mudaram as posições dos elementos de todo. Devido à sua ação, nós descrevemos isto como a permutação identidade porque ele atua como um função identidade. Por outro lado, uma permutação que altera a posição de todos os elementos (nenhum elemento é mapeado para si mesmo) é chamado um desarranjo.

Se alguém tem alguma permutação, chamado P, pode-se descrever uma permutação, P ^-1 escrito, o que desfaz a ação de aplicar P. Em essência, realizando P, então P ^-1 equivale a executar a permutação de identidade. A gente sempre tem essa permutação desde uma permutação é um mapa bijective. Tal permutação é chamado o permutação inversa. É calculada através da troca de cada número e o número do lugar que ele ocupa.

Um mesmo permutação é uma permutação que pode ser expressa como o produto de um número par de transposições, e a identidade de permutação é uma permutação ao mesmo tempo que é igual a (1 2) (1 2). Um permutação impar é uma permutação que pode ser expressa como o produto de um número ímpar de transposições. Pode ser mostrado que todas as permutações ou é par ou ímpar e não podem ser ambos.

Um teorema sobre a permutação inverso é o efeito de uma conjugação de uma permutação por uma permutação de um grupo de permutação. Se temos uma permutação Q = (i ₁ i ₂ i ... _n) e uma permutação P, então PQP ^-1 = (P (i ₁₎ P (i ₂₎ ... P (i _n)).

Nós também pode representar uma permutação na matriz de forma; a matriz resultante é conhecida como um matriz de permutação.

Permutações em computação

Alguns dos livros antigos olhar permutações, as atribuições, como mencionado acima. Em Ciência da Computação termos, estes são operações de cessão, com valores

1, 2, ..., n

atribuídos a variáveis

x _1, x _2, ..., x _n.

Cada valor deve ser atribuído apenas uma vez.

A diferença de atribuição / substituição é, em seguida, ilustrativa de uma forma em que programação funcional e programação imperativa diferem - programação funcional pura não tem mecanismo de atribuição. A convenção matemática é hoje em dia que permutações são apenas funções ea operação nelas é composição de função ; programadores funcionais seguem isso. Na linguagem atribuição de uma substituição é uma instrução para exibir rodada os valores atribuídos, simultaneamente; um problema bem conhecido.

Numeração permutações

Factoradic números podem ser usados para atribuir números exclusivos de permutações, de tal modo que uma dada factoradic de k se pode encontrar rapidamente a permutação correspondente.

Algoritmos para gerar permutações

Geração Unordered

! Para cada número k, com 0 ≤ k <n, o seguinte algoritmo gera uma permutação da sequência original inicial s _{j, j} = 1 ... N:

  função de permutação (K, S) {
      var int fatorial: = 1;
      para j = 2 ao comprimento (s) {
         fatorial: fatorial = * (j-1);  // Fatorial = (j-1)!
         de swap s [j- ((k / fatorial) mod j)] com s [j];
      }
      retornar s;
  }

Geração ordem lexicográfica

! Para cada número k, com 0 ≤ k <n, o seguinte algoritmo gera a permutação lexicographical correspondente da sequência inicial s _{j, j} = 1 ... N:

  função de permutação (K, S) {
      var int n: = comprimento (s);  fatorial: = 1;
      para j = 2 a n-1 {// calcular (n-1)!
          fatorial: fatorial * = j;
      }
      para j = 1 a N- {1
          tempj: = (k / fatorial) mod (n + 1- j);
          temps: = s [j + tempj]
          para i = j + tempj para j + 1 passo -1 {
              s [i]: = s [i-1];  // Deslocar o direito cadeia
          }
          s [j]: = temps;
          fatorial: fatorial = / (j n-);
      }
      retornar s;
  }

Notação

• k / J indica a divisão inteira de k por j, ou seja, o integral quociente sem qualquer restante, e
• k mod j é a restante seguinte divisão inteira de k por j.
• s [n] indica o n-ésimo elemento de sequência s.

Software e hardware implementações

As funções da calculadora

A maioria das calculadoras têm uma função built-in para o cálculo do número de permutações, chamado nPr ou PERM em muitos. A função de permutações é muitas vezes só está disponível através de várias camadas de menus; como acessar a função geralmente é indicado na documentação para calculadoras que o suportam.

Funções de planilha

Mais software de planilha eletrônica também oferece uma função built-in para o cálculo do número de permutações, chamado PERMUT em muitas planilhas populares. Apple Números nomeadamente software não inclui actualmente uma tal função.