Permutatsioonid ja kombinatsioonid - mitmesugused viisid, kuidas komplekti objekte alamhulkade moodustamiseks üldiselt valida ilma asendamiseta. Seda alamhulkade valikut nimetatakse permutatsiooniks, kui valiku järjekord on tegur, kombinatsiooniks, kui järjekord pole tegur. Kaaludes 17. sajandil paljude õnnemängude soovitud alamhulkade arvu ja kõigi võimalike alamhulkade suhet, andsid prantsuse matemaatikud Blaise Pascal ja Pierre de Fermat tõuke kombinatoorika ja tõenäosusteooria väljatöötamisele.
kombinatoorika: binoomide koefitsiendid
n objekti nimetatakse r korraga võetud n asja permutatsiooniks. Permutatsioonide arv on
Permutatsioonide ja kombinatsioonide mõisteid ja erinevusi saab illustreerida, uurides kõiki erinevaid viise, kuidas objektide paari saab valida viie eristatava objekti hulgast - näiteks tähed A, B, C, D ja E. Kui mõlemad kui arvestatakse valitud tähti ja valiku järjekorda, on võimalikud järgmised 20 tulemust:
Neid 20 erinevat võimalikku valikut nimetatakse permutatsiooniks. Eelkõige nimetatakse neid viie objekti permutatsioonideks, mis võetakse kaks korraga ja nende võimalike permutatsioonide arvu tähistatakse sümboliga 5 P 2, loe “5 permute 2.” Üldiselt, kui valida on n objekti, millest saab valida, ja permutatsioonid (P) tuleb moodustada, kasutades objektide k-d korraga, tähistatakse võimalike erinevate permutatsioonide arvu sümboliga n P k. Selle hindamise valem on n P k = n! / (N - k)! Lause n! - loe „n faktoriaal” - näitab, et kõik üksteisele järgnevad positiivsed täisarvud vahemikus 1 kuni n (kaasa arvatud) tuleb korrutada, ja 0! on defineeritud kui võrdne 1. Näiteks kasutatakse seda valemit kasutades korraga viiest objektist permutatsioonide arv
(K = n, n P k = n! Seega on 5 objekti puhul 5! = 120 paigutust.)
Kombinatsioonide jaoks valitakse k objekti hulgast n objekti, et toota alamhulki ilma tellimiseta. Vastupidiselt eelmisele permutatsiooninäitele vastava kombinatsiooniga, ei ole alamhulgad AB ja BA enam selged valikud; Selliste juhtumite kõrvaldamisega jääb ainult kümme erinevat alamhulka - AB, AC, AD, AE, BC, BD, BE, CD, CE ja DE.
Selliste alamhulkade arvu tähistatakse n C k-ga, loe “n vali k”. Kombinatsioonide jaoks, kuna k objektil on k! kokkulepped, seal on k! k-objekti iga valiku jaoks eristamatud permutatsioonid; jagades seega permutatsiooni valemi k-ga! annab järgmise kombinatsioonvalemi:
See on sama kui (n, k) binoomide koefitsient (vt binoomi teoreem). Näiteks on korraga viiest objektist koosnevate kombinatsioonide arv kaks
Valemid n P k ja n C k nimetatakse loendamise valemitega kuna neid saab kasutada loendada võimalike kombinatsioonide või nende kombinatsioonide puhul konkreetses olukorras, ilma et peaks neid kõiki loetleda.
