Пермутација (математика)

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

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

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

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

У комбинаторици, пермутација се обично схвата као низ који садржи сваки елемент датог коначног скупа једном и само једном. Појам низа се разликује од појма скупа, по томе што се елементи низа јављају по неком реду: низ има први елемент (осим ако је празан), други елемент (осим ако му је дужина мања од 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(n, r), _nP_r, или понекад $P_{n}^{r}$ , где је:

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

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

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

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

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

Па је:

n! = n × (n − 1) × (n − 2) × ... × 2 × 1

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

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

= P(n, r) × (n − r)!.

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

На пример, ако постоји укупно 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) × ... × (n − r + 1).

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

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

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

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

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

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

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

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

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

{\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) s²(x) …) све док се опет не јави почетни елемент (који се не записује поново већ се затварају заграде).

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

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

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

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

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

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

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

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

Референце уреди

^ Wussing, Hans (2007), The Genesis of the Abstract Group Concept: A Contribution to the History of the Origin of Abstract Group Theory, Courier Dover Publications, стр. 94, ISBN 9780486458687, „Cauchy used his permutation notation—in which the arrangements are written one below the other and both are enclosed in parentheses—for the first time in 1815.”

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

Bogart, Kenneth P. (1990), Introductory Combinatorics (2nd изд.), Harcourt Brace Jovanovich, ISBN 978-0-15-541576-8
Bóna, Miklós (2004), Combinatorics of Permutations, Chapman Hall-CRC, ISBN 978-1-58488-434-7
Bona, Miklos (2012), Combinatorics of Permutations (2nd изд.), CRC Press, ISBN 978-1-4398-5051-0
Brualdi, Richard A. (2010), Introductory Combinatorics (5th изд.), Prentice-Hall, ISBN 978-0-13-602040-0
Cameron, Peter J. (1994), Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, ISBN 978-0-521-45761-3
Carmichael, Robert D. (1956) [1937], Introduction to the theory of Groups of Finite Order, Dover, ISBN 978-0-486-60300-1
Gerstein, Larry J. (1987), Discrete Mathematics and Algebraic Structures, W.H. Freeman and Co., ISBN 978-0-7167-1804-8
Hall, Marshall, Jr. (1959), The Theory of Groups, MacMillan
Humphreys, J. F. (1996), A course in group theory, Oxford University Press, ISBN 978-0-19-853459-4
Knuth, Donald (1973), Sorting and Searching, The Art of Computer Programming, 3 This book mentions the Lehmer code (without using that name) as a variant C₁,...,C_n of inversion tables in exercise 5.1.1−7 (p. 19), together with two other variants.
Knuth, Donald (2005), Generating All Tuples and Permutations, The Art of Computer Programming, 4, Addison–Wesley, ISBN 978-0-201-85393-3 Fascicle 2, first printing.
McCoy, Neal H. (1968), Introduction To Modern Algebra, Revised Edition, Boston: Allyn and Bacon, LCCN 68015225
Nering, Evar D. (1970), Linear Algebra and Matrix Theory (2nd изд.), New York: Wiley, LCCN 76091646
Rotman, Joseph J. (2002), Advanced Modern Algebra, Prentice-Hall, ISBN 978-0-13-087868-7
Stedman, Fabian (1677), Campanalogia, London The publisher is given as "W.S." who may have been William Smith, possibly acting as agent for the Society of College Youths, to which society the "Dedicatory" is addressed. In quotations the original long "S" has been replaced by a modern short "s".
Biggs, Norman L. (2002), Discrete Mathematics (2nd изд.), Oxford University Press, ISBN 978-0-19-850717-8
Foata, Dominique; Schutzenberger, Marcel-Paul (1970), Théorie Géométrique des Polynômes Eulériens, Lecture Notes in Mathematics, 138, Berlin, Heidelberg: Springer-Verlag, ISBN 978-3-540-04927-2 . The link is to a freely available retyped (LaTeX'ed) and revised version of the text originally published by Springer-Verlag.
Knuth, Donald (1998), Sorting and Searching, The Art of Computer Programming, 3 (Second изд.), Addison–Wesley, ISBN 978-0-201-89685-5 . Section 5.1: Combinatorial Properties of Permutations, pp. 11–72.

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

[1] Wussing, Hans (2007), The Genesis of the Abstract Group Concept: A Contribution to the History of the Origin of Abstract Group Theory, Courier Dover Publications, стр. 94, ISBN 9780486458687, „Cauchy used his permutation notation—in which the arrangements are written one below the other and both are enclosed in parentheses—for the first time in 1815.”

[1]