Permutação

Origem: Wikipédia, a enciclopédia livre.

Este artigo encontra-se parcialmente em língua estrangeira. Ajude e colabore com a tradução.

Em matemática, especialmente na álgebra abstrata e áreas relacionadas, uma permutação é uma bijeção, de um conjunto finito X nele mesmo.

Em combinatória, o termo permutação tem um significado tradicional, que é usado para incluir listas ordenadas sem repetição, mas não exaustiva (so of less than maximum length).

O conceito de permutação expressa a idéia de que objetos distintos podem ser arranjados em inúmeras ordens diferentes. Por exemplo, quando se dá dois passos, um após o outro, podemos ter duas permutações: "pé esquerdo-pé direito" ou "pé direito-pé esquerdo", dependendo apenas do pé que dá o primeiro passo. Um exemplo mais complexo seria o do "change ringing", que é a arte de badalar sinos de afinação distinta em uma série de padrões. Há muitas ordens diferentes na qual um conjunto de seis sinos, cujas afinações diferem entre si, ou seja, cada um com um tom diferente, pode soar. Se os sinos forem numerados de um a seis, cada possível ordem terá uma lista com os números referente a ela e não haverá repetição alguma.

Há inúmeras formas de se definir mais formalmente o conceito de permutação. Uma permutação de um alfabeto de 26 letras, por exemplo, é uma cadeia de letras com 26 delas, aparecendo, cada uma, uma única vez; esta definição funciona para qualquer alfabeto com N letras formando cadeias com comprimento de N letras. Ou seja, uma permutação é simplesmente uma sequência ordenada sem duas ou mais repetições de cada elemento retirado de um conjunto fixo de símbolos, e com comprimento máximo. Pode-se assim apontar a diferença essencial entre uma permutação e um conjunto: em uma permutação, a ordem é relevante, já que os elementos são arranjados em uma ordem específica.

[editar] Arranjos e substituições

Consideremos mais de perto o exemplo do badalar de sinos. Vamos assumir que temos seis posições fixas nas quais um sino pode badalar (primeira, segunda, ..., sexta); e que temos seis sinos (sejam A, B, ..., F as notas da escala). Assim, o que chama-se arranjo é algo parecido com

B-A-F-E-D-C,

com cada sino posto em sua posição ordenada. O que chama-se substituição é uma ordem do tipo 'mudar a ordem na qual A e F são tocadas e a ordem na qual E e F são tocadas'. Esta substituição nos daria um novo arranjo,

B-F-A-D-E-C.

A distinção entre arranjo e substituição é importante. Por exemplo, no badalar de sinos, nem todas as substituições são possíveis, por questões práticas. As instruções para os badaladores de sinos tomam a forma de uma lista de arranjos, na qual apenas sinos vizinhos são intercambiados de uma 'rodada' a outra.

Tanto os arranjos como as substituições são comumente chamadas de permutações. Na Matemática, porém, a frase permutação de um conjunto sempre se refere a uma substituição.

[editar] Counting permutations

Somente nessa seção, a definição tradicional é usada: a permutation is an ordered list without repetitions. It is easy to count the number of permutations of size r when chosen from a set of size n (obviously with r≤n).

For example, if we have a total of 10 elements, the integers {1, 2, ..., 10}, a permutation of three elements from this set is (2,3,1). In this case, n = 10 and r = 3. So how many ways can this completely be done?

1. We can pretend to select the first member of all permutations out of n choices because there are n distinct elements from the generating set.
2. Next, since we have used one of the n elements already, the second member of the permutation has (n − 1) elements to choose from the remaining set.
3. The third member can be filled in (n − 2) ways since 2 have been used already.
4. This pattern continues until there are r members on the permutation. This means that the last member can be filled in (n − r + 1) ways.

Summarizing, we find that a total of

n(n − 1)(n − 2) ... (n − r + 1)

different permutations of r objects, taken from a pool of n objects, exist. If we denote this number by P(n, r) and use the factorial notation, we can write

.

In the above example, we have n = 10 and r = 3, so to find out how many unique sets, such as the one previously, we can find, we need to calculate P(10,3) = 720.

Other, older notations include ⁿP_r, P_n,r, or _nP_r.

A common modern notation is (n)_r which is called a falling factorial. However, the same notation is used for the rising factorial (also called Pochhammer symbol)

n(n + 1)(n + 2)...(n + r − 1).

