Movatterモバイル変換

[0]ホーム
URL:

Pumunta sa nilalaman
WikipediaAng Malayang Ensiklopedya
Hanapin

Permutasyon

Mula sa Wikipedia, ang malayang ensiklopedya
Ang bawat isa sa anim na hilera ay ibang permutasyon ng tatlong natatanging bola

Samatematika, angpermutasyon opamalitan[1] ng isangpangkat, 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.[2]

Ang mga permutasyon ay naiiba sa mgakumbinasyon, 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 mgaanagram 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 ngkombinatorika atteorya ng grupo.

Ang mga permutasyon ay ginagamit sa halos bawat sangay ng matematika at marami pang ibanglarangan ng agham. Saagham pangkompyuter, ginagamit ito para sa pagsusuri ng mga sorting algorithm; samekanikang quantum, para sa paglalarawan ng mga estado ng mgapartikula; at sabiyolohiya, para sa paglalarawan ng mga sekwensiyangRNA.

Ang bilang ng mga permutasyon ngn na magkakaibang mga bagay ayn paktoryal, karaniwang sinusulat bilangn!, na nagpapakita ng produkto ng lahat ng mga positibong integers na mas mababa o katumbas ngn.

Sa mga teknikal na termino, ipinapaliwanag ang permutasyon ngpangkatS bilangbiyeksyon (English:bijection) mula saS sa sarili. Kumbaga, isangpunsiyon mula saS hanggang saS na kung saan ang bawa't isa ngelemento ay nangyayari minsan, at minsan lang, bilang isang halaga ng isangimahe. Ito ay may kaugnayan kay pagsasaayos ng mga elemento ngS na kung saan ang bawa't isang elementos ay pinapalitan ng kaukulang elementof(s). Halimbawa, ang permutasyon (3, 1, 2) na dating nagsasabi ay inilalarawan ng punsiyonα{\displaystyle \alpha } na ipinapaliwanag bilang

α(1)=3,α(2)=1,α(3)=2{\displaystyle \alpha (1)=3,\quad \alpha (2)=1,\quad \alpha (3)=2}.

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

Sa kombinatorikong basal, ang mgak-permutasyon, o mgaparsiyal na permutasyon, ay mga pagsasaayos ng mgak elemento na pinipili mula sa pangkat. Kapagk ay katumbas ng laki ng pangkat, ang mga ito ay mga permutasyon ng pangkat.

Sa popular napalaisipan ngkubo ni Rubik, na inimbento noong 1974 niErnő Rubik, bawa't isang pagbaling ng mga harap ng palaisipan ay lumilikha ng permutasyon ng mga kulay ng ibabaw.

Kasaysayan

[baguhin |baguhin ang wikitext]

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

SaGresya, sinulat niPlutarko na nadiskubre niHenokrates (English:Xenocrates,Greek:Ξενοκράτης) ngKalsedonya (English:Chalcedon,Greek:Χαλκηδών) ang dami ng mga posiblengpantig nasawikang Griyego. Ito ay unang tangka na sinusulat para lutasin ang mahirap na problema sa mga permutasyon at mga kumbinasyon.[3]

Sinulat niAl-Khalil,Arabengmatematiko atkriptograpo, angAklat ng mga Kriptograpikong Mensahe. Sinasaklaw ang unang paggamit ng mga permutasyon at mga kumbinasyon, para sa itala ang lahat ng mga posiblengArabeng salita na walang mgapatinig.[4]

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

Ang bunga ngpagpaparami ng mgaaritmetikongserye, 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.[5]

Noong 1677, inilarawan niFabian Stedman ang mga paktoryal pagpaliwanag ng dami ng mga permutasyon ng mgakampana sachange ringing. Nagsisimula siya sa dalawang kampana at sumulat: "muna, umamin na angdalawa ay iniiba sa dalawang paraan" at inilalarawan ito sa 1 2 at 2 1 (kumbaga, 2! = 2).[6] 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!).[7] 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!).[8] Talaga, ito ayrekursibong 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.[9]

(* Ginamit niya ang salitacomprehends, sa lumang muwang ng "sumaklaw ng lahat", isang literal napagsasalin mula saLatin.)

Lumawak si Stedman ng konsiderasyon ng mga permutasyon sa mgatitik ngalpabeto at mgakabayo nasakuwadra na may 20.[10]

