Transposition
I matematiken är en transposition en permutation av en mängd, där alla element utom precis två är fixpunkter. Intuitivt sett betyder detta att man "byter plats på två element, men lämnar alla andra element på sina platser".
Transpositioner utgör ett slags "grundläggande byggstenar" för permutationer, därför att varje permutation av en ändlig mängd är en produkt av transpositioner.
Exempel
[redigera | redigera wikitext]Betrakta permutationen σ av mängden {1, 2, 3, 4, 5} som omvandlar begynnelseordningen 12345 till 34521. Denna kan erhållas genom tre transpositioner: byt först plats på 1 och 3, sedan på 2 och 4, och till sist på 1 och 5.
![{\displaystyle \sigma ={\begin{pmatrix}1&2&3&4&5\\3&4&5&2&1\end{pmatrix}}={\begin{pmatrix}1&3\end{pmatrix}}{\begin{pmatrix}2&4\end{pmatrix}}{\begin{pmatrix}1&5\end{pmatrix}}[={\begin{pmatrix}1&5\end{pmatrix}}{\begin{pmatrix}5&3\end{pmatrix}}{\begin{pmatrix}2&4\end{pmatrix}}].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/23657dc8063b37b7b3d796b89510b9495c13c450)
Det finns många andra sätt att skriva σ som en produkt (sammansättning) av transpositioner, till exempel
- σ = (2 3) (1 2) (2 4) (3 5) (4 5).
En permutation som kan erhållas genom ett jämnt antal transpositioner säges ha jämn paritet, en som kan åstadkommas genom ett udda antal transpositioner har udda paritet.