| dbo:abstract
|
- En matemàtiques, les permutacions (és a dir, les bijeccions en els conjunts finits) es poden descompondre en un producte de transposicions, és a dir en una successió d'intercanvis d'elements dos a dos.
* Una permutació parella és una permutació que es pot expressar com el producte d'un nombre parell de transposicions;
* Una permutació senar és una permutació es pot expressar com el producte d'un nombre senar de transposicions. El signe d'una permutació val 1 si és parella i -1 si és senar. L'aplicació signe constitueix un morfisme de grups. Intervé en àlgebra multilineal, sobretot per al càlcul de determinants. (ca)
- Znaménko permutace (značené obvykle jako sgn(σ), též označováno jako parita permutace) je charakteristika konkrétní permutace (seřazení množiny čísel), která vyjadřuje, zda je počet inverzí této permutace (počet prvků prohozených oproti seřazené posloupnosti) sudý či lichý. Vyjadřuje se čísly ±1 či pouze příslušným znaménkem +/-: sudý počet inverzí odpovídá kladnému znaménku, lichý zápornému. Tuto vlastnost lze zapsat tak, že sgn(σ) = (−1)n, kde n je počet inverzí permutace, nebo počet cyklů sudé délky. (cs)
- في الرياضيات، حين تكون X مجموعة منتهية ما عدد عناصرها يزيد عن الاثنين، تُقسم تبديلات X إلى صنفين اثنين متساويين من حيث عددُ العناصر : التبديلات الزوجية (بالإنجليزية: even permutations) والتبديلات الفردية (بالإنجليزية: odd permutations). يُميز بين الصنفين الاثنين كما يلي: إذا عُرف ترتيب كلي على X، فزوجية تبديلة من X يعرف بزوجية عدد الأزواج x, y اللائي عرّضتهن . وبتعبير أبسط، هو عدد الأزواج x, y حيث x < y و σ(x) > σ(y). (ar)
- Das Vorzeichen, auch Signum, Signatur oder Parität genannt, ist in der Kombinatorik eine wichtige Kennzahl von Permutationen. Das Signum einer Permutation kann die Werte oder annehmen, wobei man im ersten Fall von einer geraden und im zweiten Fall von einer ungeraden Permutation spricht. Es gibt mehrere Möglichkeiten, gerade und ungerade Permutationen zu charakterisieren. So ist eine Permutation genau dann gerade, wenn die Anzahl der Fehlstände in der Permutation gerade ist. Jede Permutation lässt sich auch als Verkettung endlich vieler Transpositionen darstellen und ist genau dann gerade, wenn die Anzahl der dabei benötigten Transpositionen gerade ist. Eine Permutation kann zudem auch in Zyklen zerlegt werden und ist genau dann gerade, wenn die Anzahl der Zyklen gerader Länge gerade ist. Das Signum einer Permutation ist auch gleich der Determinante der zugehörigen Permutationsmatrix. Das Signum ist als Abbildung ein Gruppenhomomorphismus von der symmetrischen Gruppe der Permutationen in die multiplikative Gruppe über der Menge . Ein wichtiges Einsatzbeispiel des Signums ist die Leibniz-Formel für Determinanten. (de)
- En mathématiques, une permutation de support fini est dite paire si elle présente un nombre pair d', impaire sinon. La signature d'une permutation vaut 1 si celle-ci est paire, –1 si elle est impaire. L'application signature, du groupe symétrique dans le groupe ({–1, 1}, ×), est un morphisme, c'est-à-dire qu'elle vérifie analogue à la règle des signes. Toute permutation se décompose en un produit de transpositions. , il vient de que la parité du nombre de transpositions d'une telle décomposition coïncide avec la parité de la permutation (et ne dépend donc pas de la décomposition choisie). Tout morphisme de dans un groupe abélien se factorise par le morphisme signature. La signature intervient notamment en algèbre linéaire, dans la formule de Leibniz qui est une façon de définir le déterminant d'une matrice carrée. (fr)
- En matemáticas, las permutaciones pueden descomponerse en un producto de transposiciones, es decir, en una sucesión de intercambios de elementos dos a dos.
* Una permutación par es una permutación que puede ser representada por un número par de transposiciones.
* Una permutación impar es una permutación que puede ser representada por un número impar de transposiciones. La paridad o signatura de una permutación vale 1 si esta es par y -1 si es impar. La aplicación correspondiente a la paridad constituye un homomorfismo de grupos. Es importante en álgebra multilineal, sobre todo en el cálculo de determinantes. (es)
- In mathematics, when X is a finite set with at least two elements, the permutations of X (i.e. the bijective functions from X to X) fall into two classes of equal size: the even permutations and the odd permutations. If any total ordering of X is fixed, the parity (oddness or evenness) of a permutation of X can be defined as the parity of the number of inversions for σ, i.e., of pairs of elements x, y of X such that x < y and σ(x) > σ(y). The sign, signature, or signum of a permutation σ is denoted sgn(σ) and defined as +1 if σ is even and −1 if σ is odd. The signature defines the alternating character of the symmetric group Sn. Another notation for the sign of a permutation is given by the more general Levi-Civita symbol (εσ), which is defined for all maps from X to X, and has value zero for non-bijective maps. The sign of a permutation can be explicitly expressed as sgn(σ) = (−1)N(σ) where N(σ) is the number of inversions in σ. Alternatively, the sign of a permutation σ can be defined from its decomposition into the product of transpositions as sgn(σ) = (−1)m where m is the number of transpositions in the decomposition. Although such a decomposition is not unique, the parity of the number of transpositions in all decompositions is the same, implying that the sign of a permutation is well-defined. (en)
- 数学において、少なくとも二元を含む有限集合 X の置換（X から X への全単射）は大きく二つのクラス（偶置換と奇置換）に分けられる。X の任意の全順序を固定して、X の置換 σ の偶奇性（パリティ; 対性）は σ の転倒数、すなわち X の元の対 (x, y) で x < y かつ σ(x) > σ(y) なるものの数、の偶奇性によって定義することができる。 置換 σ の符号 (sign) あるいは符号数 (signature) sgn(σ) は、σ が偶置換ならば +1, 奇置換ならば −1 を割り当てる。置換の符号函数 sgn は対称群 Sn の交代指標と呼ばれる群指標を定義する。置換の符号に対する別の記法として、より一般のレヴィ–チヴィタ記号によって与えられる εσ がある。これは X から X への全単射とは限らない任意の写像に対して定義され、全単射でない写像に対しては 0 を割り当てる。 置換の符号は inv(σ) を σ の転倒数とすれば sgn(σ) = (−1)inv(σ) と明示的に書くことができる。 あるいは、置換の符号を置換の互換の積への分解によって定義することもできる。すなわち、置換 σ の互換の積への分解に現れる互換の数を m とするとき、 sgn(σ) = (−1)m とおくのである。置換のこのような互換の積への分解は一意ではないけれども、分解に現れる互換の総数の偶奇は置換ごとに一定しているので、この方法で置換の符号は矛盾なく定まる。 (ja)
- Em matemática, quando X é um conjunto finito de ao menos dois elementos, as permutações de X (i.e. as funções bijectivas de X a X) caem em duas classes de igual tamanho: as permutações ímpares e as permutações pares. Se qualquer relação de ordem de X é fixada, a paridade (ser par ou ser ímpar) de uma permutação de X pode ser definida como a paridade do número de inversões para , i.e., de pares de elementos de X tal que e . O número de inversões depende da ordem, mas a paridade não. (pt)
- Inom matematiken, när X är en ändlig mängd med minst två element, delas permutationerna av X (det vill säga de bijektiva funktionerna från X till X) i två klasser av lika storlek: de jämna permutationerna och de udda permutationerna. Om en linjär ordning av X föreligger så kan pariteten för en permutation σX definieras som antalet inversioner för σ, det vill säga antalet par av element x, y i X sådana att och . Tecknet eller signaturen för en permutation σ betecknas sgn(σ) och definieras som +1 om σ är jämnt och som -1 om σ är udda. Signaturen bestämmer den alternerande för den symmetriska gruppen Sn. En annan notation för permutationens tecken ges av den mera allmänna Levi-Civita-tensorn, som definieras för alla avbildningar från X till X, och har värdet noll för icke -bijektiva avbildningar. En permutations tecken kan explicit uttryckas som sgn(σ) = (−1)N(σ) där inversionstalet N(σ) är antalet inversioner i σ. En permutations σ tecken kan också definieras som den sammansatta produkten av transpositioner som sgn(σ) = (−1)m där m är antalet transpositioner i sammansättningen. Fastän en sådan sammansättning inte är unik är pariteten för antalet transpositioner alltid densamma, vilket medför att en permutations tecken är . (sv)
- Парність перестановки скінченної множини — це парність кількості інверсії цієї множини. Множина перестановок розбивається на рівні підмножини: парних і непарних перестановок. (uk)
- 在数学中，当X是一个至少有两个元素的有限集合时，X的置换（即从X到X的双射）可分为大小相同的两类：奇置换与偶置换。如果X固定了任何一个全序，X的一个置换的奇偶性可以定义为中反向对个数的奇偶性。所谓反向对即X中二元组使得且。这里为置换中第位的元素。 一个置换的符号（sign或signature）记作sgn(σ)：如果是偶数则定义为 +1，如果是奇数则定义为 -1。符号定义了对称群Sn的交错。置换的符号另一个更一般的符号为列维-奇维塔符号（），定义在X到X的所有映射上，而在非双射映射上取值为0。 置换的符号可以清晰地表达为 这里是中反向对的个数。或者，置换的符号也可通过分解定义为 这里m是分解中对换的个数。尽管这样一个分解不是惟一的，所有分解中对换个数的奇偶性是相同的，蕴含着置换的符号是良定义的。 (zh)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageInterLanguageLink
| |
| dbo:wikiPageLength
|
- 18403 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:content
|
- and (en)
- Consider the elements that are sandwiched by the two elements of a transposition. Each one lies completely above, completely below, or in between the two transposition elements.
An element that is either completely above or completely below contributes nothing to the inversion count when the transposition is applied. Elements in-between contribute .
As the transposition itself supplies inversion, and all others supply 0 inversions, a transposition changes the parity of the number of inversions. (en)
- is called an inversion. We want to show that the count of inversions has the same parity as the count of 2-element swaps. To do that, we can show that every swap changes the parity of the count of inversions, no matter which two elements are being swapped and what permutation has already been applied.
Suppose we want to swap the ith and the jth element. Clearly, inversions formed by i or j with an element outside of (en)
- , which has the same parity as n.
Similarly, the count of inversions j gained also has the same parity as n. Therefore, the count of inversions gained by both combined has the same parity as 2n or 0. Now if we count the inversions gained by swapping the ith and the jth element, we can see that this swap changes the parity of the count of inversions, since we also add 1 to the number of inversions gained for the pair .
Note that initially when no swap is applied, the count of inversions is 0. Now we obtain equivalence of the two definitions of parity of a permutation. (en)
- A third approach uses the presentation of the group Sn in terms of generators τ1, ..., τn−1 and relations
* for all i
* for all i < n − 1
* if
[Here the generator represents the transposition (en)
- .] All relations keep the length of a word the same or change it by two. Starting with an even-length word will thus always result in an even-length word after using the relations, and similarly for odd-length words. It is therefore unambiguous to call the elements of Sn represented by even-length words "even", and the elements represented by odd-length words "odd". (en)
- Recall that a pair x, y such that (en)
- inversions are formed. The count of inversions i gained is thus (en)
- Let σ be a permutation on a ranked domain S. Every permutation can be produced by a sequence of transpositions . Let the following be one such decomposition
:σ = T1 T2 ... T'k
We want to show that the parity of k is equal to the parity of the number of inversions of σ.
Every transposition can be written as a product of an odd number of transpositions of adjacent elements, e.g.
: = .
Generally, we can write the transposition on the set {1,...,i,...,i+d,...} as the composition of 2d−1 adjacent transpositions by recursion on d:
* The base case d=1 is trivial.
* In the recursive case, first rewrite as . Then recursively rewrite as adjacent transpositions.
If we decompose in this way each of the transpositions T1 ... T'k above, we get the new decomposition:
:σ = A1 A2 ... Am
where all of the A1...Am are adjacent. Also, the parity of m is the same as that of k.
This is a fact: for all permutation τ and adjacent transposition a, aτ either has one less or one more inversion than τ. In other words, the parity of the number of inversions of a permutation is switched when composed with an adjacent transposition.
Therefore, the parity of the number of inversions of σ is precisely the parity of m, which is also the parity of k. This is what we set out to prove.
We can thus define the parity of σ to be that of its number of constituent transpositions in any decomposition. And this must agree with the parity of the number of inversions under any ordering, as seen above. Therefore, the definitions are indeed well-defined and equivalent. (en)
- [i, j] (en)
- elements within the interval (en)
- n − 2vi (en)
- n − vi (en)
- n = 3 (en)
- n = j − i − 1 (en)
- will not be affected.
For the (en)
- x < y (en)
- , assume v'i of them form inversions with i and v'j of them form inversions with j. If i and j are swapped, those vi inversions with i are gone, but (en)
- , we have
:
Now for a given permutation σ of the numbers {1, ..., n}, we define
:
Since the polynomial has the same factors as except for their signs, it follows that sgn is either +1 or −1. Furthermore, if σ and τ are two permutations, we see that
:
Since with this definition it is furthermore clear that any transposition of two elements has signature −1, we do indeed recover the signature as defined earlier. (en)
- An alternative proof uses the Vandermonde polynomial
:
So for instance in the case (en)
- σ > σ (en)
|
| dbp:header
|
- Proof 1 (en)
- Proof 2 (en)
- Proof 3 (en)
- Proof 4 (en)
- Proof 5 (en)
|
| dbp:title
| |
| dbp:urlname
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- Znaménko permutace (značené obvykle jako sgn(σ), též označováno jako parita permutace) je charakteristika konkrétní permutace (seřazení množiny čísel), která vyjadřuje, zda je počet inverzí této permutace (počet prvků prohozených oproti seřazené posloupnosti) sudý či lichý. Vyjadřuje se čísly ±1 či pouze příslušným znaménkem +/-: sudý počet inverzí odpovídá kladnému znaménku, lichý zápornému. Tuto vlastnost lze zapsat tak, že sgn(σ) = (−1)n, kde n je počet inverzí permutace, nebo počet cyklů sudé délky. (cs)
- في الرياضيات، حين تكون X مجموعة منتهية ما عدد عناصرها يزيد عن الاثنين، تُقسم تبديلات X إلى صنفين اثنين متساويين من حيث عددُ العناصر : التبديلات الزوجية (بالإنجليزية: even permutations) والتبديلات الفردية (بالإنجليزية: odd permutations). يُميز بين الصنفين الاثنين كما يلي: إذا عُرف ترتيب كلي على X، فزوجية تبديلة من X يعرف بزوجية عدد الأزواج x, y اللائي عرّضتهن . وبتعبير أبسط، هو عدد الأزواج x, y حيث x < y و σ(x) > σ(y). (ar)
- Em matemática, quando X é um conjunto finito de ao menos dois elementos, as permutações de X (i.e. as funções bijectivas de X a X) caem em duas classes de igual tamanho: as permutações ímpares e as permutações pares. Se qualquer relação de ordem de X é fixada, a paridade (ser par ou ser ímpar) de uma permutação de X pode ser definida como a paridade do número de inversões para , i.e., de pares de elementos de X tal que e . O número de inversões depende da ordem, mas a paridade não. (pt)
- Парність перестановки скінченної множини — це парність кількості інверсії цієї множини. Множина перестановок розбивається на рівні підмножини: парних і непарних перестановок. (uk)
- 在数学中，当X是一个至少有两个元素的有限集合时，X的置换（即从X到X的双射）可分为大小相同的两类：奇置换与偶置换。如果X固定了任何一个全序，X的一个置换的奇偶性可以定义为中反向对个数的奇偶性。所谓反向对即X中二元组使得且。这里为置换中第位的元素。 一个置换的符号（sign或signature）记作sgn(σ)：如果是偶数则定义为 +1，如果是奇数则定义为 -1。符号定义了对称群Sn的交错。置换的符号另一个更一般的符号为列维-奇维塔符号（），定义在X到X的所有映射上，而在非双射映射上取值为0。 置换的符号可以清晰地表达为 这里是中反向对的个数。或者，置换的符号也可通过分解定义为 这里m是分解中对换的个数。尽管这样一个分解不是惟一的，所有分解中对换个数的奇偶性是相同的，蕴含着置换的符号是良定义的。 (zh)
- En matemàtiques, les permutacions (és a dir, les bijeccions en els conjunts finits) es poden descompondre en un producte de transposicions, és a dir en una successió d'intercanvis d'elements dos a dos.
* Una permutació parella és una permutació que es pot expressar com el producte d'un nombre parell de transposicions;
* Una permutació senar és una permutació es pot expressar com el producte d'un nombre senar de transposicions. (ca)
- Das Vorzeichen, auch Signum, Signatur oder Parität genannt, ist in der Kombinatorik eine wichtige Kennzahl von Permutationen. Das Signum einer Permutation kann die Werte oder annehmen, wobei man im ersten Fall von einer geraden und im zweiten Fall von einer ungeraden Permutation spricht. Das Signum ist als Abbildung ein Gruppenhomomorphismus von der symmetrischen Gruppe der Permutationen in die multiplikative Gruppe über der Menge . Ein wichtiges Einsatzbeispiel des Signums ist die Leibniz-Formel für Determinanten. (de)
- En matemáticas, las permutaciones pueden descomponerse en un producto de transposiciones, es decir, en una sucesión de intercambios de elementos dos a dos.
* Una permutación par es una permutación que puede ser representada por un número par de transposiciones.
* Una permutación impar es una permutación que puede ser representada por un número impar de transposiciones. (es)
- En mathématiques, une permutation de support fini est dite paire si elle présente un nombre pair d', impaire sinon. La signature d'une permutation vaut 1 si celle-ci est paire, –1 si elle est impaire. L'application signature, du groupe symétrique dans le groupe ({–1, 1}, ×), est un morphisme, c'est-à-dire qu'elle vérifie analogue à la règle des signes. Toute permutation se décompose en un produit de transpositions. , il vient de que la parité du nombre de transpositions d'une telle décomposition coïncide avec la parité de la permutation (et ne dépend donc pas de la décomposition choisie). (fr)
- In mathematics, when X is a finite set with at least two elements, the permutations of X (i.e. the bijective functions from X to X) fall into two classes of equal size: the even permutations and the odd permutations. If any total ordering of X is fixed, the parity (oddness or evenness) of a permutation of X can be defined as the parity of the number of inversions for σ, i.e., of pairs of elements x, y of X such that x < y and σ(x) > σ(y). The sign of a permutation can be explicitly expressed as sgn(σ) = (−1)N(σ) where N(σ) is the number of inversions in σ. sgn(σ) = (−1)m (en)
- 数学において、少なくとも二元を含む有限集合 X の置換（X から X への全単射）は大きく二つのクラス（偶置換と奇置換）に分けられる。X の任意の全順序を固定して、X の置換 σ の偶奇性（パリティ; 対性）は σ の転倒数、すなわち X の元の対 (x, y) で x < y かつ σ(x) > σ(y) なるものの数、の偶奇性によって定義することができる。 置換 σ の符号 (sign) あるいは符号数 (signature) sgn(σ) は、σ が偶置換ならば +1, 奇置換ならば −1 を割り当てる。置換の符号函数 sgn は対称群 Sn の交代指標と呼ばれる群指標を定義する。置換の符号に対する別の記法として、より一般のレヴィ–チヴィタ記号によって与えられる εσ がある。これは X から X への全単射とは限らない任意の写像に対して定義され、全単射でない写像に対しては 0 を割り当てる。 置換の符号は inv(σ) を σ の転倒数とすれば sgn(σ) = (−1)inv(σ) と明示的に書くことができる。 あるいは、置換の符号を置換の互換の積への分解によって定義することもできる。すなわち、置換 σ の互換の積への分解に現れる互換の数を m とするとき、 sgn(σ) = (−1)m (ja)
- Inom matematiken, när X är en ändlig mängd med minst två element, delas permutationerna av X (det vill säga de bijektiva funktionerna från X till X) i två klasser av lika storlek: de jämna permutationerna och de udda permutationerna. Om en linjär ordning av X föreligger så kan pariteten för en permutation σX definieras som antalet inversioner för σ, det vill säga antalet par av element x, y i X sådana att och . En permutations tecken kan explicit uttryckas som sgn(σ) = (−1)N(σ) där inversionstalet N(σ) är antalet inversioner i σ. sgn(σ) = (−1)m (sv)
|
| rdfs:label
|
- زوجية تبديلة (رياضيات) (ar)
- Paritat d'una permutació (ca)
- Znaménko permutace (cs)
- Vorzeichen (Permutation) (de)
- Paridad de una permutación (es)
- Signature d'une permutation (fr)
- 置換の符号 (ja)
- Parity of a permutation (en)
- Paridade de uma permutação (pt)
- Paritet (permutationer) (sv)
- 置换的奇偶性 (zh)
- Парність перестановки (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
