Permutasyon

Sa matematika, ang permutasyon ng isang 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.^[1]

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 $n$ na magkakaibang mga bagay ay $n$ paktoryal, karaniwang sinusulat bilang $n!$ , na nagpapakita ng produkto ng lahat ng mga positibong integers na mas mababa o katumbas ng $n$ .

Sa mga teknikal na termino, ipinapaliwanag ang permutasyon ng pangkat $S$ bilang biyeksyon (Ingles: bijection) mula sa $S$ sa sarili. Kumbaga, isang punsiyon mula sa $S$ hanggang sa $S$ na kung saan ang bawa't isa ng elemento ay nangyayari minsan, at minsan lang, bilang isang halaga ng isang imahe. Ito ay may kaugnayan kay pagsasaayos ng mga elemento ng $S$ na kung saan ang bawa't isang elemento $s$ ay pinapalitan ng kaukulang elemento $f (s)$ . Halimbawa, ang permutasyon (3, 1, 2) na dating nagsasabi ay inilalarawan ng punsiyon $\alpha$ na ipinapaliwanag bilang

\alpha (1)=3,\quad \alpha (2)=1,\quad \alpha (3)=2

.

Ang koleksyon ng lahat na permutasyon ng isang pangkat ay bumubuo ng isang grupo na tinatawag na simetrikong grupo (Ingles: 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 $\{1,2,\ldots ,n\}$ para sa pag-aaral ng mga permutasyon.

Sa kombinatorikong basal, ang mga $k$ -permutasyon, o mga parsiyal na permutasyon, ay mga pagsasaayos ng mga $k$ elemento na pinipili mula sa pangkat. Kapag $k$ ay katumbas ng laki ng pangkat, ang mga ito ay mga permutasyon ng pangkat.

Kasaysayan baguhin

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

Sa Gresya, sinulat ni Plutarko na nadiskubre ni Henokrates (Ingles: Xenocrates, Griyego: Ξενοκράτης) ng Kalsedonya (Ingles: Chalcedon, Griyego: Χαλκηδών) ang dami ng mga posibleng pantig nasa wikang Griyego. Ito ay unang tangka na sinusulat para lutasin ang mahirap na problema sa mga permutasyon at mga kumbinasyon.^[2]

Sinulat ni Al-Khalil, 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 Arabeng salita na walang mga patinig.^[3]

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

Ang bunga ng pagpaparami ng mga aritmetikong 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.^[4]

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).^[5] 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!).^[6] 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!).^[7] Talaga, ito ay rekursibong 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.^[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.^[9]

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 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 (Ingles: conjugate) kapag mayroon ng parehong uri ng siklo, ginamit ni kriptologo Marian Rejewski para sumira ng siperong Enigma noong 1932–1933.^[10]^[11]

Mga permutasyon na walang repetisyon baguhin

Ang pinakasimpleng halimbawa ng permutasyon ay permutasyon na walang repetisyon. Dito iniisip natin ang dami ng mga posibleng paraan para ayusin $n$ items sa $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 $3!=1\cdot 2\cdot 3=6$ . 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 $nPk$ at ay katumbas ng bilang $n(n-1)\cdots (n-k+1)$ (na rin sinusulat bilang $n!/(n-k)!$ ).

Katuturan baguhin

Mga notasyon baguhin

Sa mga tekstong matematika nakaugalian ang mangahulugan ng mga permutasyon maliliit na Griyegong titik. Karaniwang ginagamit ang $\alpha$ at $\beta$ , o $\sigma ,\tau$ at $\pi$ .

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 baguhin

Sa notasyon sa dalawang linya ni 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:

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

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

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

o

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

Notasyon sa isang linya baguhin

Kung may "natural" na pagsasaayos para sa mga elemento ng S^[a], halimbawa $x_{1},x_{2},\ldots ,x_{n}$ , pagkatapos ginagamit ito para sa unang hilera ng notasyon sa dalawang linya:

\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}}.

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

(\sigma (x_{1})\;\sigma (x_{2})\;\sigma (x_{3})\;\cdots \;\sigma (x_{n}))

,

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 pasalita (Ingles: word representation) ng isang permutasyon. Kaya halimbawa sa itaas ay 2 5 4 3 1 dahil sa ang natural na pagsasaayos 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 baguhin

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

Para sulatin ang permutaayon ng $\sigma$ sa notasyong sikliko, magpatuloy ganyan:

