Пермутација

Из Википедије, слободне енциклопедије

У неколико области математике, израз пермутација се користи у различитим али блиско повезаним значењима. Сва ова значења се тичу појма пресликавања елемената скупа у друге елементе скупа, то јест, замене места (пермутовања) елемената скупа.

Дефиниције[уреди]

Општи појам пермутације може да се дефинише формалније у различитим контекстима:

У комбинаторици[уреди]

У комбинаторици, пермутација се обично схвата као низ који садржи сваки елемент датог коначног скупа једном и само једном. Појам низа се разликује од појма скупа, по томе што се елементи низа јављају по неком реду: низ има први елемент (осим ако је празан), други елемент (осим ако му је дужина мања од 2), и тако даље. Са друге стране, елементи скупа немају уређење; {1, 2, 3} и {3, 2, 1} су само различити начини да се означи исти скуп.

Међутим, у комбинаторици постоји и традиционално, општије значење израза пермутација. У овом општијем смислу, пермутације су они низови код којих се сваки елемент појављује највише једном, али не морају сви елементи из датог скупа да буду искоришћени.

За више података о сродном појму у коме уређење изабраних елемената из скупа није од значаја, видети чланак комбинација.

У теорији група[уреди]

У теорији група и сродним областима, елементи пермутације нису поређани у линеарном уређењу, или у било ком другом уређењу. По овој дефиницији, пермутација је бијекција из коначног скупа у самог себе. Ово омогућава дефинисање група пермутација; видети чланак група пермутација.

Пребројавање пермутација[уреди]

У овом одељку се користи традиционална дефиниција из комбинаторике, по којој је пермутација уређени низ елемената изабраних из датог коначног скупа, без понављања, и не нужно коришћењем свих елемената датог скупа. На пример, за дати скуп слова {АВРАТ}, неке пермутације су ВРАТ, ВАТА, ВРАТА, ВАТРА и ТРАВА али и АВРАТ – низ не мора да даје неку постојећу реч. Са друге стране, ТАТА, није пермутација јер користи слово Т два пута.

Ако n означава величину скупа – број елемената доступних за избор – а посматрају се једино пермутације које користе свих n елемената, онда је укупан број могућих пермутација једнак n!, где ! означава факторијел. Ово неформално може да се покаже на следећи начин. При конструисању пермутације постоји n могућих избора за први члан низа. Када је први елемент изабран преостало је n − 1 елемената, па за други члан низа има n − 1 могућих избора. За избор прва два елемента имамо скупа

n · (n − 1) могућих пермутација.

За избор трећег члана низа је онда преостало n − 2 елемената, што за прва три члана укупно даје,

n · (n − 1) · (n − 2) могућих пермутација.

Ако се настави на сличан начин док не остану само два елемента, постоје тачно 2 избора, што за n − 1 елемената даје укупан број пермутација једнак:

n · (n − 1) · (n − 2) · ... · 2.

Последњи избор је сада изнуђен, јер је преостао тачно један елемент. Значи укупан број пермутација је

n · (n − 1) · (n − 2) · ... · 2 · 1

(што је исто као и претходни број јер 1 као множилац не прави разлику у резултату). Овај број је, по дефиницији, једнак n!.

У општем случају, број пермутација се означава са P(nr), nPr, или понекад P_n^r, где је:

  • n број елемената доступних за избор, а
  • r је број елемената који се бирају (0 ≤ rn).

За случај када је r = n   је већ показано да је P(n, n) = n!. Општи случај је дат формулом:

 P(n, r) = \frac{n!}{(n-r)!}.

Као и у претходном случају, ово неформално може да се покаже посматрањем конструкције произвољне пермутације, али у овом случају се поступак зауставља када се достигне дужина r .   Број тада достигнутих пермутација износи:

P(n, r) = n × (n − 1) × (n − 2) × ... × (nr + 1).

Па је:

n! = n × (n − 1) × (n − 2) × ... × 2 × 1
     = n × (n − 1) × (n − 2) × ... × (nr + 1) × (nr) × ... × 2 × 1
     = P(n, r) × (nr) × ... × 2 × 1
     = P(n, r) × (nr)!.

Али ако је n! = P(n, r) × (nr)!, онда P(n, r) = n! / (nr)!.

На пример, ако постоји укупно 10, а бира се низ од три елемента из овог скупа, онда је први избор један од 10 елемената, следећи је један од преосталих 9, и коначно један од преосталих 8, што даје 10 × 9 × 8 = 720 пермутација. У овом случају, n = 10 а r = 3. Коришћењем формуле да се израчуна P(10,3), добија се

 P(10,3) = \frac{10!}{(10-3)!} = \frac{10!}{7!} = \frac{7!\times 8 \times 9 \times 10}{7!} = 8 \times 9 \times 10 = 720.

У специјалном случају када је n = r  формула се поједностављује:

 P(n,r) = \frac{n!}{0!} = \frac{n!}{1} = n!.

Разлог зашто је 0! = 1 је тај што је 0! празан производ, који је увек једнак 1.

У примеру са 6 целих бројева {1..6}, ово би било: P(6,6) = 6! / (6−6)! = (1×2×3×4×5×6) / 0! = 720 / 1 = 720.

Пошто је непрактично да се рачуна n! ако је вреднст n  сувише велика, ефикаснији начин је да се рачуна:

P(n, r) = n × (n − 1) × (n − 2) × ... × (nr + 1).

