Pumunta sa nilalaman

Kombinatorika: Pagkakaiba sa mga binago

Mula sa Wikipedia, ang malayang ensiklopedya
Browse history interactively
← Nakaraang pagkakaiba
Nilalaman na inalis Nilalaman na idinagdag
VisualWikitext
m Ang talasanggunian ay mas ginagamit sa pagtukoy sa bibliography habang ang mga sanggunian ay mas ginamait para tukuyin ang references (via JWB)
Tatak: Manual revert
 
(hindi ipinakita ang isang agarang pagbabago ng isang tagagamit)
Linya 1: Linya 1:
Ang '''Kombinatorika''' (Ingles: '''Combinatorics''') ay isang ng sangay ng [[matematika]] na umuukol sa may hangganan o [[mabibilang na hanay|mabiblang]] na [[diskretong matematika|diskretong]] mga [[istrakturang matematikal|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 mg 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]].<ref>Björner and Stanley, p. 2</ref> Ang kombinatorika ay marami ring mga aplikasyon sa [[matematikal na optimisasyon|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]].
Ang '''kombinatorika''' ({{lang-en|combinatorics}}) ay isang ng sangay ng [[matematika]] na umuukol sa may hangganan o [[mabibilang na hanay|mabibilang]] na [[diskretong matematika|diskretong]] mga [[istrakturang matematikal|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]].<ref>Björner and Stanley, p. 2</ref> Ang kombinatorika ay marami ring mga aplikasyon sa [[matematikal na optimisasyon|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===
==Mga pakikitungo at pang-ilalim na larangan==
===Kombinatorikang enumeratibo===
===Kombinatorikang enumeratibo===
[[Image:Catalan 4 leaves binary tree example.svg|320px|right|thumb|Limang mga [[punong binaryo]] sa tatlong mga [[berteks (teoriya ng grapo)|berteks]] na isang halimbawa ng mga [[bilang na Catalan]].]]
[[Image:Catalan 4 leaves binary tree example.svg|320px|right|thumb|Limang mga [[punong binaryo]] sa tatlong mga [[berteks (teoriya ng grapo)|berteks]] na isang halimbawa ng mga [[bilang na Catalan]].]]
Linya 15: Linya 15:
[[Image:Petersen1 tiny.svg|thumb|150px|[[Grapong Petersen]].]]
[[Image:Petersen1 tiny.svg|thumb|150px|[[Grapong Petersen]].]]
{{main|Teoriya ng grapo}}
{{main|Teoriya ng grapo}}
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<sub>G</sub>(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.<ref>[http://www.math.gatech.edu/~sanders/graphtheory/writings/2-digit.html 2-Digit MSC Comparison], by Daniel P. Sanders.</ref>
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<sub>G</sub>(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.<ref>[http://www.math.gatech.edu/~sanders/graphtheory/writings/2-digit.html 2-Digit MSC Comparison] {{Webarchive|url=https://web.archive.org/web/20081231163112/http://www.math.gatech.edu/~sanders/graphtheory/writings/2-digit.html |date=2008-12-31 }}, by Daniel P. Sanders.</ref>


===Teoriyang disenyo===
===Teoriyang disenyo===
Linya 23: Linya 23:
===Heometriyang may hangganan===
===Heometriyang may hangganan===
{{main|Heometriyang may hangganan}}
{{main|Heometriyang may hangganan}}
Ang heometriyang may hangganan ang pag-aaral ng mga [[heometriya|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]]).
Ang heometriyang may hangganan ang pag-aaral ng mga [[heometriya|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===
===Teoriyang kaayusan===
Linya 29: Linya 29:
{{main|Teoriyang kaayusan}}
{{main|Teoriyang kaayusan}}


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 mg [[lattice (kaayusan)|lattice]] at mga [[alhebrang Boolean (istraktura)|alhebrang Boolean]].
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 (kaayusan)|lattice]] at mga [[alhebrang Boolean (istraktura)|alhebrang Boolean]].


===Teoriyang matroid===
===Teoriyang matroid===
{{main|Teoriyang matroid}}
{{main|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 [[independiyensiyang linyar|dependensiyang linyar]]. Hindi lamang ang istrakturi 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.
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 [[independiyensiyang linyar|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===
===Kombinatorikang ekstremal===
Linya 43: Linya 43:
[[Image:Self avoiding walk.svg|thumb|right|150px|[[Umiiwas sa sariling lakad]] sa isang [[grapong lattice|kwadradong grid na grapo]].]]
[[Image:Self avoiding walk.svg|thumb|right|150px|[[Umiiwas sa sariling lakad]] sa isang [[grapong lattice|kwadradong grid na grapo]].]]
{{main|Pamamaraang probabilistiko}}
{{main|Pamamaraang probabilistiko}}
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.
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===
===Kominatorikang alhebraiko===
Linya 56: Linya 56:


===Kombinatorikang heometriko ===
===Kombinatorikang heometriko ===
[[Image:Icosahedron.svg||150px|thumb|right|Isang [[icosahedron]].]]
[[Image:Icosahedron.svg|150px|thumb|right|Isang [[icosahedron]].]]
{{main|Kombinatorikang heometriko}}
{{main|Kombinatorikang heometriko}}
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 [[heometriyang metriko|metriko]]ng ng mga politopo ay gumagampan rin ng isang mahalagang papel e.g. [[teorema ni Cauchy (heometriya)|teorema ni Cauchy]] sa pagiging mahigpit ng mga politopong konbeks. Ang mga espesyal na politopo ay isinasaalang alang rin gaya ng [[permutohedron|permutohedra]], [[associahedron|associahedra]] at mga [[politopong Birkhoff]]. Ang [[heometriyang kombinatoryal]] ay isang makalumang pangalan para sa heometriyang diskreto.
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 [[heometriyang metriko|metriko]]ng ng mga politopo ay gumagampan rin ng isang mahalagang papel e.g. [[teorema ni Cauchy (heometriya)|teorema ni Cauchy]] sa pagiging mahigpit ng mga politopong konbeks. Ang mga espesyal na politopo ay isinasaalang alang rin gaya ng [[permutohedron|permutohedra]], [[associahedron|associahedra]] at mga [[politopong Birkhoff]]. Ang [[heometriyang kombinatoryal]] ay isang makalumang pangalan para sa heometriyang diskreto.
===Kombinatorikang topolohikal===
===Kombinatorikang topolohikal===
[[Image:Necklace cropped.png||150px|thumb|right|[[Problemang paghahati ng kwintas]] ng may dalawang mga putol.]]
[[Image:Necklace cropped.png|150px|thumb|right|[[Problemang paghahati ng kwintas]] ng may dalawang mga putol.]]
{{main|Kombinatorikang topolohikal}}
{{main|Kombinatorikang topolohikal}}
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]].
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]].
Linya 67: Linya 67:
{{main|Kombinatorikang aritmetiko}}
{{main|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]].
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===
===Kombinatorikang walang hangganan===
Linya 73: Linya 73:


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<ref>[http://faculty.uml.edu/dklain/cpc.pdf Continuous and profinite combinatorics]</ref> upang ilarawan ang [[probabilidad]] at [[teoriya ng hanay]] dahil mayroong maraming mga analohiya sa pagitan ng pagbibilang at sukat.
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<ref>[http://faculty.uml.edu/dklain/cpc.pdf Continuous and profinite combinatorics]</ref> upang ilarawan ang [[probabilidad]] at [[teoriya ng hanay]] dahil mayroong maraming mga analohiya sa pagitan ng pagbibilang at sukat.

==Mga sanggunian==
==Mga sanggunian==
{{reflist}}
{{reflist}}


{{Matematika}}
{{Matematika}}
[[Kategorya:Matematika]]
[[Kategorya:Kombinatorika| ]]
[[Kategorya:Kombinatorika]]

Kasalukuyang pagbabago noong 00:27, 10 Pebrero 2024

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

[baguhin | baguhin ang wikitext]

Kombinatorikang enumeratibo

[baguhin | baguhin ang wikitext]
Limang mga punong binaryo sa tatlong mga berteks na isang halimbawa ng mga bilang na Catalan.
Pangunahing artikulo: Kombinatorikang enumeratibo

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

[baguhin | baguhin ang wikitext]
Pangunahing artikulo: 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

[baguhin | baguhin ang wikitext]
Isang planong partisyon.
Pangunahing artikulo: Teoriya ng 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

[baguhin | baguhin ang wikitext]
Grapong Petersen.
Pangunahing artikulo: Teoriya ng grapo

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 TG(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

[baguhin | baguhin ang wikitext]
Pangunahing artikulo: Disenyong kombinatoryal

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

[baguhin | baguhin ang wikitext]
Pangunahing artikulo: 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

[baguhin | baguhin ang wikitext]
Diagramang Hasse ng kapangyarihang hanay ng (x,y,z} na isinaayos ng mapang inklusyon.
Pangunahing artikulo: Teoriyang kaayusan

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

[baguhin | baguhin ang wikitext]
Pangunahing artikulo: 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

[baguhin | baguhin ang wikitext]
Pangunahing artikulo: 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 Kn,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

[baguhin | baguhin ang wikitext]
Umiiwas sa sariling lakad sa isang kwadradong grid na grapo.
Pangunahing artikulo: Pamamaraang probabilistiko

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

[baguhin | baguhin ang wikitext]
Diagramang Young ng isang partisyon na (5,4,1).
Pangunahing artikulo: Kombinatorikang alhebraiko

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

[baguhin | baguhin ang wikitext]
Konstruksiyon ng walang hangganang salitang Thue-Morse.
Pangunahing artikulo: Kombinatorika sa mga salita

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

[baguhin | baguhin ang wikitext]
Isang icosahedron.
Pangunahing artikulo: Kombinatorikang heometriko

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

[baguhin | baguhin ang wikitext]
Problemang paghahati ng kwintas ng may dalawang mga putol.
Pangunahing artikulo: Kombinatorikang topolohikal

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

[baguhin | baguhin ang wikitext]
Pangunahing artikulo: 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

[baguhin | baguhin ang wikitext]
Pangunahing artikulo: 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

[baguhin | baguhin ang wikitext]
  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
Kinuha sa "https://tl.wikipedia.org/w/index.php?title=Kombinatorika&oldid=2087782"