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

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

Правило за събиране
Ако елементът а може да бъде избран по m начина, a елементът b по n различни начина, изборът на а или b може да се извърши по m + n начина. Правилото за събиране може да се обобщи за повече от две множества. Трябва броят на всички обекти да е равен на сбора от броя им в отделните групи.

Правило за умножение
Ако елементът а може да бъде избран по m начина и при всеки избор на а елементът b може да бъде избран по n начина, то изборът на наредената двойка (а,b) може да стане по m.n начинa. Правилото за умножение може да се обобщи за намиране броя на наредени тройки обекти, наредени четворки обекти.

Пермутации на N–елемента

Определение
Пермутации от N–елемента се наричат такива съединения, във всяко от които влизат всички дадени елементи и се различават само по реда на елементите. Броят на всички възможни начини на подреждане на N–елементи т.е. броя на пермутациите от N–елемента се означава с P_n.

Формула за броя на пермутациите
P_n = 1.2.3.4....(n - 1)n Произведението 1.2.3....(n - 1).n е прието да се означава с n! и се четe ен факториел
Р_n = n!
0! = 1

Пример: По колко различни начина могат на се подредят 7 души в редица?
Решение: Р₇ = 7! = 1.2.3.4.5.6.7 = 5040

Вариации от N–елемента k-ти клас

Определение и примери
Вариациите без повторение на n елемента от k-ти клас (k < n) се наричат такива саединения всяко от които съдържа по k различни елемента от дадените n и се различават едно от друго или по елементите или по реда на елементите. Разликата между вариациите и пермутациите на елементите на някакво множество е единствено в това, че в една вариация не е задължително да участват всички елементи на множеството. Ясно е, че всяка пермутация е вид вариация, докато обратното не е вярно.

Пример: В дисциплината троен скок на световното първенство по лека атлетика участват 8 съзтезателки. По колко различни начина могат да се разпределят златният, сребърният и бронзовият метал, ако се знае, че представителката на България със сигурност ще вземе златният медал?
Решение: $V_7^2 = 7.6 = 42$

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

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

Определение и примери
Комбинации без повторение от n-елемента от k-ти клас се наричат такива съединения всяко от които съдържа по k различни елемента от дадените n и се различават едно от друго с поне 1 елемент.

Пример: В един клас има 20 ученика и 15 ученички. За изпълнение на дадена задача на класа трябва да изберат 5 ученика, от които 3 момчета и 2 момичета. Намерете по колко различни начина може да стане този избор.
Решение: $C_n^k = \frac{V_n^k}{P_k} = \frac{n.(n - 1).(n - 2)\cdots(n - k + 1)}{k(k - 1)\cdots 3.2.1} \\ C_{20}^3 = \frac{20.19.18}{1.2.3} = 1140 \\ c_{15}^2 = \frac{15.14}{1.2} = 105 \\ C_{20}^3 . C_{15}^2 = 1140.105 = 119700$ начина

Формула за броя на комбинациите
Броят на различните комбинации без повторение от n-елемента от k-ти клас се означава с $C_n^k.$
Броя на комбинациите от n-елемента от k-ти клас е:
$C_n^k = \frac{V_n^k}{P_k} = \frac{n.(n - 1).(n - 2)\cdots(n - k + 1)}{k(k - 1)\cdots 3.2.1}$

Вероятности

Определение и примери
При провеждане на някакъв експеримент (опит), който може да бъде както реален, така и абстрактен, се случват събития, които могат да бъдат множества от възможните изходи или събития.
Съвкупността от всички възможни изходи се нарича пространство.
Подмножествата на пространството се наричат събития.
Ако се знае, че след даден опит събитието ще настъпи, то се нарича сигурно (достоверно) събитие.
Ако след един опит се разбере, че събитието няма да настъпи то се нарича невъзможно събитие.
Ако събитията не могат да се предвидят се наричат случайни.
В заобикалащият ни свят има много явления и събития, които са взаимно свързани и могат да се предвидят. Изучаването на закономерностите на случайните събития е предмет на математическата наука „Теорията на вероятоностите”.
В теорията на вероятоностите събитие ще наричаме резултатът от проведен опит или наблюдение след осъществяване на някакви условия.
* Ако две събития настъпват едновременно, то те се наричат съвместими.
* Ако две събития не могат да настъпят едновременно, то те се наричат несъвместими. *Ако при един опит непременно настъпва едно от събитията Е₁, Е₂,...., Е_n, които са две по две несъвместими, и друго събитие не може да се появи, казваме, че тези събития са всичките възможни случaи (елементарни събития) – т.е. това е пълна система от несъвместими събития.
* Ако едно събитие А има n несъвместими събития и а подразделя на m частни събития (m < n), казваме, че тези m събития са благоприятни случаи на събитието.
Вероятност за настъпването на едно събитие А наричаме отношението на броя m на благоприятните случаи на А към броя n на всички възможни случаи.
Следва че: $p(A) = \frac{m}{n}$ = брой на благоприятните случаи/общ брой случаи
0 ? p(A) ? 1
При p(А) = 0 събирането А е невъзможно.
При p(А) = 1 събирането А е сигурно.
При 0 < p(А) < 1 събирането А е случайно.

Пример: В едно училище учат 400 ученици. От тях 48 са отличници по всички предмети, а 160 са отличници, но не по всичко. Намерете каква е вероятността първия срещнат ученик от това училище да се окаже пълен отличник (събитие A) и да се окаже отличник но не по всичко ( събитие B).
$p(A)= \frac{48}{400} = 0,12 \textrm{ , } \qquad \qquad \qquad \qquad \qquad \qquad p(B) = \frac{160}{400} = 0,40$

