Комбинаторика

Калкулатор: пермутации, вариации и комбинации

Изберете вида на съединенията и въведете $n$ (броя на елементите) и $k$ (класа, т.е. колко елемента избираме). Калкулаторът показва формулата и пресмятането стъпка по стъпка. За пермутациите е нужно само $n.$

Какво е комбинаторика?

Комбинаториката е дялът от математиката, който отговаря на въпроса „по колко начина?“. По колко начина могат да се подредят 7 души в редица? Колко различни фиша има в тотото? Колко четирицифрени числа могат да се запишат с дадени цифри? Вместо да изброяваме всички възможности една по една, ние ги броим с няколко правила и формули. Комбинаториката е и основата на класическата вероятност, където трябва да преброим благоприятните и всички възможни случаи.

Подредбите и изборите, които броим, се наричат съединения. Има три основни вида: пермутации (подреждаме всички елементи), вариации (избираме част от елементите и ги подреждаме) и комбинации (избираме част от елементите, без значение в какъв ред).

На тази страница: Калкулатор · Основни правила · Пермутации · Вариации · Комбинации · Коя формула да използваме · Вероятности · Задачи · Задачи за упражнение

Основни правила на комбинаториката

Правило за събиране

Ако елементът $a$ може да бъде избран по $m$ начина, а елементът $b$ по $n$ други начина, то изборът на $a$ или $b$ може да стане по ${m+n}$ начина.

Пример 1. На рафт има 5 различни книги по математика и 3 различни книги по физика. По колко начина можем да вземем една книга?

Решение. Взимаме или книга по математика (5 начина), или книга по физика (3 начина): ${5+3=8}$ начина.

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

Правило за умножение

Ако елементът $a$ може да бъде избран по $m$ начина и при всеки избор на $a$ елементът $b$ може да бъде избран по $n$ начина, то наредената двойка $(a;\,b)$ може да бъде избрана по ${m\cdot n}$ начина.

Пример 2. Ученик има 3 ризи и 2 панталона. По колко начина може да се облече?

Решение. За всяка от 3-те ризи има 2 панталона, затова комплектите са ${3\cdot 2=6}.$ Дървото по-долу ги показва всичките.

Правилото се обобщава за наредени тройки, четворки и т.н.: ако първият избор става по $m_1$ начина, вторият по $m_2$ начина, третият по $m_3$ начина и т.н., то всички избори заедно стават по ${m_1\cdot m_2\cdot m_3\cdots}$ начина.

Пример 3. Фирма предлага нов модел автомобил в 5 различни цвята, с 3 типа двигател и 2 вида трансмисия. Колко различни модификации има този модел?

Решение. ${5\cdot 3\cdot 2=30}$ модификации.

Пример 4. Колко са четирицифрените числа, в които се срещат само цифрите 1, 2, 3, 4, 5, 6 и 7 и никоя цифра не се повтаря?

Решение. Първата цифра може да бъде избрана по 7 начина. Каквато и да е тя, за втората остават 6 цифри, за третата 5, а за четвъртата 4. Следователно числата са ${7\cdot 6\cdot 5\cdot 4=840}.$

Пермутации на $n$ елемента

Пермутации на $n$ елемента се наричат съединенията, във всяко от които участват всички дадени елементи и които се различават само по реда на елементите. Броят им се означава с $P_n$ и е $$P_n=1\cdot 2\cdot 3\cdots (n-1)\cdot n=n!$$

Произведението ${1\cdot 2\cdot 3\cdots n}$ на първите $n$ естествени числа се означава с $n!$ и се чете „ен факториел“. Например ${3!=1\cdot 2\cdot 3=6}$ и ${5!=120}.$ По определение ${0!=1}.$ Факториелите растат много бързо: ${10!=3\,628\,800}.$

Защо $P_n=n!$? Подреждаме елементите на $n$ места. На първото място може да стои всеки от $n$-те елемента, на второто – всеки от останалите ${n-1},$ на третото – всеки от останалите ${n-2},$ …, а на последното място остава един елемент. По правилото за умножение подрежданията са ${n(n-1)(n-2)\cdots 1=n!}.$

