Вариации

Вариации използваме, когато от дадено множество от обекти избираме определен брой обекти, като редът, в който ги избираме, има значение.

Извеждане на формулата

Ще започнем с типична задача за вариации: в едно село всяка година се организира състезание по ядене на баница. Във финала са стигнали общо седем омазнени състезатели. Пресметни колко са всички възможности тези седем участници да заемат първите три места.

Важно е да осъзнаем, че в тази задача редът има значение. Например ако знаем, че на първите три места са се класирали Тони, Георги и Петър, то само тази тройка ни дава общо шест различни класирания:

Тони, Георги, Петър;
Тони, Петър, Георги;
Георги, Тони, Петър;
Георги, Петър, Тони;
Петър, Тони, Георги;
Петър, Георги, Тони.

Всичко това са различни класирания и ние искаме да преброим колко общо различни класирания можем да съставим, когато състезателите са 7.

За целта ще използваме комбинаторното правило за умножение. Ще кажем, че избираме тройки от вида (x₁; x₂; x₃), където x₁ е състезателят, който е завършил на първо място, и т.н. Кои състезатели можем да поставим на мястото на x₁? Всички, т.е. на мястото на x₁ можем да поставим 7 състезатели. Кои можем да поставим на мястото на x₂? Всички освен този, когото вече сме поставили на първо място, така че на мястото на x₂ можем да поставим 7 − 1 = 6 състезатели. На мястото на x₃ можем да поставим състезателите, които не са на първо и не са на второ място, т.е. имаме 7 − 2 = 5 възможности. Прилагаме комбинаторното правило за умножение и получаваме общия брой възможности: 7 · 6 · 5 = 210.

Забелязваме, че ако искаме да знаем броя на всички възможности за първите 4 места, на мястото на x₄ можем да поставим 7 − 3 = 4 състезатели, така че общият брой възможности ще бъде 7 · 6 · 5 · 4 = 840. Какво можем да изведем от това?

Ако имаме множество с n елемента (тук в примера 7 лакомници) и избираме 3 елемента, като редът има значение, резултатът е равен на n · (n − 1) · (n − 2). На първо място може да се класира всеки, на следващото – с един по-малко и т.н. От това можем да изведем общата формула за случая, когато избираме k елемента от множество с n елемента: броят на възможностите ще бъде равен на n · (n − 1) · (n − 2) · … · (n − k + 1).

Тази формула ще преобразуваме още малко с помощта на факториела. Ако погледнем как изглежда факториелът на седем: 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1 и как пресметнахме броя на всички класирания за медалите 7 · 6 · 5, виждаме известна прилика. Трябва само да се отървем от края, т.е. трябва да разделим 7! на 4 · 3 · 2 · 1, като така ни остава само 7 · 6 · 5. На какво е равен изразът 4 · 3 · 2 · 1? Той е равен на 4!.

Можем да запишем, че ако имаме множество с n елемента и избираме общо k елемента, като редът има значение, имаме общо

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

възможности. Ако заместим в тази формула числата от състезанието по ядене на баница:

