5.3. Біномні коефіцієнти

Кількість сполучень C(m,n) - це кількість різноманітних n-елементних підмножин у m-елементної множини. Числа C(m,n) зустрічаються у формулах розв'язання багатьох комбінаторних задач. Дійсно, роздивимося таку типову схему міркувань при розв'язанні комбінаторної задачі. Нехай потрібно визначити кількість підмножин m-елементної множини, що задовольняє деякій умові. Розіб'ємо задачу на підзадачі: Роздивимося окремо 1-елементні підмножини, 2-елементні і т.д., а потім складемо отримані результати. На щастя, числа C(m,n) володіють цілим рядом властивостей, аналізованих у цьому розділі, що допомагвє при обчисленнях.

5.3.1. Елементарна тотожність

Основна формула для кількості сполучень

дозволяє одержати таку просту тотожність.

Теорема

1. C(m,n) = C(m,m-n).

2. C(m,n) = C(m-1,n) + C(m-1,n-1).

3. C(n,i) C(i,m) = C(n,m) C(n-m,i-m).

Доведення

5.3.2. Біном Ньютона

Кількість сполучень C(n,m) називаються також біномними коефіцієнтами. Зміст цієї назви встановлюється такою теоремою, відомою також як формула бінома Ньютона.

Теорема

Розглянемо доведення за індукцією. База, m=1:

Індукційний перехід:

Висновок

Доведення

Висновок

Доведення

.

5.3.3. Властивості біномних коефіцієнтів

Біномні коефіцієнти мають цілий ряд чудових властивостей.

Теорема

Доведення

1. Розглянемо послідовність чисел 1, ..., m. Спочатку всі підмножини довжини 0, потім усі підмножини довжини 1 і т.д. Існує C(m,n) підмножин потужності n, і кажна з них має довжину n, таким чином, усього в цій послідовності чисел. З іншого боку, кожне число х входить у цю послідовність разом, а усього чисел m.

2. C(n+m, k) - це кількість способів вибрати k предметів із m+n предметів. Предмети можна вибирати в два прийоми. Спочатку вибрати i предметів із перших m предметів, а потім вибрати відсутні k-i предметів із тих n предметів, що залишилися. Звідси загальна кількість способів вибрати k предметів складає

Із другої теореми ( розділ 5.3.1) випливає ефективний спосіб рекурентного обчислення значень біномних коефіцієнтів, що можна уявити в графічній формі, відомої як трикутник Паскаля.

1

1. 1

1 2 1

1 3 3 1

1 4 6 4 1

. . . . . .

У цьому рівнобедреному трикутнику кожне число (крім одиниць на бічних сторонах) є сумою двох чисел, що стоять над ним. Кількість сполучень C(m,n) знаходиться в (m+1)-му ряду на (n+1)-му місці.

Задачі

1. У ряду зали для глядачів 15 крісел. Скількома способами можна розмістити на них 15 чоловік?

2. Скількома способами можна розфарбувати повний граф на 6-ти вершинах шістьма кольорами? (Два способи вважаються різними, якщо деяка вершина при однім способі має один колір, а при іншому способі - інший.)

3. З квадратної матриці розміром 10х10 вибираються 10 елементів так, щоб ніякі два з них не належали до однієї лінії. Скільки таких наборів по 10 елементів можна скласти?

4. Десять співробітників необхідно розподілити на 6-ти робочих місцях. Відомо, що кожний співробітник може працювати на кожному робочому місці. Скількома способами можна здійснити призначення?

5. На трьох комп'ютерах необхідно вирішити три задачі , причому кожна задача може розв'язуватися на будь-якому комп'ютері. Скількома способами можна направити задачі на розв'язок?

6. В дитячій садок надійшло 5 нових дітей, яких треба розподілити в 7 груп, причому в одну групу - не більш однієї дитини. Скільки можливостей розподілу по групах існує?

7. Із 19 запитань потрібно скласти екзаменаційні квитки, причому в кожний квиток вписувати тільки два запитання. Скільки квитків можна скласти?

8. У виразі розкрили дужки і навели подібні члени. Який коефіцієнт буде стояти біля виразу ?

9. Чому дорівнює сума ?

