Tingnan ang wikitext ng Permutasyon

[[Talaksan:Permutations RGB.svg|thumb|120 px|Ang bawat isa sa anim na hilera ay ibang permutasyon ng tatlong natatanging bola]]
Sa [[matematika]], ang '''permutasyon''' o '''pamalitan'''<ref>{{Maugnayin|pámálitan}}</ref> ng isang [[Pangkat (matematika)|pangkat]], sa malawak na kahulugan, ay ang pagkakalagay ng mga miyembro nito sa isang sunud-sunod o linear na order, o kung ang pangkat ay mayroon nang order, ito ay ang pagsasaayos muli ng mga elemento nito. Ang salitang "permutasyon" ay tumutukoy din sa gawain o proseso ng pagbabago ng linear na order ng isang nakaayos na pangkat.<ref>{{harvtxt|Webster|1969}}</ref>

Ang mga permutasyon ay naiiba sa mga [[kumbinasyon]], na mga seleksyon ng ilang miyembro ng isang pangkat anuman ang pagkakasunud-sunod nito. Halimbawa, kung isusulat bilang mga tuple, mayroong anim na permutasyon ang pangkat na {1, 2, 3}, ito ay (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), at (3, 2, 1). Ang lahat ng ito ay ang posibleng pagkakasunud-sunod ng tatlong elemento ng pangkat. Ang mga [[anagram]] ng mga salitang may magkakaibang titik ay permutasyon din: nakaayos na ang mga titik ng orihinal na salita, at ang anagram ay ang muling pagsasaayos ng mga titik. Ang pag-aaral ng mga permutasyon ng finite sets ay isang mahalagang paksa sa larangan ng [[kombinatorika]] at [[teorya ng grupo]].

Ang mga permutasyon ay ginagamit sa halos bawat sangay ng matematika at marami pang ibang [[larangan ng agham]]. Sa [[agham pangkompyuter]], ginagamit ito para sa pagsusuri ng mga sorting algorithm; sa [[mekanikang quantum]], para sa paglalarawan ng mga estado ng mga [[partikula]]; at sa [[biyolohiya]], para sa paglalarawan ng mga sekwensiyang [[RNA]].

Ang bilang ng mga permutasyon ng {{math|''n''}} na magkakaibang mga bagay ay {{math|''n''}}&nbsp;[[paktoryal]], karaniwang sinusulat bilang {{math|''n''!}}, na nagpapakita ng produkto ng lahat ng mga positibong integers na mas mababa o katumbas ng {{math|''n''}}.

Sa mga teknikal na termino, ipinapaliwanag ang permutasyon ng [[Pangkat (matematika)|pangkat]] {{math|''S''}} bilang [[biyeksyon]] ({{lang-en|bijection}}) mula sa {{math|''S''}} sa sarili. Kumbaga, isang [[Punsiyon (matematika)|punsiyon]] mula sa {{math|''S''}} hanggang sa {{math|''S''}} na kung saan ang bawa't isa ng [[Elemento (matematika)|elemento]] ay nangyayari minsan, at minsan lang, bilang isang halaga ng isang [[Imahe (matematika)|imahe]]. Ito ay may kaugnayan kay pagsasaayos ng mga elemento ng {{math|''S''}} na kung saan ang bawa't isang elemento {{math|''s''}} ay pinapalitan ng kaukulang elemento {{math|''f''(''s'')}}. Halimbawa, ang permutasyon (3, 1, 2) na dating nagsasabi ay inilalarawan ng punsiyon <math>\alpha</math> na ipinapaliwanag bilang

: <math>\alpha(1) = 3, \quad \alpha(2) = 1, \quad \alpha(3) = 2</math>.

Ang koleksyon ng lahat na permutasyon ng isang pangkat ay bumubuo ng isang [[Grupo (matematika)|grupo]] na tinatawag na [[simetrikong grupo]] ({{lang-en|symmetric group}}) ng pangkat. Ang operasyon pangrupo ay komposisyon (dalawang sunod-sunod na pagsasaayos) na nauuwi ng ibang pagsasaayos. Dahil hindi nagdedepende, ang mga propyedad ng mga permutasyon, ng ugali ng mga elemento ng pangkat, madalas na iniisip ng mga permutasyon ng pangkat <math>\{1, 2, \ldots, n\}</math> para sa pag-aaral ng mga permutasyon.