Пример 5. Напишете всички пермутации на буквите $A,$ $B,$ $C.$

Решение. ${P_3=3!=6}:$ $ABC,$ $ACB,$ $BAC,$ $BCA,$ $CAB,$ $CBA.$

Пример 6. По колко различни начина могат да се подредят 7 души в редица?

Решение. $P_7=7!=1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7=5040.$

Пермутации с повтарящи се елементи

Ако някои от елементите са еднакви, размяната им не дава нова подредба. Колко различни думи (със смисъл или без) се получават от буквите на думата МАМА? Ако двете букви М и двете букви А бяха различни, подрежданията щяха да са ${4!=24}.$ Но всяка дума се получава ${2!\cdot 2!=4}$ пъти (разменяме двете М и двете А), затова думите са

${\frac{4!}{2!\cdot 2!}=\frac{24}{4}=6}:$ ММАА, МАМА, МААМ, АММА, АМАМ, ААММ.

Изобщо, ако от $n$ елемента $n_1$ са еднакви от един вид, $n_2$ от друг вид и т.н., подрежданията са ${\frac{n!}{n_1!\,n_2!\cdots}}.$

Вариации от $n$ елемента $k$-ти клас

Вариации без повторение на $n$ елемента от $k$-ти клас ${(k\le n)}$ се наричат съединенията, всяко от които съдържа $k$ различни елемента от дадените $n$ и които се различават едно от друго или по елементите, или по реда на елементите. Броят им е произведението на $k$ поредни естествени числа, започващо от $n:$ $$V_n^k=n(n-1)(n-2)\cdots(n-k+1)=\frac{n!}{(n-k)!}$$

Вариацията е наредена извадка: важно е кои елементи сме избрали и в какъв ред. Формулата следва от правилото за умножение: за първото място има $n$ възможности, за второто ${n-1},$ …, за $k$-тото място ${n-k+1}.$ Пермутациите са вариации, в които участват всички елементи: ${V_n^n=n!=P_n}.$

Пример 7. Напишете всички вариации от 2-ри клас на буквите $A,$ $B,$ $C,$ $D.$

Решение. ${V_4^2=4\cdot 3=12}:$

$AB,$ $AC,$ $AD,$ $BA,$ $BC,$ $BD,$ $CA,$ $CB,$ $CD,$ $DA,$ $DB,$ $DC.$

Двойките $AB$ и $BA$ са различни вариации, защото редът е различен.

Пример 8. В дисциплината троен скок на световното първенство участват 8 състезателки. По колко различни начина могат да се разпределят златният, сребърният и бронзовият медал, ако се знае, че представителката на България със сигурност ще спечели златния медал?

Решение. Златото е определено, затова остава да подредим сребърния и бронзовия медал между другите 7 състезателки. Редът има значение (сребро и бронз са различни медали), следователно начините са ${V_7^2=7\cdot 6=42}.$

Пример 9. Колко различни знамена с три хоризонтални ивици могат да се направят от бял, зелен и червен цвят, ако всеки цвят се използва точно веднъж?

Решение. Подреждаме и трите цвята: ${V_3^3=P_3=3!=6}.$ Едното от тях е българското знаме.

Вариации с повторение

Ако един и същ елемент може да се използва повече от веднъж, на всяко от $k$-те места има по $n$ възможности. Тогава броят на вариациите с повторение е

Тук $k$ може да е и по-голямо от $n.$

Пример 10. Колко са четирицифрените ПИН кодове, ако всяка от цифрите 0–9 може да се повтаря?

Решение. ${\overline{V}{}_{10}^4=10^4=10\,000}.$ Без повторение щяха да са само ${V_{10}^4=10\cdot 9\cdot 8\cdot 7=5040}.$

Комбинации от $n$ елемента $k$-ти клас

Комбинации без повторение на $n$ елемента от $k$-ти клас ${(k\le n)}$ се наричат съединенията, всяко от които съдържа $k$ различни елемента от дадените $n$ и които се различават едно от друго поне по един елемент. Броят им е $$C_n^k=\frac{V_n^k}{P_k}=\frac{n(n-1)\cdots(n-k+1)}{1\cdot 2\cdots k}=\frac{n!}{k!\,(n-k)!}$$

