Борисенко О.А. Дискретна математика

Подождите немного. Документ загружается.

Дискретна математика

Оберемо один з цих елементів, наприклад, х та розкладемо

початкову (вихідну) множину з С^' підмножинами на два класи,

один з яких містить у своїх підмножинах елемент*, а другий ні.

У першому класі елемент х присутній у всіх без винятку

підмножинах. Це означає, що він просто приєднується до к елементів,

які тепер обираються не з п + 1 елементів, як це було до розкладу на

два класи, азл (елемент х під час їх вибору відсутній). Тому кількість

підмножин у першому класі дорівнює С*.

Оскільки елемент х у другому класі відсутній, то підмножини,

які до нього належать, не містять цього елементу, хоча й без нього до

них належать к + 1 елементів, однак вони вибираються не з п + 1

елементів, аз п. Тому кількість підмножин у другому класі дорівнює

Відповідно сума підмножин першого та другого класу

я+1 >

що й доводить початкове твердження.

Теорема 3.

СІ + с

:\ = І .

1=0

Доведення. На основі теореми 2 запишемо рівності:

ґ-*к к ,

•тА-І (-~ік

і^к .

/~>к-1

*->к , 1

я ~

^п-1 >

п-2

(

"л-2

' •••'

к+2

/с+1

ЧМ

-Ч •

Оскільки С

С^Г' -1, то, після підстановки виразу для С*

вираз для С

к+2

, отримаємо:

(~*к

__ у~<к

к~\ , 1 ,

у~<к~і

г~<к __ у~>к~\

. 1 ґ->к~\

^-к+2 Т^-к

^к+І

+ + +

Ч-Г

Після

того, як підставимо коефіцієнти для С

к+

2 у попередню

йому рівність

133

Борисенко О. А.

А+2

к+2

одержимо, що

/-іА—1

/~<к—\

, .

^к +

к+2

-к+1

+ +

Потім таку ж саму операцію виконаємо для решти коефіцієнтів

безпосередньо до і в результаті отримаємо необхідну рівність,

яка доводить дану теорему.

Теорему доведено.

Теорема 4.

к к к 1 2 І 0

і=0

Доведення. На основі рівності

- С

+ і Г° = Г° =

маємо

+ г° = г

потім

+ г

= г

чі -а- + 1 ^ "•'и-і-+і ^п-к+2

і гак до одержання в кінцевому підсумку необхідного результату.

Теорему доведено.

3. Властивості винесення за дужки

Теорема 5. При кф(і, п * 0

— — Г

Доведення.

к /?!

" (и-1)!

" к\(п -к)\ к' (к-Щп-к)і'

134

Дискретна математика

Оскільки відношення

(и-1)!

(к-\)\(п-к)\

то

Теорему доведено.

Наслідок 1.

Наслідок 2.

' Г

—

І-Г"

1-1

/? /о

Теорема 6. /7ри

А Ф

0, п

к _

п-к

Доведення. Відповідно до теореми 5

и ~ , я—і '

п-к

Унаслідок теореми 1, згідно з якою

л-1

_С

Я-І'

П-к _ »

я ~ , л ~

п-к

Теорему доведено.

135

Борисенко О. А.

Лекція 24

ТРИКУТНИКИ ПАСКАЛЯ

1. Числові й символічні трикутники Паскаля

Теорема 2 з лекції 23 відома, як правило Паскаля. Воно

виражає згідно з правилами рскурсії один біноміальний коефіцієнт,

який не дорівнює одиниці, через два інших. З допомогою цього

правила можна побудувати трикутники Паскаля, як числовий

(рис. 3.1а), так і символічний (рис. 3.16).

При необмеженому продовженні трикутники Паскаля

дозволяють знаходити біноміальні коефіцієнти з будь-яким п і к, що

може в деяких випадках значно спростити процедуру їх обчислення.

/7 = 0

л= 1

1 2

1 3

1 /7 = 3

1 4

'Ч/

4 1 п

1 5 10 10 5

1 /7 = 5

Рис. 3.1а. Числовий трикутник Паскаля

с°

/7 = 0

с;>

/7=1

с°

сі

/7 = 2

с° С'

/7 = 3

С°

с'

/7 = 4

° С

сі

/7 = 5

Рис. 3.16. Символічний трикутник Паскаля

136

Дискретна математика

2. Властивості трикутників Паскаля

У рядку п, п = 0, 1,..., трикутника Паскаля стоять

коефіцієнти

, до того ж кожен коефіцієнт, крім двох крайніх, які

дорівнюють 1, дорівнює сумі двох коефіцієнтів з попереднього рядка,

які стоять над ним (див. рис. 3.1а і 3.16).

Сума біноміальних коефіцієнтів одного рядка дорівнює 2" і,

крім того, сума біноміальних коефіцієнтів, які стоять на непарних

місцях, дорівнює їх сумі на парних. У свою чергу, кожна з цих сум

дорівнює 2"~'.

Числовий трикутник відповідно до властивості симетрії

біноміальних коефіцієнтів строго симетричний відносно його

середньої лінії. Тому при використанні його для обчислення

біноміальних коефіцієнтів достатньо побудувати будь-яку одну його

половину.

3. Таблична форма трикутників Паскаля

Іноді при обчисленні С

більш зручно користуватися

трикутником Паскаля, який поданий у табличній формі (див.

табл. 3.1).

Таблиця 3.1. Трикутник Паскаля в табличній формі

Біноміальні коефіцієнти

С°

с;

1 1

СІ

1 2 1

С]

1 3 3 1

с:

4 6 4

СІ

1 5

5 1

Тут, як і раніше, усі коефіцієнти біноміального розкладу

розташовані в одному рядку і в сумі утворюють величину 2".

У той же самий час правило Паскаля реалізується шляхом

підсумовування двох біноміальних коефіцієнтів, які стоять поруч в

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

137

Борисенко О. А.

сусідньому нижньому рядку під правим біноміальним коефіцієнтом,

який підсумовується (див. табл. 3.1).

Наприклад,

'-з

С?

Це означає, що СІ - С

+ С

(правило Паскаля).

4. Знаходження біноміальних коефіцієнтів

Біноміальний коефіцієнт С

можливо знайти в трикутнику

Паскаля з допомогою теореми 4 (лекція 23). Для цього в трикутнику

знаходять коефіцієнт С

„ і потім підсумовують у верхньому рядку,

паралельному правій стороні трикутника, біноміальний коефіцієнт,

який стоїть над ним, і всі біноміальні коефіцієнти в цьому рядку, які

знаходяться зліва від цього коефіцієнта (див. рис. 3.2). Отримана

таким чином сума і буде біноміальним коефіцієнтом, який шукають.

С°

с*

с;

с°

сі

С? Сі

'-з

с°

с'

)

С,

Рис.

3.2

Символічний трикутник Паскаля

поданням

коефіцієнтів

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

Біноміальний коефіцієнт на основі вище зазначеної теореми 4

можна отримати й з допомогою трикутника Паскаля, який поданий у

табличній формі. Для цього виділяється рядок, паралельний гіпотенузі

прямокутного трикутника, який було одержано у табл. 3.1. Сума всіх

коефіцієнтів у будь-якій початковій частині цього рядка дорівнює

138

Дискретна математика

коефіцієнту паралельного знизу йому сусіднього рядка, який стоїть

під останнім коефіцієнтом цієї частини, наприклад, як це показано на

рис. 3.3.

сГ

сЛ

—^

к.

4 '

Рис. 3.3. Приклад обчислення біноміального коефіцієнта

з допомогою трикутника Паскаля

Теорема 3 (лекція 23) реалізується в трикутнику Паскаля

шляхом арифметичних операцій над сусідніми коефіцієнтами будь-

якого рядка, розташованого паралельно лівій стороні трикутника. У

цьому випадку коефіцієнт С* знаходиться в сусідньому нижньому

рядку і визначається як сума біноміального коефіцієнта, який стоїть

над ним і всіх сусідніх справа коефіцієнтів верхнього рядка

(рис. 3.1а, б).

Так, наприклад, коефіцієнт на рис. 3.16 утворюється кое-

фіцієнтами С'

и С\ верхнього рядка. При цьому коефіцієнт С\

стоїть над ним зверху, а коефіцієнт С,

- справа від коефіцієнта С\.

Відповідно коефіцієнт 3 у нижньому рядку рис. 3.1а дорівнює

сумі двох коефіцієнтів - коефіцієнту 2 у верхньому рядку й

сусідньому до нього справа коефіцієнту

у тому ж самому рядку.

Реалізація вищезгаданої теореми 3 в табличній формі

трикутника Паскаля відбувається шляхом підсумовування всіх

біноміальних коефіцієнтів, які стоять у одному й тому ж самому

стовпчику, до коефіцієнта С*",

включно. Коефіцієнт С*, який

шукають, знаходиться в сусідньому справа стовпчику в рядку, де

розташований коефіцієнт С*

_І

(див. табл. 3.1).

139

Борисенко О. А.

5. Історична довідка

Уперше опис біноміальних коефіцієнтів зустрічається в працях

давньогрецьких авторів. У 12 віці докладний опис біноміальних

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

Числовий трикутник, поданий на рис. 3.1а, уперше в Європі

запропонував Паскаль у 1653 р. За свою форму цей трикутник

отримав назву трикутника Паскаля, однак він був добре відомий

задовго до нього, наприклад, китайському математику Чжу Ші-Цзе ще

в 1303 році.

Заслугою Паскаля є також те, що він обчислив біноміальний

коефіцієнт за допомогою явної формули, яка широко

використовується й дотепер, і, крім того, він уперше дає доведення

цієї формули на базі усвідомленого їм нового на той час фунда-

ментального методу математичних доведень - методу математичної

індукції.

Користь від знань - в їх практичному застосуванні.

Конфуцій

140

Дискретна математика

Лекція 25

ОБЧИСЛЕННЯ БІНОМІАЛЬНИХ КОЕФІЦІЄНТІВ

1. Загальні положення

Задачі на обчислення кількості сполучень к об'єктів з п, тобто

значень біноміальних коефіцієнтів С

, зустрічаються досить часто на

практиці, наприклад, при кодуванні інформації. При цьому має

значення можливість їх ефективної реалізації з допомогою

спеціалізованих пристроїв. Тому поряд з уже добре відомими

способами обчислення біноміальних коефіцієнтів, які розглядались у

попередній лекції, розробляються й інші, у деяких випадках більш

ефективні, способи обчислення біноміальних коефіцієнтів, які

різняться між собою при їх реалізації надійністю, швидкодією,

апаратурними затратами, складністю.

2. Обчислення з допомогою явних формул

Найбільш просто обчислити біноміальний коефіцієнт, як це вже

розглядалося вище, можна з допомогою формул, які подаються в

такому вигляді:

" к\{п-кУ

або

гк _

" _ п(п-1)...(п-к

+ 1)

Наприклад, якщо к = 2, п = 6 , то

СІ = - ~~ = 15.

4!2! 2

3. Обчислення з допомогою рекурентних формул

Розглянутий вище метод при великих к і п потребує великої

кількості операцій множення та ділення, що створює складності для

проектування спеціалізованих обчислювальних пристроїв. Інколи для

більш ефективної реалізації таких пристроїв може бути використана

одна з рекурентних формул для біноміальних коефіцієнтів,

наприклад:

141

Борисеико О.А.

=-с

:1к*

о.

Так, при обчисленні біноміального коефіцієнта С*

буде

отримана така послідовність:

Сі = =1°.= і°±^ = 210.

4 4 3

4 3 2

4-3-2-1

Однак цей метод обчислення біноміальних коефіцієнтів, як і

попередній, використовує операції множення й ділення, тому не

завжди є достатньо ефективним при побудові спеціалізованих

пристроїв. Тому можуть бути застосовані й інші методи їх

обчислення. Деякі з них наведені нижче.

4. Обчислення біноміальних коефіцієнтів на основі

побудови числових послідовностей

На основі трикутника Паскаля нами був розроблений метод

обчислення біноміальних коефіцієнтів, який використовує тільки

операції додавання між елементами числових послідовностей, що

створюються біноміальними коефіцієнтами. Цей метод має значення

при побудові спеціалізованих пристроїв, де виконування лише

операцій додавання спрощує обчислення біноміальних коефіцієнтів,

підвищує швидкодію і надійність.

Для реалізації цього методу спочатку на першому кроці його

роботи з трикутника Паскаля береться перша послідовність

натуральних чисел 1, 2, 3, 4 ... . Елементи наступної послідовності

чисел будуються на другому кроці таким чином, що першим

елементом є 1. Другий елемент після цього отримується в результаті

додавання цієї 1 до другого елемента початкової послідовності - 2. У

результаті буде отримане число 3. Третій елемент є результатом

додавання другого елемента, тобто 3, нової послідовності до третього

елемента початкової послідовності - 3, і так буде продовжуватися до

того часу, поки не буде отримана послідовність 1, 3, 6, 10... з

+ 1

елементів. На основі цієї послідовності створюється нова - третя

послідовність 1,4,10,20..., потім ще одна, і так буде

продовжуватися, поки не буде створена послідовність чисел на кроці

142