Kombinatoriko

El Vikipedio

Matematiko > Kombinatoriko

Kombinatoriko estas branĉo de la matematiko, en kiu oni studas la ekziston kaj konstruon de diversaj kombinaĵoj kaj aranĝoj de elementoj laŭ difinitaj reguloj, kaj serĉas la nombrojn de kombinaĵoj kaj aranĝoj de diversaj tipoj.

Ekzemploj de tiaj kombinaĵoj estas aranĝaĵoj, kombinaĵoj permutaĵoj, blok-skemoj kaj Latinaj kvadratoj. Apero de ĉefaj nocioj kaj evoluo de kombinatora analizo okazis paralele kun aliaj branĉoj de matematiko, tiaj kiaj estas algebro, nombroteorio, probabloteorio, kun kiuj ĝi havas proksimajn rilatojn. Estiĝo de kombinatoriko, kiel matematika scienco, estas ligita kun la verkoj de Blaise Pascal kaj Pierre De Fermat. Ĉi tiuj verkoj, fariĝintaj bazo por la teorio de probabloj, samtempe enhavis principojn por la determino de nombro de kombinaĵoj por finia aro.

La gravan rolon en la evoluo de kombinatoraj metodoj plenumis Gottfried Wilhelm Leibniz, Jakob Bernoulli kaj Leonhard Euler. De la 50-aj jaroj de la 20-a jarcento intereso pri kombinatoriko reviviĝas pro la impeta evoluo de komputiko, cibernetiko, diskreta matematiko, teorio de planado kaj informteorio.

La ĉefaj konceptoj de kombinatoriko estas:

Faktorialo - la produto 1·2·3·...·n; ĝi estas signita per la simbolo n! La faktorialo de 5 estas:

5!=1·2·3·4·5=120

Permutaĵo - Ĉiu el la eblaj diversaj manieroj vicigi la elementojn de certa aro. La diversaj permutaĵoj de la elementoj a, b, c estas: abc, acb, bac, bca, cab, cba. La nombro de eblaj permutaĵoj de n elementoj estas ĉiam n! .
Aranĝaĵo - Ĉiu el la diversaj manieroj fari ordigitan liston de m elementoj el aro de n elementoj (do, du aranĝoj estas samaj nur kondiĉe ke inter la du listoj ekzistu diferenco aŭ pri la loko, aŭ pri la identeco de almenaŭ unu elemento). La nombron de tiaj aranĝaĵoj esprimas la formulo

$A(n,r) = n(n-1)(n-2)(n-3)...(n-m+2)(n-m+1) = \frac{n!}{(n-k)!}$

Kombinaĵo ( aŭ kombinacio) - de k el n elementoj. Aro de k elementoj, elektita el la aro da n elementoj: la eblaj kombinacioj de 2 el la 4 elementoj a, b, c, d estas: ab, ac, ad, bc, bd, cd. La K de k el n estas la nombro de la aranĝaĵoj dividita de la nombro de permutaĵoj en k:

${n \choose k} = \frac{n!}{k! (n-k)!}$

Latina kvadrato - aranĝo de n simboloj en kvadrato kun n horizontalaj linioj kaj n vertikalaj linioj, tiel ke, ĉiu simbolo aperas ĝuste unu fojon en ĉiu horizontala linio kaj ĝuste unu fojon en ĉiu vertikala linio.