In the latter case, the number of permutations is (n + r − 1)_r.

[editar] Abstract algebra

As explained in a previous section, in abstract algebra and other mathematical fields, the term permutation (of a set) is now reserved for a bijective map (bijection) from a finite set onto itself. The earlier example, of making permutations out of numbers 1 to 10, would be translated as a map from the set {1, ..., 10} to itself.

There are two main notations for such permutations. In relation notation, one can just arrange the "natural" ordering of the elements being permuted on a row, and the new ordering on another row:

This means that in the first position, the second element of the set should be placed, in the second position, the fifth element in the set should be placed, and so on. Alternatively, if we have a finite set of elements (which need not be integers), we can firstly create an association between each element and an integer - more precisely, we can create a mapping ν(s) : S -> Z where ν is bijective, and S is our pool of elements. One can then read the above notation as mapping the element ν^-1(1) to element ν^-1(2), element ν^-1(2) to element ν^-1(5), and so on.

Alternatively, we can write the permutation in terms of how the elements change when the permutation is successively applied. If we look at the above permutation as an example, if we take an element in the first position, the result of applying the permutation is then placed in the second position, the result of applying the permutation again is placed in the third position, and if we were to apply the permutation again we see that the element has now returned to the first permutation. We say that the behaviour of such an element is a cycle, and we can write this cycle as (1 2 5), or alternatively as (2 5 1) or (5 1 2), but not as e.g. (1 5 2). The next cycle begins with any other element not considered till now, until every element appears in a cycle.

As such, we can write the permutation as a set of cycles. The previous permutation just considered has cycle form (1 2 5)(3 4). The order of the cycles is not significant (but, as said before, the order of the elements within a cycle is, up to cyclic change). Thus, the same permutation could be written as e.g (4 3)(2 5 1). The "canonical" form for a permutation places the lowest-numbered position in each cycle first in that cycle and then orders the cycles by increasing first element.

This notation often omits fixed points, that is, elements mapped to themselves; thus (1 3)(2)(4 5) can become simply (1 3)(4 5), since a cycle of just one element has no effect.

A permutation consisting of one cycle is itself called a cycle. The number of entries of a cycle is called the length. For example, the length of (1 2 5) is three. A special terminology is used to describe cycles of length two - these are transpositions - since in a length two cycle, the elements are merely transposed.

[editar] Special permutations

If we think of a permutation that "changes" the position of the first element to the first element, the second to the second, and so on, we really have not changed the positions of the elements at all. Because of its action, we describe it as the identity permutation because it acts as an identity function.

If we have some permutation called P, the identity permutation I, we can describe a permutation, written P^-1, which undoes the action of applying P. In essence, performing P then P^-1 is the same as performing the identity permutation. We always have such a permutation since a permutation is a bijective map. Such a permutation is called the inverse permutation.

One can define the product of two permutations. If we have two permutations, P and Q, the action of performing P and Q will be the same as performing some other permutation, R, itself. Note that R could be P or Q. The product of P and Q is defined to be the permutation R. For more, see symmetric group and permutation group.

An even permutation is a permutation which can be expressed as the product of an even number of transpositions, and the identity permutation is an even permutation as it equals (1 2)(1 2). An odd permutation is a permutation which can be expressed as the product of an odd number of transpositions. It can be shown that every permutation is either odd or even and can't be both.

We can also represent a permutation in matrix form - the resulting matrix is known as a permutation matrix.

[editar] Permutations in computing

Some of the older textbooks do look at permutations as assignments, as mentioned above. In computer science terms, these are assignment operations, with values

1, 2, ..., n

assigned to variables

x₁, x₂, ..., x_n.

Each value should be assigned just once.

The assignment/substitution difference is then illustrative of one way in which functional programming and imperative programming differ — pure functional programming has no assignment mechanism. The mathematics convention is nowadays that permutations are just functions and the operation on them is function composition; functional programmers follow this. In the assignment language a substitution is an instruction to switch round the values assigned, simultaneously; a well-known problem.

[editar] Numbering permutations

Factoradic numbers can be used to assign unique numbers to permutations, such that given a factoradic n, one can quickly find the corresponding permutation.

[editar] See also

• Cyclic permutation
• Permutations and combinations
• Even and odd permutations
• Combinations
• Josephus permutation
• Symmetric group
• Permutation group
• Cyclic order
• Weak order of permutations
• Substitution cipher
• Sorting network
• Random permutation