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

Розділ математики, в якому вивчаються комбінаторні задачі, називається комбінаторикою.

Наприклад:

У вазі лежать 3 яблука і 2 груші – усі різних сортів. Скількома способами можна вибрати 1)один із фруктів; 2)пару з одного яблука і однієї груші?

Існує два основних закони комбінаторики – правило суми і правило добутку: якщо елемент множини А можна вибрати m способами, а після цього елемент множини В вибрати n способами, то

пару елементів множин А і В можна вибрати (m∙n) способами.

елемент множини А або В можна вибрати (m+n) способами

Розв’яжемо попередню задачу.

Одне яблуко можна вибрати m=3 способами, одну грушу можна вибрати n=2 способами.

1. Один фрукт можна вибрати m+n=3+2=5 (способами).

2. Пару фруктів можна вибрати m∙n=3∙3=6 (способами).

Існують наслідки цих законів.

Нехай А, В, … - множини n(А), n(В), … - число елементів відповідних множин.

Теорема 1. Якщо А В= , то n(А В)= n(А)+n(В).

Теорема 2. Якщо А В , то n(А В)= n(А)+n(В) - n(А В).

Теорема 3. Якщо А₁, А₂, … , А_к скінчені, то n(А₁∙ А₂∙ … ∙А_к)= n(А₁) ∙ n(А₂) ∙… ∙n(А_к).

Задача. Номери складаються з двох букв, за якими йдуть 3 цифри. Скільки номерів можна скласти із 32 букв і 10 цифр?

Розв’язання.

А – множина із 32 букв, В – множина із 10 цифр, тому n(А)=32, n(В)=10. Щоб скласти номер треба вибрати разом по одному елементу із множин А, А, В, В, В відповідно, тому маємо

n(А) ∙ n(А) ∙ n(В) ∙ n(В) ∙ n(В) = 32∙32∙10∙10∙10 = 1024000 (номерів).

Відповідь: 1024000 номерів.

Вправи.

1. Із 120 студентів 63 відвідують секцію легкої атлетики, 75 – займаються туризмом, 12 студентів не відвідують ці секції. Скільки студентів, які займаються і відвідують секцію легкої атлетики одночасно?

2. Номер складають із однієї букви та трьох цифр. Скільки номерів можна скласти з 26 букв і 10 цифр?

Відповіді:

1. 20 студентів; 2) 26000 номерів.

Поняття факторіалу: n!=1∙2∙3∙…∙( n - 1) ∙ n (n - факторіал) – добуток усіх натуральних чисел від 1 до n включно. 0!=1.

Приклад 1.

Обчисліть: 4!; 5!.

Розв’язання:

4!= 1∙2∙3∙4=24; 5!=4!∙5=24∙5=120.

Приклад 2.

Скоротіть дріб: ;

Розв’язання:

= =5040; = =15.

Приклад 3.

Скоротіть дріб: а) ; б) ; в) ; г) , n>k.

Розв’язання:

а) = ;

б) = ;

в) = ;

г) =

Приклад 4.

Розв’язати рівняння: n N.

Розв’язання:

; ;

n² + n – 30 = 0

n₁ = - 6; n₂ = 5

n₁<0

Відповідь: 5.

Самостійна робота Множини та операції над ними

В-1 В-2

1. Для даних множин А=[0;5], В=[1;6] знайдіть:

А В А В.

2. Д ано: М= , N= . Знайдіть:

M\N N\M

3. Для даних множин А=[-2;2], В=(- ), С=[0;5) знайдіть:

А В С А В С

4

У класі 35 учнів. Із них 20 навчаються у математичному гуртку, 11 – у біологічному, 10 учнів не відвідують цих гуртків. Скільки біологів цікавляться математикою?

Із 220 студентів 163 грають у шахи, 175 – у футбол, 22 студенти не грають у ці ігри. Скільки студентів одночасно грають у шахи і футбол?

.

5 .Доведіть:

(А В) С=А (В С) (А В) С=А (В С)

Відповідь:

1 .[0;6) 1. (0;5]

2. 2.

3. 3. (- )

4. 6 4. 40

5 . 5.