10. Чому дорівнює сума ?

11. У множині з 10 елементів зафіксовані чотири властивості , якими можуть володіти або не володіти елементи множини. Як за допомогою методу включення-виключення описати ті елементи, в яких немає жодного з даних властивостей?

Предметний покажчик

А

Автомат

гомоморфізм, 58

комбінаційний, 55

Алгебра

k-значної логіки, 44

логіки, 44

Алгоритм

Дейкстри, 40

Форда - Фалкерсона, 37

Б

Біном Ньютона, 92

Біномні коефіцієнти, 92

В

Вектор

вимірність, 12

довжина, 12

компонента, 12

координата, 12

Вершина

ізольована, 25

суміжна, 24

тупикова, 25

Відношення

антирефлексивне, 15

антисиметричне, 15

еквівалентності, 16

інцидентності, 22

одномісне, 13

рефлексивне, 15

симетричне, 15

транзитивне, 15

Відображення

бієктивне, 18

ін'єктивне, 18

рівні, 18

сюр'єктивне, 18

функціональне, 17

Відповідність, 17

Включення строге, 7

Г

Граф

двочастковий, 18

Ейлера, 31

ізоморфний, 27

неорієнтований, 25

частковий, 23

Графа

автоморфізм, 27

вершини, 22

діаметр, 30

зв'язність, 26

радіус, 30

центр, 30

Д

Двочастковий граф

відображення, 18

Декартов добуток множин, 14

Диз'юнкція, 46

Довжина шляху, 23

Додавання по модулю два, 46

Досконала нормальна форма

диз'юнктивна, 50

кон'юнктивна, 50

Дуга, 22

З

Завдання бінарних відно- шень, 14

Способи завдання функцій, 20

Звуження, 14

І

Імплікація, 46

Інверсій кількість, 88

Інверсія, 88

Інцидентність дуг і вершин, 24

К

Кардинальне число, 7

Класи розбиття, 10

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

числа, 83

обчислення, 83

конфігурації, 84

Контекстно-вільна

граматика,79

Контур елементарний, 23

Кон'юнкція, 47

Л

Ланцюг Ейлера, 31

Лінгвістика, 77

М

Математична лінгвістика, 77

Матриця

інцидентності, 24

Карно, 51

Мережа, 32

Мережі

початок, 40

стік, 40

Методи композиції, 61

Мінімізація функцій, 50

Множин

доповнення, 9

об'єднання, 8

перетинання, 8

рівність, 8

різниця, 9

Множина

внутрішньої устале-

ності, 30

злічена, 7

зовнішньої устале-

ності, 30

нескінченна, 7

розбивки, 10

цілком упорядкована, 16

частково упорядкована, 16

m-элементна, 6

Множини

взаємовиключальні, 9

рівнопотужні, 7

Мультимножина, 7

Н

Неістотна змінна, 44

О

Ознака, 13

Орграф, 19

П

Пари упорядкованості, 12

Перестановок кількість, 85

Перетворення, 19

Перетин простий, 37

Петля, 23

Підграф, 23

Підстановка

обернена, 87

тотожна, 87

Підстановки

одноциклові, 19

тотожні, 19

цикл, 88

Порожня множина, 7

Порядок

нестрогий, 16

строгий, 16

Потік, 36

Потоку величина, 36

Потужність

злічена, 7

кінцева, 7

Правила

виведення, 74

склеювання, 50

Пропускна спроможність, 36

Р

Ребро

перетину обернене, 37

перетину пряме, 37

Розміщень кількість

без повторень, 87

С

Семіотика, 77

Скінченність графів, 24

Складність

часова, 83

ємнісна, 83

Сполучень кількість

з повтореннями, 86

Стірлінга формула, 86

Стрілка Пірса, 46

Суміжності матриця, 24

Сусідні вирази, 51

Т

Терми, 75

Транзитивне замикання, 15

Трикутник Паскаля, 94

Ф

Фактор - множини, 11

Формули, 75

Функція, 17

Х

Хроматичне число, 29

Ц

Цикл Гамільтона, 31

Цикломатичне число, 29

Ш

Шлях простий, 23

елементарний, 23

Штрих Шеффера, 46

94