Kombinatorika

Ang kombinatorika (Ingles: combinatorics) ay isang ng sangay ng matematika na umuukol sa may hangganan o mabibilang na diskretong mga istraktura. Ang mga aspeto ng kombinatorika ay kinabibilangan ng pagbibilang ng mga istraktura ng isang ibinigay na uri at sukat (kombinatorikang enumeratibo) na nagpapasya kapag ang ilang kriterya ay nasasalubong at lumilikha at nagsusuri ng mga obhekto na sumasalubong sa kriterya (gaya ng sa mga disenyong kombinatoryal at teoriyang matroid) na naghahanap ng mga obhektong pinakamalaki, pinakamalaiit o optimal (kombinatorikang ekstremal) at nag-aaral ng mga istrakturang kombinatoryal na lumilitaw sa kontekstong alhebraiko o naglalapat ng mga pamamaraang alhebraiko sa mga problemang kombinatoryal (kombinatorikang alhebraiko). Ang mga problemang kombinatoryal ay lumilitaw sa maraming mga sakop ng purong matematika na ang pinakakilala ang alhebra, teoriya ng probabilidad, topolohiya, at heometriya.^[1] Ang kombinatorika ay marami ring mga aplikasyon sa optimisasyon, agham pangkompyuter, teoriyang ergodiko, at pisikang estadistikal. Maraming mga tanong na kominatoryal ay isinaalang alang sa isolasyon na nagbibigay ng solusyong ad hoc sa isang problema na lumilitaw sa isang kontekstong matematikal. Gayunpaman, sa huli nang ika-20 siglo, ang makapangyarihan at pangkalahatang teoretikal na mga pamamaraan ay binuo na gumagawa sa kominatorika na independiyenteng sangay ng matematika sa sarili nitong karapatan. Ang pinakamatanda at pinaka magagamit na mga bahagi ng kombinatorika ang teoriya ng grapo na mayroon ring maraming mga natural na koneksiyon sa ibang mga sakop. Ang kombinatorika ay kadalasang ginagamit sa agham pangkompyuter upang magkamit ng mga pormula at pagtatantiya sa analisis ng mga alogoritmo.

Mga pakikitungo at pang-ilalim na larangan

Kombinatorikang enumeratibo

Limang mga punong binaryo sa tatlong mga berteks na isang halimbawa ng mga bilang na Catalan.

Ang kombinatorikang enumeratibo ang pinaka klasikong area ng kombinatorika at umuukol sa pagbibilang ng bilang ng ilang mga obhetong kombinatoryal. Bagaman ang pagbibilang ng bilang ng mga elemento sa isang hanay ay medyo malawak na problemang matematikal, marami sa mga problema na lumilitaw sa mga aplikasyon ay may isang relatibong simpleng deskripsiyong kombinatoryal. Ang mga bilang Fibonnaci ang basikong halimbawa ng isang problema sa kombinatorikang enumeratibo. Ang daang labindalawa ay nagbibigay ng isang pinag-asang balangkas para sa pagbibilang ng mga permutasyon, kombinasyon at partisyon.

Kombinatorikang analitiko

Ang Kombinatorikang analitiko ay umuukol sa enumerasyon ng mga istrakturang kombinatoryal gamit ang mga kasangkapan mula sa analisis na kompleks at teoriya ng probabilidad. Salungat sa kombinatorikang enumeratibo na gumagamit ng hayagang pormulang kombinatoryal at mga lumilikhang punsiyon upang ilarawan ang mga resulta, ang kombinatorikang analitiko ay naglalayon na magkamit ng mga pormulang asimptotiko.

Teoriya ng partisyon

Isang planong partisyon.

