Пермутации

Пермутацията е частен случай на вариация, когато имаме множество с n елемента и искаме да намерим броя на всички различни n-торки.

Формула

Ще си припомним самите вариации. Нека имаме множеството от цифри {1, 2, 3, 4, 5}. Колко трицифрени числа можем да съставим от тях, ако никоя цифра не може да се повтаря? Това е типичен пример за вариации, който се решава с познатата формула

$$V_n^k=\frac{n!}{(n-k)!}=\frac{5!}{(5-3)!}=60.$$

Колко петцифрени числа бихме могли да съставим?

$$V_n^k=\frac{5!}{(5-5)!}=\frac{5!}{0!}=5!=120.$$

Забелязваме, че ако имаме множество с пет елемента и търсим броя на всички различни петорки, резултатът е равен на 5!. Можем да обобщим и да кажем, че ако имаме множество с n елемента, съществуват общо n! различни n-торки. Така стигаме до понятието пермутация.

Какво е пермутация

Ако имаме множество M с n елемента, пермутация е всяка n-торка, съставена от елементи на множеството M, като никой елемент не може да се повтаря. Пример: ако имаме множеството M = {a, b, c, d}, пермутация е например (a; b; d; c) или (d; b; a; c). Броят на всички различни пермутации е равен на

$$P_n=V_n^n=n!$$

Решени примери

1. Имаш шест книги и искаш да ги подредиш на един рафт в някакъв ред. Колко са всички различни подредби? Имаме шест книги, всеки път пермутираме всички книги, така че резултатът е равен на P₆ = 6! = 720.

2. Към твоите 6 български книги от предишния пример са се добавили 4 книги на латински. По колко различни начина можеш да подредиш тези 10 книги на рафта, ако искаш всички български книги да са заедно и всички латински книги да са заедно?

   Какви са възможностите да подредим книгите? Можем първо да наредим шестте български книги и след това четирите латински или обратно – първо четирите латински и после шестте български. При това има 6! начина да наредим българските книги и 4! начина да наредим латинските. Прилагаме комбинаторното правило за умножение и умножаваме тези резултати: 6! · 4! = 17 280. Тъй като има две възможности как да подредим книгите (първо българските, после латинските и обратно), това число трябва да умножим още по две. Общият резултат е 17 280 · 2 = 34 560.