Sa paligid ng 1770 nangyari ang kaso na kung saan sinuri ang ilang mga matematikong tanong, tila walang kaugnayan. Habang pag-aaral ng mgaekwasyong polinomial, pinansin niJoseph Louis Lagrange na ang mga proiyedad ng mga permutasyon ng mgaugat ng isangekwasyon ay kaugnay sa mga posibilidad para malutas nitong ekwasyon. Nauwi ang itong trabaho,via trabaho niÉvariste Galois, sateorya 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 sakriptanalisis ng Enigma, isang kagamitan na ginamit ngAlemanyang Nazi habangIkalawang Digmaang Pandaigdig. Lalo na, isang mahalagang propyedad ng mga permutasyon, na ang dalawang permutasyon ay konhugado (English:conjugate) kapag mayroon ng parehong uri ng siklo, ginamit ni kriptologo Marian Rejewski para sumira ngsiperong Enigma noong 1932–1933.[11][12]

Mga permutasyon na walang repetisyon

[baguhin |baguhin ang wikitext]

Ang pinakasimpleng halimbawa ng permutasyon ay permutasyon na walang repetisyon. Dito iniisip natin ang dami ng mga posibleng paraan para ayusinn items san 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 permutasyon3!=1⋅2⋅3=6{\displaystyle 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 naparsiyal na permutasyon ok-permutasyon. Puwedeng sulatin bilangnPk{\displaystyle nPk} at ay katumbas ng bilangn(n−1)⋯(n−k+1){\displaystyle n(n-1)\cdots (n-k+1)} (na rin sinusulat bilangn!/(n−k)!{\displaystyle n!/(n-k)!}).

Katuturan

[baguhin |baguhin ang wikitext]

Mga notasyon

[baguhin |baguhin ang wikitext]

Sa mga tekstong matematika nakaugalian ang mangahulugan ng mga permutasyon maliliit naGriyegong titik. Karaniwang ginagamit angα{\displaystyle \alpha } atβ{\displaystyle \beta }, oσ,τ{\displaystyle \sigma ,\tau } atπ{\displaystyle \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 |baguhin ang wikitext]

Sanotasyon sa dalawang linya niCauchy, inililista ang mga elemento ngS sa unang hilera, at kaukulang imahe sa pangalawang hilera. Halimbawa, nasusulat ang partikular na permutasyon ng pangkatS = {1, 2, 3, 4, 5} ganyan:

σ=(1234525431);{\displaystyle \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 ngS. At saka nasusulat itong permutasyon ganyan:

σ=(3251445123),{\displaystyle \sigma ={\begin{pmatrix}3&2&5&1&4\\4&5&1&2&3\end{pmatrix}},}

o

σ=(5143212345).{\displaystyle \sigma ={\begin{pmatrix}5&1&4&3&2\\1&2&3&4&5\end{pmatrix}}.}

Notasyon sa isang linya

[baguhin |baguhin ang wikitext]

Kung may "natural" na pagsasaayos para sa mga elemento ngS[a], halimbawax1,x2,…,xn{\displaystyle x_{1},x_{2},\ldots ,x_{n}}, pagkatapos ginagamit ito para sa unang hilera ng notasyon sa dalawang linya:

σ=(x1x2x3⋯xnσ(x1)σ(x2)σ(x3)⋯σ(xn)).{\displaystyle \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 sanotasyon sa isang linya ganyan:

(σ(x1)σ(x2)σ(x3)⋯σ(xn)){\displaystyle (\sigma (x_{1})\;\sigma (x_{2})\;\sigma (x_{3})\;\cdots \;\sigma (x_{n}))},

kumbaga, bilang pagsasaayos ng mga elemento ngS. 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 mgapanaklong mula sa notasyon sa isang linya, at ang paggamit para sa notasyong sikliko. Ang notasyon sa isang linya tinatawag din narepresentasyonpasalita (English:word representation) ng isang permutasyon. Kaya halimbawa sa itaas ay2 5 4 3 1 dahil sa ang natural na pagsasaayos1 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 nakombinatorika atagham pangkompyuter. Lalo na kapaki-pakinabang ito sa mga aplikasyon kung saan mga elemento ngS o mga permutasyon ay ikinukumpara bilang mas malaki o mas maliit.

Notasyong sikliko

[baguhin |baguhin ang wikitext]

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

Para sulatin ang permutaayon ngσ{\displaystyle \sigma } sa notasyong sikliko, magpatuloy ganyan:

  1. Sulatin ang inisyal napanaklong, pagkatapos piliin at sulatin ang arbitraryong elementox{\displaystyle x} ngS{\displaystyle S}:(x{\displaystyle (\,x}
  2. Bakasin ang landas ngx{\displaystyle x}, kumbaga, sulatin ang mga dami sa ilalim ng sunud-sunod na aplikasyon ngσ{\displaystyle \sigma }:(xσ(x)σ(σ(x))…{\displaystyle (\,x\,\sigma (x)\,\sigma (\sigma (x))\,\ldots }
  3. Ulitin hanggang ang dami ay bumabalik sax{\displaystyle x} at sulatin ang pinal na panaklong imbes nax{\displaystyle x}:(xσ(x)σ(σ(x))…){\displaystyle (\,x\,\sigma (x)\,\sigma (\sigma (x))\,\ldots \,)}
  4. Ulitin ito sa ibang mga elemento ngS{\displaystyle 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:(125)(34)=(34)(125).{\displaystyle (\,1\,2\,5\,)(\,3\,4\,)=(\,3\,4\,)(\,1\,2\,5\,).}(125)(34)=(512)(34)=(251)(43).{\displaystyle (\,1\,2\,5\,)(\,3\,4\,)=(\,5\,1\,2\,)(\,3\,4\,)=(\,2\,5\,1\,)(\,4\,3\,).}[(125)(34)]−1=(521)(43).{\displaystyle [(\,1\,2\,5\,)(\,3\,4\,)]^{-1}=(\,5\,2\,1\,)(\,4\,3\,).}

Notasyong siklikong kanoniko

[baguhin |baguhin ang wikitext]

Komposisyon ng mga permutasyon

[baguhin |baguhin ang wikitext]

Ibang mga paggamit ng terminongpermutasyon

[baguhin |baguhin ang wikitext]

Mga propyedad

[baguhin |baguhin ang wikitext]

Mga tala

[baguhin |baguhin ang wikitext]
  1. ↑Ang pagsasaayos ay madalas na implisito na naiintindihan. Halimbawa, ang pangkat ng mgabuumbilang ay natural na sinusulat mula sa pinakamaliit hanggang sa pinakamalaki, yamang ang pangkat ng mgatitik ay sinusulat saleksikograpikong pagsasaayos. Para sa ibang mga pangkat, kailangang eksplisito na tukuyin ang natural na pagsasaayos.

Mga sanggunian

[baguhin |baguhin ang wikitext]
  1. ↑"pámálitan":Del Rosario, Gonsalo (1969). Salcedo, Juan (pat.).Maugnaying Talasalitaang Pang-agham Ingles-Pilipino (sa wikang Filipino). Maynila, Pilipinas: Lupon sa Agham. p. {{{pahina}}}.
  2. ↑Webster (1969)
  3. ↑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)
  4. ↑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.
  5. ↑Biggs, N. L. (1979)."The Roots of Combinatorics".Historia Math.6 (2): 109–136.doi:10.1016/0315-0860(79)90074-0.
  6. ↑Stedman 1677, p. 4. harv error: no target: CITEREFStedman1677 (help)
  7. ↑Stedman 1677, p. 5. harv error: no target: CITEREFStedman1677 (help)
  8. ↑Stedman 1677, pp. 6–7. harv error: no target: CITEREFStedman1677 (help)
  9. ↑Stedman 1677, p. 8. harv error: no target: CITEREFStedman1677 (help)
  10. ↑Stedman 1677, pp. 13–18. harv error: no target: CITEREFStedman1677 (help)
  11. ↑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.
  12. ↑Cash, David (2019)."CMSC 28400 Introduction to Cryptography Autumn 2019 - Notes #2: Permutations and Enigma"(PDF).

MatematikaAng lathalaing ito na tungkol saMatematika ay isangusbong. Makatutulong ka saWikipedia sapagpapalawig nito.

Kinuha sa "https://tl.wikipedia.org/w/index.php?title=Permutasyon&oldid=2149452"
Mga kategorya:
Mga nakatagong kategorya:
[8]ページ先頭
©2009-2025 Movatter.jp