Комбинацията е ненаредена извадка: важно е само кои елементи сме избрали. Затова $AB$ и $BA$ са една и съща комбинация. Числото $C_n^k$ се записва и като $\binom{n}{k}$ и се чете „ен над ка“.

Пример 11. Напишете всички комбинации от 2-ри клас на буквите $A,$ $B,$ $C,$ $D.$

Решение. ${C_4^2=\frac{4\cdot 3}{1\cdot 2}=6}:$ $AB,$ $AC,$ $AD,$ $BC,$ $BD,$ $CD.$

Защо делим на $k!$? Сравнете с пример 7. Всяка от 6-те комбинации, например $\{A,\,B\},$ дава ${2!=2}$ вариации ($AB$ и $BA$), затова вариациите са ${6\cdot 2=12}.$ Изобщо всяка комбинация от $k$ елемента може да се подреди по $k!$ начина, следователно ${V_n^k=C_n^k\cdot P_k}$ и ${C_n^k=\frac{V_n^k}{P_k}}.$

Пример 12. Колко прави се определят от 8 точки, никои три от които не лежат на една права?

Решение. Всяка права се определя от две точки, а редът на точките няма значение: ${C_8^2=\frac{8\cdot 7}{1\cdot 2}=28}.$

Пример 13. В един клас има 20 момчета и 15 момичета. Трябва да се изберат 5 души, от които 3 момчета и 2 момичета. По колко различни начина може да стане този избор?

Решение. Трите момчета избираме по ${C_{20}^3=\frac{20\cdot 19\cdot 18}{1\cdot 2\cdot 3}=1140}$ начина, а двете момичета по ${C_{15}^2=\frac{15\cdot 14}{1\cdot 2}=105}$ начина. По правилото за умножение изборите са ${1140\cdot 105=119\,700}.$

Свойства на комбинациите

• ${C_n^0=C_n^n=1}$ и ${C_n^1=n}.$
• ${C_n^k=C_n^{n-k}}:$ да изберем $k$ елемента е същото като да изберем кои ${n-k}$ елемента остават. Например ${C_{10}^8=C_{10}^2=45}.$
• ${C_n^k=C_{n-1}^{k-1}+C_{n-1}^k}:$ фиксираме един елемент; комбинациите, които го съдържат, са $C_{n-1}^{k-1},$ а тези, които не го съдържат, са $C_{n-1}^k.$

Последното свойство дава триъгълника на Паскал: всяко число е сборът на двете числа над него, а в $n$-тия ред стоят числата ${C_n^0,\ C_n^1,\ \ldots,\ C_n^n}$ (редовете се номерират от 0: най-горният ред е нулевият).

Същите числа са коефициентите в Нютоновия бином ${(a+b)^n},$ затова се наричат и биномни коефициенти. Сборът на числата в $n$-тия ред е $2^n,$ защото това е броят на всички подмножества на множество с $n$ елемента.

Коя формула да използваме

Задайте си два въпроса: участват ли всички елементи и има ли значение редът?

Вид	Има ли значение редът?	Брой
Пермутации	да; участват всички $n$ елемента	${P_n=n!}$
Вариации без повторение	да; избираме $k$ различни елемента	${V_n^k=\frac{n!}{(n-k)!}}$
Комбинации без повторение	не; избираме $k$ различни елемента	${C_n^k=\frac{n!}{k!\,(n-k)!}}$
Вариации с повторение	да; елементите може да се повтарят	${\overline{V}{}_n^k=n^k}$

Пример: от 10 ученици избираме председател, секретар и касиер – редът (длъжността) има значение, ${V_{10}^3=720}.$ Ако избираме просто трима души за екип, редът няма значение, ${C_{10}^3=120}.$

Вероятности

Нека при един опит всички възможни изходи са равновъзможни, $n$ е броят им, а $m$ от тях са благоприятни за събитието $A$ (т.е. при тях $A$ настъпва). Тогава вероятността на $A$ е

