Пермутации и комбинации, различните начини, по които могат да бъдат избрани обекти от даден набор, обикновено без подмяна, за да се образуват подмножества. Този избор на подмножества се нарича пермутация, когато редът на подбор е фактор, комбинация, когато редът не е фактор. Разглеждайки съотношението на броя на желаните подмножества към броя на всички възможни подмножества за много хазартни игри през 17-ти век, френските математици Блез Паскал и Пиер дьо Фермат дават тласък на развитието на комбинаториката и теорията на вероятностите.
комбинаторика: Биномиални коефициенти
n обекти се наричат пермутация на n неща, взети r наведнъж. Броят на пермутациите е
Концепциите и разликите между пермутациите и комбинациите могат да бъдат илюстрирани чрез разглеждане на всички различни начини, по които двойка обекти могат да бъдат избрани от пет различими обекта - като буквите A, B, C, D и E. Ако и двете се вземат предвид избраните букви и редът на подбор, тогава са възможни следните 20 резултата:
Всеки от тези 20 различни възможни селекции се нарича пермутация. По-специално, те се наричат пермутации на пет обекта, взети два наведнъж и броят на възможните такива пермутации се обозначава със символа 5 P 2, четено „5 пермута 2.“ Като цяло, ако има n обекта, от които да изберете, и пермутациите (P) трябва да се формират с помощта на k на обектите в даден момент, броят на различните възможни пермутации се обозначава със символа n P k. Формула за нейното оценяване е n P k = n! / (N - k)! Изразът n! - прочетено „n факторен“ - показва, че всички последователни положителни числа от 1 до и включително n трябва да бъдат умножени заедно, и 0! се дефинира на равен 1. Например, използвайки тази формула, е броят на престановките на пет обекта, взети два наведнъж
(За k = n, n P k = n! По този начин за 5 обекта има 5! = 120 подредби.)
За комбинации, k обекти са избрани от набор от n обекта, за да се произведат подмножества, без да се подреждат. Контрастирайки предишния пример за пермутация със съответната комбинация, подмножествата AB и BA вече не са различни селекции; чрез елиминиране на такива случаи остават само 10 различни възможни подмножества - AB, AC, AD, AE, BC, BD, BE, CD, CE и DE.
Броят на такива подмножества се обозначава с n C k, четете "n select k." За комбинации, тъй като k обекти имат k! уговорки, има к! неразличими пермутации за всеки избор на k обекти; следователно разделянето на формулата за пермутация на k! дава следната комбинирана формула:
Това е същото като (n, k) биномиален коефициент (виж биномиална теорема). Например, броят на комбинациите от пет обекта, взети два наведнъж, е
Формулите за n P k и n C k се наричат формули за броене, тъй като те могат да бъдат използвани за преброяване на броя на възможните пермутации или комбинации в дадена ситуация, без да се налага да ги изброявате всички.