Събиране на вероятностти
Ако имаме събития А и B то тяхното обединение (сбор) на събитията А и B и се бележи с А ? B. Ако събитията А и B немогат да настъпят едновременно то те се състоят от различни екементарни събития. Такива събития се наричат несъвместими. От тук следва ако събитията А и B са несъвместими. n(A ? B) = n(A) + n(B)
*Ако събитията А и B са несъвместими, то р(A ? B) = р(A) + р(B)

Задачи

1. Колко са четирицифрените числа, в които се срещат само цифрите 1, 2, 3, 4, 5, 6 и 7 и никоя цифра не се повтаря? Решение: Първата цифра може да бъде избрана по 7 начина. Да избереме коя да е от дадените цифри,например 7. За останалите три цифри от числото имаме възможност да изберем една от цифрите 1, 2, 3, 4, 5 и 6. Сега можем да приложим резултата от предишната задача - наредена тройка цифри може да се избере от 6 цифри по 6.5.4 начина. Тогава броят на всички разглеждани четирицифрени числа е 7.6.5.4 = 840.

2. Колко прави минават през 8 точки,никои 3 от които не лежат на 1 права?
$C_8^2 = \frac{8.7}{1.2} = 28$

3. При участия в играта 6 от 49 на Спортния тотализатор играчите попълват фиш с 6 числа от 1 до 49. Колко различни фиша могат да бъдат попълнени? Решение: Тъй като редът на попълването на числата в един фиш няма значение,то вcеки фиш е една комбинация на 49 елемента от 6-ти клас. съгласно формулата броят на различните фишове е
$C_{49}^6 = \frac{49.48.47.46.45.44}{49.47.46.3.44} = 13 983 816$

4. Колко 10-цифрени числа могат да се състоят,като всяка цифра се използва веднъж? P₁₀ = n! = 10! = 1.2.3.4.5.6.7.8.9.10 = 3628800 P₉ = n! = 9! = 1.2.3.4.5.6.7.8.9 = 362880 P₁₀ - P₉ = 3628800 - 362880 = 3265920

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

6. Колко пермутации могат да се състават от: а) 4 елемента б) 5 елемента в) 7 елемента
a) P₄ = n! = 4! = 1.2.3.4 = 6.4 = 24 б) P₅ = n! = 5! = 1.2.3.4.5 = 120 в) P₇ = n! = 7! = 1.2.3.4.5.6.7 = 5040

7. Колко различни знамена могат да се направят с цветовете бяло, зелено и червено, разположени в три хоризонтални ивици?
$V_n^2 = V_n^3 = 3.(3 - 1)(3 - 2) (3 - 3 + 1) = 3.2.1.1 = 6$

8. Пресметнете броя на комбинациите:
а) $C_2^5 = \frac{5.4}{1.2} = \frac{20}{2} = 10$
б) $C_{10}^3 = \frac{10.9.8}{1.2.3} = \frac{720}{6} = 120$
в) $C_5^5 = \frac{5.4.3.2.1}{1.2.3.4.5} = 1$
г) $C_6^1 = \frac{6}{1} = 6$
д) $C_6^6 = \frac{6.5.4.3.2.1}{1.2.3.4.5.6} = 1$

9. При играта белот се раздават по 8 карти от 32 .Каква е вероятността при едно раздаване играч да получи 4 валета?
$\frac{C_{28}^4}{C_{32}^8} \approx \frac{28.27.26.25}{4!}:\frac{32.31.30.29.28.27.26.25}{8!} \approx 0,0019$

10. Каква е вероятноста при игра на белот играч да получи кварта? Тоест четри поредни карти от един вид (спатии,кари,купи или пики)?
$\frac{4.5.C_{24}^4}{C_{32}^8} \approx \frac{4.5.24.23.22.21}{4!}:\frac{32.31.30.29.28.27.26.25}{8!} \approx 0,02$

11. От колода с 52 карти са истеглени 3 карти. Каква е вероятността те да са 3, 7, А?
$\frac{4^3}{C_{52}^3} \approx \frac{64}{\frac{52.51.20}{1.2.3}} \approx 0,0029$

12. Кое от събитията е най-вероятно:
А) в играта 6 от 49 да се улучи 6
В) в играта 6 от 42 да се улучи 6
С) в играта 5 от 35 да се улучи 5?

$P(A) = \frac{1}{C_{49}^6} = \frac{1}{\frac{49.48.47.46.45.44}{6!}} = 0,0000007 \\ P(B) = \frac{1}{C_{42}^6} = \frac{1}{\frac{42.41.40.39.38.37}{6!}} = 0,000001 \\ P(C) = \frac{1}{C_{35}^5} = \frac{1}{\frac{35.34.33.32.31}{5!}} = 0,000003 \\ P(A) < P(B) < P(C) $ Р(А) < Р(В) < Р(С)

13. Колко са възможните комбинации в играта 5 от 35 на спортния тотализатор?
$C_{35}^5 = \frac{35.34.33.32.31}{5!} = 324632$

14. Иван забравил последната цифра от телефонния номер на Петър. Каква е вероятността от 2 опита Иван да набере правилния номер.
Отговор: 1/5.

Комбинации във форума за математика

Още комбинаци във форума за математика