$V_{7}^{3} = \frac{7!}{(7 - 3)!} = \frac{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{4 \cdot 3 \cdot 2 \cdot 1} = 7 \cdot 6 \cdot 5 = 210.$

Калкулатор

Следният калкулатор пресмята броя на вариациите за дадени n и k.

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

Оставаме при състезанието по ядене на баница. Как би се променил броят на възможните класирания за медалите, ако знаем, че на състезанието е дошъл Любен, който е майстор и винаги печели? Т.е. колко са различните класирания за медалите, ако имаме 7 състезатели и Любен със сигурност печели?

Това е отново проста вариация: първото място е сигурно, а от останалите 6 състезатели трябва да определим как могат да заемат второто и третото място. Избираме 2 елемента от множество с 6 елемента, което води до вариацията

$V_{6}^{2} = \frac{6!}{(6 - 2)!} = 30$

Преди много време, когато Любен още не беше такъв майстор, той редовно се класираше сред първите трима. Колко са различните класирания за медалите, ако имаме 7 състезатели и Любен със сигурност получава някакъв медал?

Този пример се различава от предишния по това, че не знаем на кое място се е класирал Любен – може да е бил втори или дори трети, за което още се срамува. Затова трябва да пресметнем общо три различни вариации: за случая, когато Любен е спечелил, после когато е получил сребърен медал и накрая бронзов медал. Всеки път обаче остават само две места, на които може да се класира някой друг. Ако например Любен е бил втори, останалите участници са могли да се класират или на първо, или на трето място. Следователно отново пресмятаме вариация на шест елемента от втори клас, само че трябва да я пресметнем три пъти – за трите различни класирания на Любен. Броят на всички класирания е равен на:

$3 \cdot V_{6}^{2} = 3 \cdot \frac{6!}{(6 - 2)!} = 3 \cdot 30 = 90$

Забележи, че тройката пред вариацията можем да запишем като $V_{3}^{1}$ , защото всъщност избираме един елемент (едно конкретно класиране) от множество с три елемента (трите медални позиции).
В училището има общо 20 учители. Наближава ДЗИ и трябва да се състави комисия в следния състав: един председател, един „добър“ член и един „строг“ член. Колко са всички възможности?

Първо трябва да отговорим на въпроса дали редът има значение – да, има, защото тримата учители можем отново да разместим по шест различни начина. Сега вече е лесно – избираме вариация на 20 елемента от трети клас:

$V_{20}^{3} = \frac{20!}{17!} = 6840.$
Колко трицифрени числа можем да съставим от цифрите {0, 1, 2, 3, 4, 5}, ако никоя цифра не може да се повтаря?

Редът има ли значение? Да, има, 123 е различно число от 321. Колко различни тройки има? Това е проста вариация на 6 елемента от трети клас:

$V_{6}^{3} = \frac{6!}{3!} = 120.$

Но трябва да извадим още онези вариации, които започват с нула, защото 012 не е трицифрено число. Въпросът сега е: колко са различните тройки, които започват с нула? В такъв случай цифрите се сменят само на останалите две места (тройките са от вида (0; x₂; x₃)), така че търсим колко различни двойки можем да образуваме с числата {1, 2, 3, 4, 5}. Това отново е просто: $V_{5}^{2} = 5! / 3! = 20$ . Следователно има 20 тройки, които започват с нула.

Общият брой на трицифрените числа, съставени от цифрите {0, 1, 2, 3, 4, 5}, е 120 − 20 = 100.
Колко различни трицифрени числа можем да съставим от цифрите {1, 2, 3, 4, 5}, ако никоя цифра не може да се повтаря и полученото число трябва да е нечетно?

Редът има значение, защото 123 е различно число от 321. Съставяме трицифрено число, което е нечетно, т.е. на първите две позиции може да има произволна цифра, а на последната трябва да има една от цифрите {1, 3, 5}. Първо ще пресметнем броя на всички тройки, които можем да съставим от петте цифри: $V_{5}^{3} = 5! / 2! = 60$ .

Всяка цифра ще се среща на последното място еднакво често, така че при 5 цифри всяка от тях ще е на последното място 60 / 5 = 12 пъти. Имаме три цифри {1, 3, 5}, които могат да се появят на последното място, т.е. имаме 12 различни числа, които завършват на 1, 12 числа, които завършват на 3, и 12 числа, които завършват на 5. Прилагаме комбинаторното правило за събиране и получаваме общо 12 + 12 + 12 = 36 възможности.
Пресметни x, ако знаеш, че $V_{x}^{2} = 72$ . С други думи: от множество с големина x избираме двойки и знаем, че можем да изберем общо 72 различни двойки. Колко голямо е било множеството, от което сме избирали двойките? Ще го разпишем:

$V_{x}^{2} = \frac{x!}{(x - 2)!} = 72$

После преобразуваме:

$\begin{array}{rcl} \frac{x!}{(x - 2)!} & = & 72 \\ \frac{x \cdot (x - 1) \cdot (x - 2)!}{(x - 2)!} & = & 72 \\ x \cdot (x - 1) & = & 72 \\ x^{2} - x & = & 72 \\ x^{2} - x - 72 & = & 0 \end{array}$

Това вече е класическо квадратно уравнение, така че можем да го решим с помощта на дискриминантата или да запишем уравнението във вида

$(x + 8) \cdot (x - 9) = 0$

от който вече можем да прочетем решенията: x₁ = −8 и x₂ = 9. Отрицателното решение не ни интересува, защото множеството не може да има отрицателен брой елементи, така че решението на първоначалното уравнение е x = 9, т.е. множеството е имало девет елемента.

Глави: Комбинаторика, Вариации, Пермутации, Комбинации, Вариации с повторение, Комбинации с повторение, Колко различни ПИН кода има?

« Предишна: Комбинаторика

Следваща: Пермутации »