Друге, старије нотације укључују nPr, Pn,r, или nPr. Уобичајена модерна нотација је (n)r што се назива опадајућим факторијелом. Међутим, иста нотација се користи и за растући факторијел.

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

У нотацији растућег факторијела, број пермутација је (nr + 1)r.

Пермутације у теорији група[уреди]

Као што је већ описано, у теорији група израз пермутација (скупа) се користи за бијективно пресликавање (бијекцију) из коначног скупа у самог себе. Претходни пример, прављења пермутација бројева од 1 до 10, би био овде био пресликавање скупа {1, …, 10} у самог себе.

Апстрактније, пермутација може да се сматра филтрацијом (ланцем подскупова): уређење \{0,1,2\} одговара филтрацији \{0\} \subset \{0,1\} \subset \{0,1,2\}. Из тачке гледишта поља са једним елементом, уређење на скупу одговара максималној филтрацији на векторском простору, када се сматра да је скуп векторски простор над пољем са једним елементом; ово повезује својства симетричне групе са својствима алгебарских група.

Нотација[уреди]

Постоје две главне нотације за пермутације.

У релационој нотацији довољно је само исписати природно уређење елемената који се пермутују у првом реду, а ново уређење у другом реду (први пример доле):

\begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\ 
2 & 5 & 4 & 3 & 1\end{pmatrix} = \begin{pmatrix}1 & 2 & 5 \end{pmatrix} \begin{pmatrix}3 & 4 \end{pmatrix} = \begin{pmatrix}3 & 4 \end{pmatrix} \begin{pmatrix}1 & 2 & 5 \end{pmatrix}= \begin{pmatrix}3 & 4 \end{pmatrix} \begin{pmatrix}5 & 1 & 2 \end{pmatrix}

означава пермутацију s скупа {1, 2, 3, 4, 5} дефинисану као s(1)=2, s(2)=5, s(3)=4, s(4)=3, s(5)=1.

Ако је дат коначан скуп E сачињен од n елемената, то је по дефиницији бијекција са скупом {1, …, n}, где ова бијекција f одговара простом ређању елемената. Када су они поређани, могу да се идентификују пермутације на скупу E са пермутацијама на скупу {1, …, n}. (Речено математички, функција која пресликава пермутацију s из E у пермутацију f o s o f-1 of {1,…,n} је морфизам из симетричне групе од E у {1,…,n}, види испод.)

Алтернативно, пермутација може да се представи начином на који елементи мењају места када се пермутација примењује редом. Ово се назива декомпозицијом пермутације у производ дисјунктних циклуса. користи се циклична нотација (задња три примера горе). Пермутација се записује на следећи начин: крене се од неког елемента x, и записује се низ (x s(x) s2(x) …) све док се опет не јави почетни елемент (који се не записује поново већ се затварају заграде).

Затим се узме неки елемент који није још искоришћен и започне следећи циклус, и тако све док има елемената. У горњем примеру се добија: s = (1 2 5) (3 4).

Сваки циклус (x1 x2xL) представља пермутацију која пресликава xi у xi+1 (i=1…L-1) и xL у x1, а остале елементе оставља нетакнутим. L је дужина циклуса. Како ови циклуси по конструкцији имају дисјунктне носаче (то јест понашају се као нетривијално дисјунктни подскупови од E), они комутирају (на пример, (1 2 5) (3 4) = (3 4)(1 2 5)). Редослед цикулса у производу није битан, док је редослед елемената у сваком циклусу битан (до на цикличну промену; види још циклуси и непокретне тачке). Канонски начин за представљање таквих циклуса је да се почне од најмањег елемента у сваком циклусу.

1-циклус (циклус дужине 1) једноставно фиксира елемент који се у њему налази, тако да се такви циклуси обично не записују експлицитно. У неким књигама се циклуси дефинишу тако да искључују циклусе дужине 1.

Циклуси дужине два се називају транспозицијама; такве пермутације просто замењују места двама елементима.

Производ и инверз пермутација[уреди]

Vista-xmag.png За више информација погледајте чланак Симетрична група

Производ две пермутације може да се дефинише на следећи начин. Ако су дате две пермутације, P и Q, примењивање прво P а затим Q би дало исти резултат као и примена само једне неке пермутације, R. Производ пермутација P и Q се тада дефинише као пермутација R. Ако се пермутације посматрају као бијекције, производ двеју пермутација је исто што и њихова композиција када се оне посматрају као функције. Не постоји универзално прихваћена нотација за операцију производа пермутација, и зависности од литературе формула као што је PQ може да буде било PQ било QP. Како је композиција функција асоцијативна, и производ пермутација је асоцијативан: (PQ) ∘ R = P ∘ (QR).

Слично, како бијекције имају инверзе, имају их и пермутације, и PP−1 и P−1P су иденитичне пермутације (види ниже) које остављају све елементе на својим местима. То значи да пермутације образују групу.

Види још[уреди]

Литература[уреди]

  • Miklos Bona. "Combinatorics of Permutations", Chapman Hall-CRC, 2004. ISBN 1-58488-434-7.
  • Donald Knuth. The Art of Computer Programming, Volume 4: Generating All Tuples and Permutations, Fascicle 2, first printing. Addison-Wesley, 2005. ISBN 0-201-85393-0.
  • Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 5.1: Combinatorial Properties of Permutations, pp.11-72.

Спољашње везе[уреди]