Винаги ${0\le P(A)\le 1}.$ При ${P(A)=0}$ събитието е невъзможно, при ${P(A)=1}$ е сигурно, а при ${0\lt P(A)\lt 1}$ е случайно. Ако събитията $A$ и $B$ са несъвместими (не могат да настъпят едновременно), то ${P(A\cup B)=P(A)+P(B)}.$ Подробно за събитията и за свойствата на вероятността вижте урока Теория на вероятностите. Тук ни интересува как комбинаториката преброява $m$ и $n.$

Пример 14. В едно училище учат 400 ученици. От тях 48 са отличници по всички предмети, а 160 са отличници, но не по всички предмети. Каква е вероятността първият срещнат ученик да е пълен отличник (събитие $A$)? А да е отличник, но не по всички предмети (събитие $B$)?

Решение. ${P(A)=\frac{48}{400}=0{,}12}$ и ${P(B)=\frac{160}{400}=0{,}4}.$ Събитията са несъвместими, затова вероятността ученикът да е отличник изобщо е ${0{,}12+0{,}4=0{,}52}.$

Пример 15. При играта белот всеки играч получава 8 от 32 карти. Каква е вероятността играч да получи и четирите валета?

Решение. Възможните раздавания на 8 карти са $C_{32}^8.$ Благоприятни са тези, в които са четирите валета и още 4 карти от останалите 28: $C_{28}^4$ раздавания. Следователно

${P}={\frac{C_{28}^4}{C_{32}^8}}={\frac{20\,475}{10\,518\,300}}={\frac{7}{3596}}\approx{0{,}0019.}$

Задачи

Задача 1. Колко десетцифрени числа могат да се запишат, като всяка от цифрите 0–9 се използва точно веднъж?

Решение. Пермутациите на 10-те цифри са ${10!=3\,628\,800},$ но тези, които започват с 0, не са десетцифрени числа. Те са колкото пермутациите на останалите 9 цифри, ${9!=362\,880}.$ Следователно числата са ${10!-9!=3\,265\,920}.$ Същото получаваме и направо: първата цифра избираме по 9 начина (без 0), а останалите 9 цифри подреждаме по $9!$ начина: ${9\cdot 9!=3\,265\,920}.$

Задача 2. Колко пермутации могат да се съставят от а) 4 елемента; б) 5 елемента; в) 7 елемента?

Решение. а) ${P_4=4!=24};$ б) ${P_5=5!=120};$ в) ${P_7=7!=5040}.$

Задача 3. Пресметнете: а) $C_5^2;$ б) $C_{10}^3;$ в) $C_5^5;$ г) $C_6^1;$ д) $C_6^6.$

Решение. а) ${C_5^2=\frac{5\cdot 4}{1\cdot 2}=10};$ б) ${C_{10}^3=\frac{10\cdot 9\cdot 8}{1\cdot 2\cdot 3}=120};$ в) ${C_5^5=1};$ г) ${C_6^1=6};$ д) ${C_6^6=1}.$

Задача 4. В играта „6 от 49“ на Българския спортен тотализатор играчите отбелязват 6 числа от 1 до 49. Колко различни фиша могат да бъдат попълнени?

Решение. Редът на числата във фиша няма значение, затова всеки фиш е комбинация от 49 елемента от 6-ти клас:

${C_{49}^6}={\frac{49\cdot 48\cdot 47\cdot 46\cdot 45\cdot 44}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6}}={13\,983\,816.}$

Задача 5. Колко са възможните комбинации в играта „5 от 35“?

Решение. $C_{35}^5=\frac{35\cdot 34\cdot 33\cdot 32\cdot 31}{1\cdot 2\cdot 3\cdot 4\cdot 5}=324\,632.$

Задача 6. Кое от следните събития е най-вероятно: $A$ – в играта „6 от 49“ да се познаят 6 числа; $B$ – в играта „6 от 42“ да се познаят 6 числа; $C$ – в играта „5 от 35“ да се познаят 5 числа?

Решение. При всяка игра само един фиш от всички възможни печели:

$P(A)=\frac{1}{C_{49}^6}=\frac{1}{13\,983\,816}\approx 0{,}000\,000\,072,$