Sulatin ang inisyal na panaklong, pagkatapos piliin at sulatin ang arbitraryong elemento $x$ ng $S$ : $(\,x$
Bakasin ang landas ng $x$ , kumbaga, sulatin ang mga dami sa ilalim ng sunud-sunod na aplikasyon ng $\sigma$ : $(\,x\,\sigma (x)\,\sigma (\sigma (x))\,\ldots$
Ulitin hanggang ang dami ay bumabalik sa $x$ at sulatin ang pinal na panaklong imbes na $x$ : $(\,x\,\sigma (x)\,\sigma (\sigma (x))\,\ldots \,)$
Ulitin ito sa ibang mga elemento ng $S$ , 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:

(\,1\,2\,5\,)(\,3\,4\,)=(\,3\,4\,)(\,1\,2\,5\,).

(\,1\,2\,5\,)(\,3\,4\,)=(\,5\,1\,2\,)(\,3\,4\,)=(\,2\,5\,1\,)(\,4\,3\,).

[(\,1\,2\,5\,)(\,3\,4\,)]^{-1}=(\,5\,2\,1\,)(\,4\,3\,).

Notasyong siklikong kanoniko baguhin

Komposisyon ng mga permutasyon baguhin

Ibang mga paggamit ng terminong permutasyon baguhin

Mga propyedad baguhin

Mga tala baguhin

↑ 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 leksikograpikong pagsasaayos. Para sa ibang mga pangkat, kailangang eksplisito na tukuyin ang natural na pagsasaayos.

Mga sanggunian baguhin

↑ Webster (1969)
↑ Heath, Thomas Little, Sir (1981). A history of Greek mathematics. New York: Dover Publications. ISBN 0-486-24073-8. OCLC 7703465.{{cite book}}: CS1 maint: multiple names: mga may-akda (link)
↑ Broemeling, Lyle D. (1 November 2011). "An Account of Early Statistical Inference in Arab Cryptology". The American Statistician. 65 (4): 255–257. doi:10.1198/tas.2011.10191. S2CID 123537702.
↑ Biggs, N. L. (1979). "The Roots of Combinatorics". Historia Math. 6 (2): 109–136. doi:10.1016/0315-0860(79)90074-0.
↑ Stedman 1677, p. 4.
↑ Stedman 1677, p. 5.
↑ Stedman 1677, pp. 6—7.
↑ Stedman 1677, p. 8.
↑ Stedman 1677, pp. 13—18.
↑ Rejewski, Marian (1980). "An application of the theory of permutations in breaking the Enigma cipher". Applicationes Mathematicae. 16 (4): 543–559. doi:10.4064/am-16-4-543-559. ISSN 1233-7234.
↑ Cash, David (2019). "CMSC 28400 Introduction to Cryptography Autumn 2019 - Notes #2: Permutations and Enigma" (PDF).

Ang lathalaing ito na tungkol sa Matematika ay isang usbong. Makatutulong ka sa Wikipedia sa pagpapalawig nito.

[12] 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 leksikograpikong pagsasaayos. Para sa ibang mga pangkat, kailangang eksplisito na tukuyin ang natural na pagsasaayos.

[1] Webster (1969)

[2] Heath, Thomas Little, Sir (1981). A history of Greek mathematics. New York: Dover Publications. ISBN 0-486-24073-8. OCLC 7703465.{{cite book}}: CS1 maint: multiple names: mga may-akda (link)

[LB-3] Broemeling, Lyle D. (1 November 2011). "An Account of Early Statistical Inference in Arab Cryptology". The American Statistician. 65 (4): 255–257. doi:10.1198/tas.2011.10191. S2CID 123537702.

[4] Biggs, N. L. (1979). "The Roots of Combinatorics". Historia Math. 6 (2): 109–136. doi:10.1016/0315-0860(79)90074-0.

[FOOTNOTEStedman16774-5] Stedman 1677, p. 4.

[FOOTNOTEStedman16775-6] Stedman 1677, p. 5.

[FOOTNOTEStedman16776—7-7] Stedman 1677, pp. 6—7.

[FOOTNOTEStedman16778-8] Stedman 1677, p. 8.

[FOOTNOTEStedman167713—18-9] Stedman 1677, pp. 13—18.

[10] Rejewski, Marian (1980). "An application of the theory of permutations in breaking the Enigma cipher". Applicationes Mathematicae. 16 (4): 543–559. doi:10.4064/am-16-4-543-559. ISSN 1233-7234.

[11] Cash, David (2019). "CMSC 28400 Introduction to Cryptography Autumn 2019 - Notes #2: Permutations and Enigma" (PDF).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[a]