Permutação parcial

Na matemática combinatória, a permutação parcial em um conjunto finito S é uma bijeção entre dois subconjuntos específicos de S. Ou seja, é definida por dois subconjuntos U e V de tamanhos iguais e com mapeamento um-para-um de U para V. De forma equivalente, é uma função parcial em S, que pode ser estendida para uma permutação.^[1]^[2]

É comum considerar o caso onde o conjunto S é simplesmente o conjunto {1, 2, …, n} dos primeiros n inteiros. Neste caso, a permutação parcial pode ser representada por uma string de n símbolos, alguns dos quais são números distintos em um intervalo 1 para $n$ e os remanescentes possuem um símbolo especial redondo ◊. Nesta formulação, o domínio U da permutação parcial, consiste nas posições da sting que não contém o símbolo redondo, e cuja posição é mapeada para um número naquela posição. Por exemplo: A string "1◊2" pode representar a permutação parcial que mapeia 1 para ele mesmo e mapeia 3 para 2.^[3]

Alguns autores restringem a permutação parcial de modo que o domínio ^[4] ou o intervalo^[3] da bijeção consiste dos primeiros k itens do conjunto dos n itens sendo permutados por algum k. No caso formal, a permutação parcial de tamanho k de um conjunto-n é apenas umas seqüência de k termos do conjunto-n, sem repetição. (Em combinações elementárias, esse objetos são as vezes confusamente chamados "permutação-k" do conjunto-n). Alguns autores restringem permutações parciais

Referências

↑ Straubing, Howard (1983), «A combinatorial proof of the Cayley-Hamilton theorem», Discrete Mathematics, 43 (2-3): 273–279, MR 685635, doi:10.1016/0012-365X(83)90164-4 .
↑ Ku, C. Y.; Leader, I. (2006), «An Erdős-Ko-Rado theorem for partial permutations», Discrete Mathematics, 306 (1): 74–86, MR 2202076, doi:10.1016/j.disc.2005.11.007 .
↑ ^a ^b Claesson, Anders; Jelínek, Vít; Jelínková, Eva; Kitaev, Sergey (2011), «Pattern avoidance in partial permutations», Electronic Journal of Combinatorics, 18 (1): Paper 25, 41, MR 2770130 .
↑ Burstein, Alexander; Lankham, Isaiah (2010), «Restricted patience sorting and barred pattern avoidance», Permutation patterns, London Math. Soc. Lecture Note Ser., 376, Cambridge: Cambridge Univ. Press, pp. 233–257, MR 2732833, doi:10.1017/CBO9780511902499.013 .

[1] Straubing, Howard (1983), «A combinatorial proof of the Cayley-Hamilton theorem», Discrete Mathematics, 43 (2-3): 273–279, MR 685635, doi:10.1016/0012-365X(83)90164-4 .

[2] Ku, C. Y.; Leader, I. (2006), «An Erdős-Ko-Rado theorem for partial permutations», Discrete Mathematics, 306 (1): 74–86, MR 2202076, doi:10.1016/j.disc.2005.11.007 .

[cjjk-3] Claesson, Anders; Jelínek, Vít; Jelínková, Eva; Kitaev, Sergey (2011), «Pattern avoidance in partial permutations», Electronic Journal of Combinatorics, 18 (1): Paper 25, 41, MR 2770130 .

[4] Burstein, Alexander; Lankham, Isaiah (2010), «Restricted patience sorting and barred pattern avoidance», Permutation patterns, London Math. Soc. Lecture Note Ser., 376, Cambridge: Cambridge Univ. Press, pp. 233–257, MR 2732833, doi:10.1017/CBO9780511902499.013 .

[1]

[2]

[3]

[4]