Дискретні структури Лекція 3 Елементи комбінаторики 3.1. Основні загальні правила комбінаторики 3.2. Основні види комбінацій 3.3. Біном Ньютона 3.4. Трикутник Паскаля

3.1. Основні загальні правила комбінаторики Комбінаторика – розділ дискретної математики, предметом якого є теорія скінченних множин. А, В, С,... – множини; a, b, c – їх елементи. Позначимо: N(A) – кількість елементів множини А. Якщо N(A)=n, то говорять, що А – n-множина. Чотири задачі комбінаторики: 1. Формулювання вимог до класу комбінаторних конфігурацій. 2. перелік комбінаторних обєктів, які відповідають вихідним правилам їх побудови. 3. Побудова комбінаторної конфігурації. 4. Пошук серед комбінаторних конфігурацій такої, яка б приводила деяку функцію до оптимуму.

Два основних правила комбінаторики. Правило суми. Якщо є можливість вибрати елемент з деякої множини елементів А m способами, а елемент з множини В, яка не має спільних елементів з множиною А, - k способами, то вибрати елемент множини А або множини В можна m+k способами. Іншими словами, якщо необхідно виконати якусь дію n1,n2, або nk способами, то кількість можливих способів реалізації цієї дії буде дорівнювати N=n1+n2+…+nk.

Правило добутку. Якщо 1-у дію можна здійснити n1 способами, 2-у, яка не залежить від першої, – n2 способами,..., k-ту, яка не залежить від усіх попередніх, – nk способами, то першу, другу,..., k-ту дії послідовно можна здійснити n1*n2*...*nk способами. Приклад. Скількома способами можна потрапити з п.А до п.D, якщо з А до В веде m доріг, з В до D – k доріг, з А до С – n доріг і з С до D – l доріг? Розвязання. За правилом добутку рух шляхом ABD можна здійснити mk способами, а шляхом ACD – nl способами. Згідно з правилом суми з А до D можна потрапити mk + nl способами.

3.2. Основні види комбінацій Визначення. Нехай М – n-множина, Розміщенням з n елементів по k називають будь-яку впорядковану k-підмножину множини М. Кількість розміщень з п елементів по k обчислюють за формулою: Приклад. М={1, 2, 3}, п=3, k=2, Справді, можливі розміщення такі: (1;2), (1;3), (2;1), (2;3), (3;1), (3;2) – всього шість.

Визначення. Перестановкою з n елементів називається розміщення з n елементів по n, тобто будь-яке впорядкування n-множини, яка складається з різних елементів. Щоб задати перестановку з n елементів, досить певним чином впорядкувати n -множину. Кількість перестановок з n елементів обчислюють за формулою: Зокрема, в чому можна переконатися, повернувшись до прикладу про можливі впорядкування множини М={1, 2, 3}.

Визначення. Нехай М – n-множина; Комбінацією з n елементів по k називають будь-яку k- підмножину множини М. Кількість комбінацій з n елементів по k обчислюють за формулою: Приклад. М={1, 2, 3}; n=3, k=2; Можливі комбінації такі: {1;2}, {1;3}, {2;3} – всього три. - числа називають біноміальними коефіцієнтами, оскільки вони фігурують у відомій формулі біному Ньютона.

Визначення. Нехай М – n-множина; довільне натуральне число. Розміщенням з повтореннями з n елементів по k називають будь-яку впорядковану множину вигляду елементи множини М, не обовязково різні. Кількість розміщень з повтореннями з п елементів по k обчислюють за формулою: Приклад. 1) М={1, 2}; n=2, k=3; Розміщення з повтореннями: (2,1,1), (1;2,1), (1,1,2), (1,2,2), (2,1,2), (2;2,1), (1,1,1), (2,2,2) – всього вісім. 2) М={1, 2, 3}; n=3, k=2; Розміщення з повтореннями: (1;2), (1;3), (2;1), (2;3), (3;1), (3;2), (1;1), (2;2), (3;3) – всього девять.

Визначення. Перестановкою з повтореннями з n елементів називається будь-яке впорядкування п-множини, серед елементів якої є однакові. Якщо серед елементів п-множини є n1 елементів першого типу, n2 елементів другого типу,..., nk елементів k-ого типу, причому то кількість перестановок з повтореннями з п елементів обчислюють за формулою: Приклад. М={1, 2, 2}; n=3, n1=1, n2=2, k=2; Перестановки з повтореннями: (1,2,2), (2,1,2), (2,2,1) – всього три.

Визначення. Нехай М – n-множина; довільне натуральне число. Комбінацією з повтореннями з n елементів по k називають будь-яку k-множину, де елементи множини М, не обовязково різні. Кількість комбінацій з повтореннями з п елементів по k обчислюють за формулою: Приклад. 1) М={1, 2}; n=2, k=3; Комбінації з повтореннями: {2,1,1}, {1,2,2}, {1,1,1}, {2,2,2} – всього чотири. 2) М={1, 2, 3}; n=3, k=2; Комбінації з повтореннями: {1;2}, {1;3}, {2;3}, {1;1}, {2;2}, {3;3} – всього шість.

3.3. Біном Ньютона Визначення. Біном Ньютона – це вираз вигляду Біном розкладається в суму одночленів, які є добутками деяких степенів його доданків a і b. Загально відомі формули розкладу бінома Ньютона в многочлен із степенями a і b при n=2 та 3: Розклад многочлена в загальному випадку

Приклад. Знайти розклад виразу на основі формули бінома Ньютона.

3.4. Трикутник Паскаля Трикутник Паскаля – арифметичний трикутник, утворений біноміальними коефіцієнтами. Якщо окреслити трикутник Паскаля, то вийде рівнобедрений трикутник. У цьому трикутнику на вершині і з боків стоять одиниці. Кожне число дорівнює сумі двох розташованих над ним чисел. Трикутник можна продовжувати нескінченно. Має симетрії щодо вершини.