thumb|300px|Permutoedrul de ordinul 4 În matematică permutoedrul de ordinul n este un politop (−1)-dimensional conținut într-un spațiu -dimensional. Coordonatele vârfurilor sale (vârfuri etichetate în imaginea din dreapta) sunt permutări ale primelor numere naturale. Laturile identifică cele mai scurte drumuri posibile (ansambluri de transpoziții) care leagă două vârfuri (permutări). Două permutări legate printr-o latură diferă doar în două locuri (o transpunere), iar numerele de pe aceste locuri sunt vecine (diferă ca valoare cu 1).
Imaginea din dreapta arată permutoedrul de ordinul 4, care este octaedrul trunchiat. Vârfurile sale sunt cele 24 de permutări ale lui (1, 2, 3, 4). Laturile paralele au aceeași culoare. Cele 6 culori ale laturilor corespund celor 6 posibile transpoziții a 4 elemente, adică indică în ce două locuri diferă permutările conectate. (De exemplu, latorile roșii conectează permutări care diferă în ultimele două locuri.)
Deși terminația -edru dă impresia că permutoedrul ar fi un poliedru, adică o figură geometrică tridimensională, el este de fapt un politop.
Istoric Conform lui Günter Ziegler, permutoedrele au fost studiate pentru prima dată de Pieter Hendrik Schoute. Googlebook, 370–381 Also online on the KNAW Digital Library at http://www.dwc.knaw.nl/toegangen/digital-library-knaw/?pagetype=publDetail&pId=PU00011495 Numele de permutoèdre a fost inventat de Georges Guilbaud și Pierre Rosenstiehl. Ei descriu cuvântul drept un barbarism, dar ușor de reținut și îl supun criticii cititorilor lor.În original în
Permutoedrele sunt uneori numite politopuri de permutare, dar această terminologie este folosită și pentru politopul Birkhoff, definit ca anvelopa convexă a matricilor permutare. Mai general, Joseph Bowman folosește acest termen pentru orice politop ale cărui vârfuri pot fi puse într-o corespondență biunivocă cu permutările unei mulțimi.
Vârfuri, laturi și fațete , , fațete, Dimensiunea feței .
1 1 14 1 30 150
Permutoedrul de ordinul are vârfuri, fiecare fiind adiacent altor . Numărul laturilor este , iar lungimea lor este .
Două vârfuri conectate diferă prin interschimbarea a două coordonate, ale căror valori diferă cu 1. . Perechea de locuri interschimbate corespunde direcției laturii. (În imaginea de la începutul articolului vârfurile și sunt conectate printr-o latură albastră și diferă prin interschimbarea lui 2 și 3 de pe primele două locuri. Valorile 2 și 3 diferă cu 1. Toate laturile albastre corespund interschimbărilor de coordonate de pe primele două locuri.)
Numărul de fațete este , deoarece acestea corespund unor submulțimi proprii nevide din Vârfurile unei fațete corespunzătoare submulțimii au în comun faptul că coordonatele lor pe locurile din sunt mai mici decât coordonatele din pozițiile care nu sunt în S. , p. 105 (see chapter The Permutahedron).
Exemple de fațeteLa ordinul 3 fațetele sunt cele 6 laturi, iar la ordinul 4 sunt cele 14 fețe. Coordonatele de pe locurile unde sunt marcate cu un fundal întunecat. Se observă că sunt mai mici decât restul. Pătratul de deasupra corespunde submulțimii În cele patru vârfuri ale sale, coordonatele de pe ultimele două locuri au cele mai mici valori (și anume 1 și 2). ordinul 3 ordinul 4 submulțimi de 1-elemente submulțimi de 2-elemente submulțimi de 1-elemente submulțimi de 2-elemente submulțimi de 3-elemente 160px 160px 160px 160px 160px Mai general, fețele de dimensiune 0 (vârfurile) până la (permutoedrul însuși) corespund ordonării slabe stricte a mulțimii Deci numărul tuturor fețelor este al -lea număr ordonat Bell.v. de exemplu , p. 18. O față de dimensiunea corespunde unei ordonări cu clasa de echivalență .
Exemple de fețe ordinul 3 ordinul 4 300px 500px<div style="width: 800px;"> Imaginile de mai sus arată laticele fețelor permutoedrelor de ordinul 3 și 4 (fără fețele vide). Fiecare centru al unei fețe este etichetat cu o ordine slabă strictă. De exemplu. pătratul de deasupra ca 3 4 | 1 2, care reprezintă . Ordonările sunt ordonate parțial prin rafinare, cele mai fine fiind la exterior. Deplasarea de-a lungul unei laturi spre interior înseamnă fuzionarea a două clase de echivalență învecinate.
Etichetele vârfurilor a | b | c | d interpretate drept permutări (a, b, c, d) sunt cele care formează graful Cayley.
Fațete printre fețeFațetele menționate mai sus se numără printre aceste fețe și corespund ordonărilor cu două clase de echivalență. Primul este folosit ca submulțimea atribuită fațetei, deci ordonarea este .
Imaginile de mai jos arată cum fațetele permutoedrului corespund proiecției simpliciale a unui -cub. Etichetele de coordonate binare corespund submulțimilor , de ex. 0011 la (Vârful proiectat spre centru nu corespunde unei fațete. Nici vârful său opus în -cub, care nu face parte din proiecție.) 250px 300px
Numărul de fețe de dimensiunea în permutoedrul de ordin este dat de triunghiul :
cu reprezentând numerele Stirling de tipul al doilea. Este afișat în dreapta împreună cu sumele sale pe rând, numerele Bell ordonate.
Alte proprietăți thumb|300px|Graful Cayley S4 ca permutoedru Permutoedrul este tranzitiv pe vârfuri: Sn acționează asupra permutoedrului prin permutarea coordonatelor.
Permutoedrul este un zonotop; o copie translată a permutoedrului poate fi generată ca a unui număr triunghiular de segmente care conecteaă perechile de vectori ai bazei standard.
Vârfurile și laturile permutoedrului sunt izomorfe cu unul dintre ale grupului simetric, și anume cel prin transpoziții care schimbă elemente consecutive. Vârfurile grafului Cayley sunt permutările inverse ale celor din permutoedru.Această etichetare a grafului Cayley este prezentată, de exemplu, de Imaginea din dreapta arată graful Cayley al lui S4. Culorile laturilor sale reprezintă cele 3 transpoziții generatoare: , , .
Acest graf Cayley este un ciclu Hamiltonian. Un asemenea ciclu poate fi găsit prin algoritmul Steinhaus–Johnson–Trotter.
Teselarea spațiului
Permutoedrul de ordinul n se află în întregime în hiperplanul (n − 1)-dimensional format din toate punctele ale căror coordonate se însumează cu numărul 1 + 2 + ... + n = n(n + 1)/2.
Mai mult decât atât, acest hiperplan poate fi teselat de nenumărate copii translate ale permutoedrului. Fiecare dintre ele diferă de permutoedrul de bază printr-un element dintr-o anumită latice (n − 1)-dimensională, care constă din n-tupluri de numere întregi care se însumează la zero și ale căror resturi modulo n sunt toate egale: x1 + x2 + ... + xn = 0 x1 ≡ x2 ≡ ... ≡ xn (mod n).
Aceaste este laticea , laticea duală a laticei . În alte cuvinte, permutoedrul este pentru . Această latice este uneori numită latice permutoedrică.
Astfel, permutoedrul de ordinul 4 prezentat mai sus teselează spațiul tridimensional prin translație. Aici spațiul tridimensional este subspațiul afin al spațiului cvadridimensional R4 cu coordonatele x, y, z, w care constă din cele 4 tupluri de numere reale a căror sumă este 10, x + y + z + w = 10.
Se verifică cu ușurință că pentru fiecare dintre următorii patru vectori, (1,1,1,−3), (1,1,−3,1), (1,−3,1,1) and (−3,1,1,1), suma coordonatelor este zero și toate coordonatele sunt congruente cu 1 (mod 4). Oricare trei dintre acești vectori generează laticea de translație.
Teselările formate în acest fel din permutoedrele de ordinul 2, 3 și 4 sunt apeirogonul, pavarea hexagonală regulată și fagurele cubic bitrunchiat. Teselările duale au toate fațetele simplexuri, deși dincolo de ordinul 3 nu sunt politopuri regulate.
Exemple Ordinr 2 Ordin 3 Ordin 4 Ordin 5 Ordin 6 2 vârfuri 6 vârfuri 24 vârfuri 120 vârfuri 720 vârfuri 160px 160px 160px 160px 160px segment hexagon octaedru trunchiat 5-celule omnitrunchiat 5-simplex omnitrunchiat
Note
Bibliografie
. .
Lectură suplimentară .
Legături externe
Categorie:Politopuri Categorie:Permutări