Пермутација (математика) — разлика између измена

Садржај обрисан Садржај додат
м r2.5.4) (Робот мења: am:ሰልፍ
Autobot (разговор | доприноси)
м Разне исправке
Ред 19:
Ако -{''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
Линија 36 ⟶ 39:
Као и у претходном случају, ово неформално може да се покаже посматрањем конструкције произвољне пермутације, али у овом случају се поступак зауставља када се достигне дужина ''r'' .   Број тада достигнутих пермутација износи:
:''P''(''n'', ''r'') = ''n'' × (''n'' − 1) × (''n'' − 2) × ... × (''n'' − ''r'' + 1).
 
Па је:
:''n''! = ''n'' × (''n'' − 1) × (''n'' − 2) × ... × 2 × 1
Линија 41 ⟶ 45:
:     = ''P''(''n'', ''r'') × (''n'' − ''r'') × ... × 2 × 1
:     = ''P''(''n'', ''r'') × (''n'' − ''r'')!.
 
Али ако је ''n''! = ''P''(''n'', ''r'') × (''n'' − ''r'')!, онда ''P''(''n'', ''r'') = ''n''! / (''n'' − ''r'')!.
 
Линија 72 ⟶ 77:
== Нотација ==
Постоје две главне нотације за пермутације.
 
У релационој нотацији довољно је само исписати ''природно'' уређење елемената који се пермутују у првом реду, а ново уређење у другом реду (први пример доле):
: <math>\begin{pmatrix}
Линија 81 ⟶ 87:
 
Алтернативно, пермутација може да се представи начином на који елементи мењају места када се пермутација примењује редом. Ово се назива ''декомпозицијом пермутације у производ дисјунктних [[циклус (математика)|циклуса]]''. користи се [[циклична нотација]] (задња три примера горе). Пермутација се записује на следећи начин: крене се од неког елемента ''x'', и записује се низ (''x'' ''s''(''x'') ''s''<sup>2</sup>(''x'') …) све док се опет не јави почетни елемент (који се не записује поново већ се затварају заграде).
 
Затим се узме неки елемент који није још искоришћен и започне следећи циклус, и тако све док има елемената. У горњем примеру се добија: ''s'' = (1 2 5) (3 4).