Sa kombinatorikong basal, ang mga {{math|''k''}}-permutasyon, o mga [[parsiyal na permutasyon]], ay mga pagsasaayos ng mga {{math|''k''}} elemento na pinipili mula sa pangkat. Kapag {{math|''k''}} ay katumbas ng laki ng pangkat, ang mga ito ay mga permutasyon ng pangkat.

[[Image:Rubik's cube.svg|thumb|Sa popular na [[palaisipan]] ng [[kubo ni Rubik]], na inimbento noong 1974 ni [[Ernő Rubik]], bawa't isang pagbaling ng mga harap ng palaisipan ay lumilikha ng permutasyon ng mga kulay ng ibabaw.]]

== Kasaysayan ==

Ang isang uri ng permutasyon, na tinatawag na [[heksagram]], ay ginamit sa [[I Ching]] ([[Pinyin]]: Yi Jing) kasing maaga ng 1000 BK.

Sa [[sinaunang Gresya|Gresya]], sinulat ni [[Plutarko]] na nadiskubre ni [[Henokrates]] ({{lang-en|Xenocrates}}, {{lang-el|Ξενοκράτης}}) ng [[Kalsedonya]] ({{lang-en|Chalcedon}}, {{lang-el|Χαλκηδών}}) ang dami ng mga posibleng [[pantig]] nasa [[Wikang Sinaunang Griyego|wikang Griyego]]. Ito ay unang tangka na sinusulat para lutasin ang mahirap na problema sa mga permutasyon at mga kumbinasyon.<ref>{{Cite book |last=Heath |first=Thomas Little, Sir |url=https://www.worldcat.org/oclc/7703465 |title=A history of Greek mathematics |date=1981 |publisher=Dover Publications |isbn=0-486-24073-8 |location=New York |oclc=7703465}}</ref>

Sinulat ni [[Al-Khalil]], [[Mga Arabe|Arabeng]] [[matematiko]] at [[kriptograpo]], ang ''Aklat ng mga Kriptograpikong Mensahe''. Sinasaklaw ang unang paggamit ng mga permutasyon at mga kumbinasyon, para sa itala ang lahat ng mga posibleng [[Wikang Arabe|Arabeng]] salita na walang mga [[patinig]].<ref name="LB">{{cite journal|last=Broemeling|first=Lyle D.|title=An Account of Early Statistical Inference in Arab Cryptology|journal=The American Statistician|date=1 November 2011|volume=65|issue=4|pages=255–257|doi=10.1198/tas.2011.10191|s2cid=123537702}}</ref>

Inalam ang paraan para tumiyak ng dami ng mga permutasyon ng ''n'' bagay sa kulturang [[Indiya]]no noong 1150 AD. Sumasaklaw ang ''Lilavati'' ni matematiko Indiyano Bhaskara II ng pangungusap na isinasalin ganyan:

:Ang bunga ng [[Pagpaparami (matematika)|pagpaparami]] ng mga [[Aritmetikong serye|aritmetikong]] [[Serye (matematika)|serye]], na nagsisimula sa pagkakaisa [i.e. 1] at nagpapatuloy sa dami ng lugar [''n''], ay mga baryasyon ng bilang [''n''!] na may mga espesipikong tuos.<ref>{{cite journal |first=N. L. |last=Biggs |title=The Roots of Combinatorics |journal=Historia Math. |volume=6 |year=1979 |issue=2 |pages=109–136 |doi=10.1016/0315-0860(79)90074-0 |doi-access=free }}</ref>

Noong 1677, inilarawan ni [[Fabian Stedman]] ang mga paktoryal pagpaliwanag ng dami ng mga permutasyon ng mga [[kampana]] sa ''change ringing''. Nagsisimula siya sa dalawang kampana at sumulat: "muna, umamin na ang ''dalawa'' ay iniiba sa dalawang paraan" at inilalarawan ito sa 1 2 at 2 1 (kumbaga, 2! = 2).{{sfn|Stedman|1677|p=4}} Ipinapaliwanag pagkatapos na kung may tatlong kampana may "tatlo pinarami nang dalawang beses na tuos na ginagawa mula sa [bilang] tatlo" na inilalarawan ulit. Ayon sa kaniyang paliwanag, "magtapon 3, at matitira 1 2; magtapon 2, at matitira 1 3; magtapon 1, at matitira 2 3" (kumbaga, 3! = 3 x 2!).{{sfn|Stedman|1677|p=5}} Pagkatapos umaabante sa apat na kampana at inuulit ang katwiran ng magtapon para ipakita na may apat na pangkat ng tatlo (kumbaga, 4! = 4 x 3!).{{sfn|Stedman|1677|pp=6—7}} Talaga, ito ay [[rekursibo]]ng proseso. Umaabante sa limang kampana sa pamamagitan ng paraan ng magtapon at itinatala ang 120 kumbinasyon. Sa puntong ito niyang isinusuko at nasasabi:

:Ngayon ang ugali ng itong mga paraan ay nangangahulugan, na pagbabago sa isang bilang ay sumasaklaw* ng mga pagbabago sa mas mababang mga bilang, [...] kaya ang buong dagundong ng pagbabago sa isang bilang ay kamukha ng unyon ng buong mga dagundong ng lahat ng mga mababang mga bilang sa buong katawan.{{sfn|Stedman|1677|p=8}}

(* Ginamit niya ang salita ''comprehends'', sa lumang muwang ng "sumaklaw ng lahat", isang literal na [[pagsasalin]] mula sa [[Latin]].)

Lumawak si Stedman ng konsiderasyon ng mga permutasyon sa mga [[titik]] ng [[alpabeto]] at mga [[kabayo]] nasa [[kuwadra]] na may 20.{{sfn|Stedman|1677|pp=13—18}}

Sa paligid ng 1770 nangyari ang kaso na kung saan sinuri ang ilang mga matematikong tanong, tila walang kaugnayan. Habang pag-aaral ng mga [[ekwasyong polinomial]], pinansin ni [[Joseph Louis Lagrange]] na ang mga proiyedad ng mga permutasyon ng mga [[Ugat (matematika)|ugat]] ng isang [[ekwasyon]] ay kaugnay sa mga posibilidad para malutas nitong ekwasyon. Nauwi ang itong trabaho, ''via'' trabaho ni [[Évariste Galois]], sa [[teorya ni Galois]], na lubos na inilalarawan ang posible at imposible tungkol sa kalutasan ng mga ekwasyong polinomial (na may isang hindi alam) sa pamagitan ng mga radikal. Nasa modernong matematika, may maraming katulad na sitwasyon na kung saan pagkakaintindi ng isang problema ay nangangailangan ng pag-aaral ng ilang mga permutasyong kaukulan.

Napakahahalaga ang mga permutasyon sa [[kriptanalisis ng Enigma]], isang kagamitan na ginamit ng [[Alemanyang Nazi]] habang [[Ikalawang Digmaang Pandaigdig]]. Lalo na, isang mahalagang propyedad ng mga permutasyon, na ang dalawang permutasyon ay konhugado ({{lang-en|conjugate}}) kapag mayroon ng parehong uri ng siklo, ginamit ni kriptologo Marian Rejewski para sumira ng [[sipero]]ng Enigma noong 1932–1933.<ref>{{Cite journal |last=Rejewski |first=Marian |date=1980 |title=An application of the theory of permutations in breaking the Enigma cipher |url=https://eudml.org/doc/264403 |journal=Applicationes Mathematicae |volume=16 |issue=4 |pages=543–559 |doi=10.4064/am-16-4-543-559 |issn=1233-7234}}</ref><ref>{{Cite web |last=Cash |first=David |date=2019 |title=CMSC 28400 Introduction to Cryptography Autumn 2019 - Notes #2: Permutations and Enigma |url=https://people.cs.uchicago.edu/~davidcash/284-autumn-19/02-permutations-and-enigma.pdf}}</ref>

== Mga permutasyon na walang repetisyon ==

Ang pinakasimpleng halimbawa ng permutasyon ay permutasyon na walang repetisyon. Dito iniisip natin ang dami ng mga posibleng paraan para ayusin {{mvar|n}} items sa {{mvar|n}} lugar. Mayroon ang paktoryal ng espesyal na aplikasyon para ipaliwanag ang dami ng mga permutasyon sa isang pangkat na hindi sumasaklaw ng mga repetisyon. Ang bilang n!, na binabasa "n paktoryal", ay tamang-tamang dami ng paraan para ayusin n bagay sa bagong pagsasaayos. Halimbawa, kung may tatlong prutas (isang dalandan, isang mansanas, at isang peras), puwedeng tayong kumain nila sa pagsasaayos na sinabi, o sa ibang pagsasaayos (halimbawa, ng mansanas, ng peras, pagkatapos ng dalandan). Tamang-tamang dami ng permutasyon <math>3! = 1 \cdot 2 \cdot 3 = 6</math>. Dumadami ang n! mas mabilis na mabilis habang dumadami n.

Sa katulad ng paraan, ang dami ng pagsasaayos ng k gamit mula sa n bagay ay minsan na tinatawag na ''parsiyal na permutasyon'' o ''k-permutasyon''. Puwedeng sulatin bilang <math>nPk</math> at ay katumbas ng bilang <math>n (n-1) \cdots (n - k + 1)</math> (na rin sinusulat bilang {{nowrap|<math>n! / (n-k)!</math>}}).

== Katuturan ==

== Mga notasyon ==

Sa mga tekstong matematika nakaugalian ang mangahulugan ng mga permutasyon maliliit na [[Alpabetong Griyego|Griyegong titik]]. Karaniwang ginagamit ang <math>\alpha</math> at <math>\beta</math>, o <math>\sigma, \tau</math> at <math>\pi</math>.

Dahil sa sulatin ang mga permutasyon ayon sa mga elemento, kumbaga, bilang mga punsiyon sa mga bahagi, ay mahirap, inimbento ang iba-ibang notasyon para mas siksik na katawanin sila. Ang notasyong sikliko ay popular na pagpili para sa maraming matematiko, dahil sa siksik na hitsura at dahil sa katotohanan na ipinapaliwanag ang istruktura ng isang permutasyon. Ito ay notasyon na ginagamit sa itong artikulo, maliban kung iba ang nakasaad, pero ibang mga notasyon ay ginagamit pa, lalo sa espesipikong mga aplikasyon.

=== Notasyon sa dalawang linya ===

Sa ''notasyon sa dalawang linya'' ni [[Augustin-Louis Cauchy|Cauchy]], inililista ang mga elemento ng ''S'' sa unang hilera, at kaukulang imahe sa pangalawang hilera. Halimbawa, nasusulat ang partikular na permutasyon ng pangkat ''S'' = {1, 2, 3, 4, 5} ganyan:

: <math>\sigma = \begin{pmatrix}
  1 & 2 & 3 & 4 & 5 \\
  2 & 5 & 4 & 3 & 1
\end{pmatrix};</math>

ito ay nangangahulugan na ginaganap ng ''σ'' ang {{math|''σ''(1) {{=}} 2}}, {{math|''σ''(2) {{=}} 5}}, {{math|''σ''(3) {{=}} 4}}, {{math|''σ''(4) {{=}} 3}}, at {{math|''σ''(5) {{=}} 1}}. Maaaring magpakita sa anumang pagsasaayos ang mga elemento ng ''S''. At saka nasusulat itong permutasyon ganyan:

: <math>\sigma = \begin{pmatrix}
  3 & 2 & 5 & 1 & 4 \\
  4 & 5 & 1 & 2 & 3
\end{pmatrix},</math>
o
: <math>\sigma = \begin{pmatrix}
  5 & 1 & 4 & 3 & 2 \\
  1 & 2 & 3 & 4 & 5
\end{pmatrix}.</math>

=== Notasyon sa isang linya ===

Kung may "natural" na pagsasaayos para sa mga elemento ng ''S''{{efn|Ang pagsasaayos ay madalas na implisito na naiintindihan. Halimbawa, ang pangkat ng mga [[buumbilang]] ay natural na sinusulat mula sa pinakamaliit hanggang sa pinakamalaki, yamang ang pangkat ng mga [[titik]] ay sinusulat sa [[leksikograpiko]]ng pagsasaayos. Para sa ibang mga pangkat, kailangang eksplisito na tukuyin ang natural na pagsasaayos.}}, halimbawa <math>x_1, x_2, \ldots, x_n</math>, pagkatapos ginagamit ito para sa unang hilera ng notasyon sa dalawang linya:

: <math>\sigma = \begin{pmatrix}
  x_1         & x_2         & x_3         & \cdots & x_n \\
  \sigma(x_1) & \sigma(x_2) & \sigma(x_3) & \cdots & \sigma(x_n)
\end{pmatrix}.</math>

Nangangahulugan itong palagay na maaaring itapon ang unang hilera at sulatin ang permutasyon sa ''notasyon sa isang linya'' ganyan:

: <math>(\sigma(x_1) \; \sigma(x_2) \; \sigma(x_3) \; \cdots \; \sigma(x_n)) </math>,

kumbaga, bilang pagsasaayos ng mga elemento ng ''S''. Dapat mag-ingat para itangi ang notasyon sa isang linya mula sa notasyong sikliko na inilalarawan sa ilalim. Sa panitikan ng matematika, karaniwan ang ligta ng mga [[panaklong]] mula sa notasyon sa isang linya, at ang paggamit para sa notasyong sikliko. Ang notasyon sa isang linya tinatawag din na ''representasyon [[Salita (matematika)|pasalita]]'' ({{lang-en|word representation}}) ng isang permutasyon. Kaya halimbawa sa itaas ay {{nowrap|2 5 4 3 1}} dahil sa ang natural na pagsasaayos {{nowrap|1 2 3 4 5}} ay ipinalalagay para sa unang hilera. (Karaniwan ang mga kuwit para sa maghiwalay ng mga bilang lang kung mayroon ang ibang mga bilang ng dalawang o mas karakter.) Mas siksik ang itong porma, at karaniwan sa basal na [[kombinatorika]] at [[agham pangkompyuter]]. Lalo na kapaki-pakinabang ito sa mga aplikasyon kung saan mga elemento ng ''S'' o mga permutasyon ay ikinukumpara bilang mas malaki o mas maliit.

=== Notasyong sikliko ===

Inilalarawan ng notasyong sikliko ang bunga ng permutasyon na inuulit sa mga elemento ng pangkat. Ipinahahayag ang permutasyon bilang bunga ng mga [[Permutasyong sikliko|siklo]].

Para sulatin ang permutaayon ng <math>\sigma</math> sa notasyong sikliko, magpatuloy ganyan:

# Sulatin ang inisyal na [[panaklong]], pagkatapos piliin at sulatin ang arbitraryong elemento <math>x</math> ng <math>S</math>: <math>(\,x</math>
# Bakasin ang landas ng <math>x</math>, kumbaga, sulatin ang mga dami sa ilalim ng sunud-sunod na aplikasyon ng <math>\sigma</math>: <math>(\,x\,\sigma(x)\,\sigma(\sigma(x))\,\ldots</math>
# Ulitin hanggang ang dami ay bumabalik sa <math>x</math> at sulatin ang pinal na panaklong imbes na <math>x</math>: <math>(\,x\,\sigma(x)\,\sigma(\sigma(x))\,\ldots\,)</math>
# Ulitin ito sa ibang mga elemento ng <math>S</math>, hanggang sinusulat ang lahat ng elemento sa mga siklo.

Kaya ang permutasyon 2 5 4 3 1 (sa notasyon sa isang linya) ay sinusulat bilang (125)(34) sa notasyong sikliko.

Ibang mga tala:
<math display="block">(\,1 \, 2 \, 5\,) (\,3\,4\,) = (\,3 \, 4\,) (\,1 \, 2 \, 5\,).</math>
<math display="block">(\,1 \, 2 \, 5\,) (\,3\,4\,) = (\,5 \, 1 \, 2\,)(\,3 \, 4\,) = (\,2 \, 5 \, 1\,)(\,4 \, 3\,).</math>
<math display="block">[(\,1\,2\,5\,)(\,3\,4\,)]^{-1} = (\,5\,2\,1\,)(\,4\,3\,).</math>

=== Notasyong siklikong kanoniko ===

=== Komposisyon ng mga permutasyon ===

== Ibang mga paggamit ng terminong ''permutasyon'' ==

== Mga propyedad ==

== Mga tala ==
{{notelist}}

== Mga sanggunian ==
{{reflist}}

{{Stub|Matematika}}

[[Kategorya:Mga permutasyon| ]]