Ang teoriya ng partisyon ay nag-aaral ng iba't ibang mga problemang enumerasyon at asimptotiko na nauugnay sa mga partisyong intedyer at malapit na kaugnay ng seryeng-q, mga punsiyong espesyal at mga ortogonal na polinomial. Isang orihinal na bahagi ng teoriya ng bilang at analisis, ito ay isinasaalang alang ngayon na bahagi ng kombinatorika o isang independiyenteng larangan. Ito ay nagsasama ng pakikitungong bihektibo at iba't ibang mga kasangkapan sa analisis, analitikong teoriya ng bilang at may mga ugnayan sa mekanikang estadistikal.

Teoriya ng grapo

Grapong Petersen.

Ang mga grapo ang mga basikong obhekto sa kombinatorika. Ang mga tanong ay sumasaklaw mula pagbibilang (e.g. ang bilang ng mga grapo sa mga berteks na n na may mga gilid na k) hanggang sa istraktural (e.g. anong mga grapo ang naglalaman ng mga siklong Hamiltonian hanggang sa mga tanong na alhebraiko (e.g. sa ibinigay na grapong G at dalawang mga bilang na x at y, ang polinomial na Tutte na T_G(x,y) ba ay may interpretasyong kombinatoryal?). Bagaman may mga napakalakas na koneksiyon sa pagitan ng teoriya ng grapo at kombinatorika, ang dalawang ito ay minsang inaakala na magkahiwalay na mga paksa.^[2]

Teoriyang disenyo

Ang teoriyang disenyo ang pag-aaral ng mga disenyong kombinatoryal na mga koleksiyon ng mga pang-ilalim na hanay na may ilang mga katangiang interseksiyon ng hanay. Ang mga disenyong bloke ay mga disenyong kombinatoryal ng isang uring espesyal. Ang sakop na ito ang pinakamatandang mga bahagi ng kombinatorika gaya ng problemang babaeng estudyante ni Kirkman na iminungkahi noong 1850. Ang solusyon sa problema ay isang espesyal na kaso ng isang sistemang Steiner na mga sistemang gumagampan ng isang mahalagang papel sa klasipikasyon ng may hangganang simpleng mga grupo. Ang sakop na ito ay may karagdagang mga koneksiyon sa teoriya ng pagkokodigo at kombinatorikang heometriko.

Heometriyang may hangganan

Ang heometriyang may hangganan ang pag-aaral ng mga sistemang heometiko na tanging may isang hangganang bilang ng mga punto. Ang mga istraktura ay analogoso sa mga matatagpuan sa tuloy tuloy na heometriya (planong Euclidian), tunay na prohektibong espasyo, etc) ngunit ang inilalarawang kombinatoryo ang mga pangunahing item na pinag-aaralan. Ang sakop na ito ay nagbiigay ng isang mayamang magpagkukunang mga halimbawa para sa disenyong kombinatoryal. Ito ay hindi dapat ikalito sa heometriyang diskreto (heometriyang kombinatoryal).

Teoriyang kaayusan

Diagramang Hasse ng kapangyarihang hanay ng (x,y,z} na isinaayos ng mapang inklusyon.

Ang teoriyang kaayusan ang pag-aaral ng parsiyal na isinaayos na mga hanay na parehong may hangganan at walang hangganan. Ang iba't ibang mga halimbawa ng parsiyal na mga kaayusan ay lumilitaw sa abstraktong alhebra, heometriya, teoriya ng bilang, at sa buong kombinatorika at teoriya ng grapo. Ang mga kilalang klase at halimbawa ng mga parsiyal na kaayusan ay kinabibilangan ng mga lattice at mga alhebrang Boolean.

Teoriyang matroid

Ang Teoriyang matroid ay nag-aabstrakto ng bahagi ng heometriya. Ito ay nag-aaral ng mga katangian ng hanay (na karaniwang mga may hangganan hanay) ng mga bektor sa isang espasyong bektor na hindi nakasalalay sa partikular na mga koepisyente sa isang relasyong dependensiyang linyar. Hindi lamang ang istraktura kundi pa rin ang mga katangiang enumeratibo ay kabilang sa teoriyang matroid. Ang teoriyang matroid ay ipinakilala ni Hassler Whitney at pinag-aralan bilang isang bahagi ng teoriya ng kaayusan. Ito ay isa na ngayong independiyenteng larangan ng pag-aaral na may mga koneksiyon sa iba pang bahagi ng kombinatorika.