$P(B)=\frac{1}{C_{42}^6}=\frac{1}{5\,245\,786}\approx 0{,}000\,000\,19,$

$P(C)=\frac{1}{C_{35}^5}=\frac{1}{324\,632}\approx 0{,}000\,003\,1.$

Следователно ${P(A)\lt P(B)\lt P(C)}:$ най-вероятно е събитието $C.$

Задача 7. От тесте с 52 карти се изтеглят 3 карти. Каква е вероятността това да са една тройка, една седмица и едно асо?

Решение. Всички изтегляния са ${C_{52}^3=\frac{52\cdot 51\cdot 50}{1\cdot 2\cdot 3}=22\,100}.$ Тройката може да е всяка от 4-те тройки, седмицата – всяка от 4-те седмици, а асото – всяко от 4-те аса, затова благоприятните случаи са ${4\cdot 4\cdot 4=64}.$ Следователно ${P=\frac{64}{22\,100}=\frac{16}{5525}\approx 0{,}0029}.$

Задача 8. Иван забравил последната цифра от телефонния номер на Петър и я набира наслуки, без да повтаря цифра. Каква е вероятността да уцели правилния номер с най-много 2 опита?

Решение. Възможностите за първите два опита са наредените двойки различни цифри, ${V_{10}^2=10\cdot 9=90}.$ Благоприятни са двойките, в които правилната цифра е първа ($9$ двойки) или втора (също $9$ двойки). Следователно ${P=\frac{18}{90}=\frac15}.$ Отговорът е естествен: правилната цифра е с еднаква вероятност на всяко от 10-те места в реда на опитите, а за нас са благоприятни 2 от тях.

Задача 9. При белота „кварта“ се наричат четири поредни карти от една боя (например 9, 10, вале, дама купа). Подредбата на картите във всяка боя е 7, 8, 9, 10, вале, дама, поп, асо. Каква е вероятността играч да получи поне една кварта в 8-те си карти?

Решение. Във всяка боя има 5 кварти (започващи от 7, 8, 9, 10 или вале), общо ${4\cdot 5=20}.$ Раздаванията, които съдържат една определена кварта, са $C_{28}^4$ (останалите 4 карти са произволни). Но ${20\cdot C_{28}^4=409\,500}$ брои някои раздавания повече от веднъж: например ръка с 7, 8, 9, 10, вале на една боя съдържа две кварти. Затова

${P\lt\frac{20\cdot C_{28}^4}{C_{32}^8}=\frac{409\,500}{10\,518\,300}\approx 0{,}039.}$

Ако преброим внимателно (без повторно броене), раздаванията с поне една кварта са $362\,550,$ и ${P=\frac{362\,550}{10\,518\,300}\approx 0{,}034}.$ Задачата показва най-честата грешка в комбинаториката: един и същ случай да се преброи два пъти.

Задачи за упражнение

1. По колко начина могат да седнат 5 души на 5 стола в редица?

${P_5=5!=120}.$

2. Колко трицифрени числа с различни цифри могат да се запишат с цифрите 1, 2, 3, 4, 5?

${V_5^3=5\cdot 4\cdot 3=60}.$

3. По колко начина от 12 ученици могат да се изберат 4 за отбор?

Редът няма значение: ${C_{12}^4=\frac{12\cdot 11\cdot 10\cdot 9}{1\cdot 2\cdot 3\cdot 4}=495}.$

4. Колко диагонала има изпъкнал десетоъгълник?

Отсечките между 10 върха са ${C_{10}^2=45};$ 10 от тях са страни, затова диагоналите са ${45-10=35}.$

5. Колко различни думи могат да се получат от буквите на думата КАЛАЙ?

Буквата А се среща два пъти: ${\frac{5!}{2!}=\frac{120}{2}=60}.$

6. Колко са трицифрените числа, записани само с цифрите 1, 2 и 3, ако цифрите може да се повтарят?

${\overline{V}{}_3^3=3^3=27}.$

7. В кутия има 6 бели и 4 черни топки. Изваждаме едновременно 3 топки. Каква е вероятността и трите да са бели?

${P=\frac{C_6^3}{C_{10}^3}=\frac{20}{120}=\frac16}.$