Kombinatorikang ekstremal

Ang kombinatorikang ekstremal ay nag-aaral ng mga tanong na ekstremal sa mga sistemang hanay. Ang mga uri ng tanong na tinutugon sa kasong ito ay tungkol sa pinakamalaking posibleng grapo na sumasapat sa ilang mga katangian. Halimbawa, ang pinaka malakaing malaya sa tatsulok na grapo sa mga berteks na 2n ay isang kompletong grapong bipartite na K_n,n. Kadalasan, napakahirap na kahit humanap ng sagot na f(n) nang eksakto at maaari lamang magbigay ng pagtatantiyang asimptotiko. Ang teoriyang Ramsey ay isa pang bahagi ng kombinatorikang ekstremal. Ito ay nagsasaad na anumang sapat na malaking konpigurasyon ay maglalaman ng ilang uri ng kaayusan. Ito ay sumulong na paglalahat ng prinsipyong butasngkalapati.

Kombinatorikang probabilistiko

Umiiwas sa sariling lakad sa isang kwadradong grid na grapo.

Sa kombinatorikang probabilistiko, ang mga tanong ay ng sumusunod na uri: ano snh probabilidad ng isang katangian para sa randomang disrektong obhekto gaya randomang grapo? Halimbawa, ano ang aberaheng bilang mga tatsulok sa isang randomang grapo? Ang mga pamamaraang probabilistiko ay ginagamit rin upang tukuyin ang pag-iral ng mga obhektong kombinatoryal na may ilang inilarawang katangian (kung saan ang mga hayagang halimbawa ay maaaring mahirap na matagpuan) sa simpleng pagmamasid ng probabilidad ng randomang napiling obhekto na may mga katangian na mas malaki sa 0. Ang pakikitungong ito (na kadalasang tinutukoy na ang pamamarang probabilistiko) ay napatunayang mataas na epektibo sa pag-aaral ng may hangganang mga kadenang Markov lalo na sa mga obhektong kombinatoryal. Dito muli, ang mga kasangkapang probabilistiko ay ginagamit upang tantiyahin ang paghahalong panahon na kadenang Markov. Kadalasang inuugnay kay Paul Erdős na gumawa ng nagpasimulang akda sa paksa, ang kombinatorikang probabilistiko ay tradisyonal na nakikita bilang isang hanay ng mga kasangkapan sa pag-aaral ng ibang mga problema ng kombinatorika. Gayunpaman, sa paglago ng mga aplikasyon ng [[analisis ng algoritmo] sa agham pangkompyuter gayundin din sa klasikong probabilidad na aditibong teoriya ng bilang at teoriya ng bilang na probabilistiko, ang sakop na ito ay lumago na naging isang idependiyenteng larangan ng kombinatorika.

Kominatorikang alhebraiko

Diagramang Young ng isang partisyon na (5,4,1).

Ang kombinatorikang alhebraiko ang area ng matematika na gumagamit ng mga pamamaraan ng abstraktong alhebra at sa kabaligtaran ay naglalapat ng mga pamamaraang kombinatoryal sa mga problema sa abstraktong alhebra. Sa loob ng mga huling dekada, ang kombinatorikang alhebraiko ay nakita ng mas malawig bilang area ng matematika kung saan ang interaksiyong mga pamamaraang kombinatoryal at alhebraiko ay partikular na malakas at mahalaga. Ang isa sa pinakamabilis na umuunlad na pang-ilalim na mga larangan sa loob ng kombinatorikang alhebraiko ang kombinatoryal na komutatibong alhebra.

Kombinatorika sa mga salita

Konstruksiyon ng walang hangganang salitang Thue-Morse.

Ang kombinatorika sa mga salita ay umuukol sa mga wikang pormal. Ito ay independiyenteng lumitaw sa loob ng ilang mga sangay ng matematika kabilang ang teoriya ng bilang, teoriya ng grupo at probabilidad. Ito ay may mga aplikasyon sa kombinatorikang enumeratibo, analisis ng praktal, teoretikal na agham pangkompyuter, teoriyang automata, at linguistika. Bagaman ang maraming mga aplikasyon ay bago, ang klasikong hierarkang Chomsky–Schützenberger ng mga klase ng mga grammar na pormal ay marahil ang pinaka kilalang resulta sa larangan.

Kombinatorikang heometriko

Isang icosahedron.

Ang kombinatorikang heometriko ay nauugnay sa heometriyang konbeks at [[heometriyang disrekto sa partikular na ang kombinatorikang polihedral. Ito ay nagtatanong halimbawa kung gaano karaming mga mukha ng bawat dimensiyon na ang politopong konbeks ay maaaring magkaroon. Ang mga katangiang metrikong ng mga politopo ay gumagampan rin ng isang mahalagang papel e.g. teorema ni Cauchy sa pagiging mahigpit ng mga politopong konbeks. Ang mga espesyal na politopo ay isinasaalang alang rin gaya ng permutohedra, associahedra at mga politopong Birkhoff. Ang heometriyang kombinatoryal ay isang makalumang pangalan para sa heometriyang diskreto.

Kombinatorikang topolohikal

Problemang paghahati ng kwintas ng may dalawang mga putol.

Ang mga analogong kombinatoryal ng mga konsepto at pamamaraan sa topolohiya ay ginagamit upang pag-aralan ang pagkukulay ng grapo, pantay na paghahati, partisyon ng isang hanay, parsiyal na inayon na hanay, mga desisyong puno, mga problema ng kwintas at teoriyang diskretong Morse. Ito ay hindi dapat ikalito sa topolohiyang kombinatoryal na mas matandang pangalan ng topolohiyang alhebraiko.

Kombinatorikang aritmetiko

Ang kombinatorikang aritmetiko ay lumitaw mula sa ugnayan sa pagitan ng teoriya ng bilang, kombinatorika, teoriyang ergodiko at analisis na harmoniko. Ito ay tungkol sa mga pagtatantiyang nauugnay sa mga operasyong aritmetiko (adisyon, subtraksiyon, multiplikasyon at dibisyon). Ang kombinatorikang aditibo ay tumutukoy sa espesyal na kaso kapag tanging ang mga operasyon ng adisyon at subtraksiyon ay nasasangkot. Ang isang mahalagang pamamaraan sa kombinatorikang aritmetiko ang teoriyang ergodiko ng mga sistemang dinamikal.

Kombinatorikang walang hangganan

Ang kombinatorikang walang hangganan o kombinatoryal na teoriya ng hanay ang ekstensiyon ng mga ideya sa kombinatorika sa mga hanay na walang hangganan. Ito ay bahagi ng teoriya ng hanay na sakop ng lohikang matematikal ngunit gumagamit rin ng mga kasangkapan at ideya mula sa parehong teoriya ng hanay at kombinatorikang ekstremal. Ginamit ni Gian-Carlo Rota ang pangalang kombinatorikang tuloy tuloy^[3] upang ilarawan ang probabilidad at teoriya ng hanay dahil mayroong maraming mga analohiya sa pagitan ng pagbibilang at sukat.

Mga sanggunian

↑ Björner and Stanley, p. 2
↑ 2-Digit MSC Comparison Naka-arkibo 2008-12-31 sa Wayback Machine., by Daniel P. Sanders.
↑ Continuous and profinite combinatorics

[1] Björner and Stanley, p. 2

[2] 2-Digit MSC Comparison Naka-arkibo 2008-12-31 sa Wayback Machine., by Daniel P. Sanders.

[3] Continuous and profinite combinatorics

[1]

[2]

[3]