Главная страница

Вступ-Комбінаторика. Комбінаторика Вступ


НазваниеКомбінаторика Вступ
АнкорВступ-Комбінаторика.doc
Дата14.03.2018
Размер93 Kb.
Формат файлаdoc
Имя файлаВступ-Комбінаторика.doc
ТипДокументы
#67005
Каталогroma_zorivchak

С этим файлом связано 33 файл(ов). Среди них: 4.jpg, СПИСОК ЛІТЕРАТУРИ.doc, dkr-difury-33gr.doc, 6.jpg, ІНСТРУКТАЖ СТУДЕНТАМ .doc, 3.jpg, 5.jpg, 1 ЛЕКЦІЯ значення історії педагогіки, зародже...doc, 4_3-4_4.docx и ещё 23 файл(а).
Показать все связанные файлы

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

Вступ
Комбінаторика або комбінаторний аналіз — розділ дискретної математики, яка вивчає комбінації і перестановку предметів, взаємне розташування частин скінченних множин предметів довільного походження, а також нескінченних множин, які задовольняють деякі умови підпорядкованості. Виникла комбінаторика у XVII ст. Але у самостійну наукову дисципліну комбінаторний аналіз сформувався лише у XX ст. Комбінаторні методи застосовуються в теорії ймовірностей, випадкових процесах, статистиці, математичному програмуванні, плануванні експериментів. Розглядаються задачі, в яких доводиться обирати ті чи інші предмети, розташовувати їх у певному порядку і знаходити серед різноманітних комбінацій найкращі. Комбінаторика тісно зв'язана з теоріями чисел, графів, скінченних автоматів. її досягнення використовуються під час планування та аналізу наукових експериментів, у лінійному та динамічному програмуванні, у математичній економіці, у системах проектування та керування, у комп'ютерних науках та інших галузях науки і техніки.

Виділяють такі проблеми комбінаторного аналізу:

1) Задачі на перелічення, в яких необхідно визначити кількість розміщень елементів скінченної множини, що задовольняють певні умови. Для розв'язку задач перелічення розроблено різноманітні методи, серед яких слід відзначити метод продуктивних функцій і метод перелічення Пойа.

  1. Задачі про існування та побудову. В задачах такого класу розглядаються питання: чи має місце визначена конфігурація частин скінченної множини з деякими властивостями; якщо така конфігурація існує, то як її побудувати. При цьому важливу роль відіграють чисельні та алгебраїчні методи.

  2. Задачі про вибір. Задачі такого типу досліджують умови, за яких можна здійснити вибір підмножини або деякої сукупності частин множини так, щоб задовольнити певні вимоги. Для розв'язку задач про вибір, крім комбінаторних методів, треба застосовувати алгебраїчний апарат.

Історія розвитку комбінаторики
Китайські рукописи 12 - 13 ст. до н. є. описували навколишню дійсність як об'єднання двох початків — чоловічого і жіночого. Вісім рисунків з трьох рядів символів зображували землю, гори, воду та інші стихії — сума перших восьми натуральних чисел (36) утілювала Всесвіт.

Легенда про китайського імператора Ію, який жив 4000 років тому, розповідає: існувала священна черепаха, на панцирі якої був зображений рисунок, що містив дев'ять чисел

4 9 2

3 5 7

8 1 6 Магічний квадрат
Додавши числа у рядках, стовпцях або діагоналях магічного квадрату, одержимо одне й те ж число — 15.

Конкретні комбінаторні задачі, які стосувалися переліку предметів або невеликих їх груп, стародавні греки розв'язували без помилок.

Існують суміжні задачі між комбінаторикою та теорією чисел. Старогрецькі філософи запропонували поняття «квадрату числа» — квадрати натуральних чисел зображувалися камінцями, як зображено нижче.

0 0 0

0 0 0 0 0

0 0 0 0 0 0 Зображення квадратів чисел
За допомогою комбінацій предметів та обчислення кількості таких комбінацій було одержано числа, які дорівнюють сумі своїх дільників, наприклад, 6=1 + 2 + 3; «дружні числа», кожне з яких дорівнює сумі дільників деякого іншого числа.

Великий розвиток у середні віки в Європі та Азії одержали різноманітні числові забобони і тлумачення, зв'язані із заміною букв відповідними числами (греки позначали числа за допомогою букв — перші 9 літер алфавіту позначали цифри від 1 до 9, наступні за ними — від 10 до 90, а останні 9 літер — числа від 100 до 900). В середні віки вчені, які називалися кабалістами, піддавали такому «аналізу» слова Біблії та інших священних книг і робили на підставі своїх досліджень пророцтва про майбутнє світу. Особливо виділялися чортова дюжина— число 13, комбінації цього числа з днями тижня та астрономічними явищами — затьмареннями або появою комет; число диявола — 666.

Поряд з кабалістами і містиками комбінаторикою у середньовіччі займалися астрологи.

Астрологія — наука, яка вивчає об'єднання планет і їх взаєморозташування між собою, — також дала поштовх для формулювання і розв'язку класичних комбінаторних задач. Астрологів цікавило питання про рух планет і їх вплив на долю людини. Особливе значення приділяли вони об'єднанням планет — зустрічам різних планет в одному знаку Зодіаку.

Астролог Бен Езра (1140 р. н. є.) підрахував кількість сполучень семи планет по дві, по три і т. д. Виявилося



де — число сполучень з п різних предметів по k.

Остаточно формулу числа сполучень одержав Леві Бен Герман у 14 ст.:

.

На початку 17 ст. цю формулу заново вивів французький математик П. Ерігон.

Велику увагу класифікації видів суджень приділяла схоластична наука. У схоластиці дивно перепліталися дослідження богословів з дослідженнями проблем, які примикають до комбінаторики, математичної логіки, теорії множин та інших сучасних розділів математики. Великими знавцями схоластичних досліджень були засновники теорії множин — Бернард Больцано та Георг Кантор. Сперечаючись про взаємовідношення членів пресвятої трійці, супідрядності ангелів, архангелів, херувимів та серафимів, схоласти були змушені розглядати різноманітні відношення порядків та ієрархії. Наприклад, загробний світ, що описаний Данте у «Божественній комедії», з його колами пекла і різними частинами чистилища і раю.

Схоласт Раймонд Лулій створив у 13 ст. машину, складену з кількох кіл, на яких були нанесені основні предикати, суб'єкти, атрибути та інші поняття схоластичної логіки. Повертаючи ці кола, він одержував різноманітні об'єднання понять і сподівався знайти з їх допомогою істину.

Розв'язуючи питання про добуток коренів будь-якого степеня, арабські алгебраїсти дійшли до формули для степеня суми двох чисел, відомою під назвою «біном Ньютона». Напевне, цю формулу знав поет и математик Омар Хайям, який жив у 11 - 12 ст. н. е. В 13 – 15 ст. н. є. таку формулу наводять у своїх роботах деякі арабські вчені.

Італієць Леонардо Ліванський, на прізвисько Фібоначчі, у своїй книзі «Liber Abaci», що видана у 1202 p., систематизував всю арифметику арабів, деякі відомості з геометрії Евкліда і додав до них результати своїх досліджень. Робота Фібоначчі містила і нові комбінаторні задачі, наприклад, про знаходження найменшої кількості гир, за допомогою яких можна одержати будь-яку цілу вагу від 1 до 40 фунтів. Розглядав Леонардо і знаходження цілих розв'язків рівнянь. Далі аналогічні задачі призвели до розв'язку задачі про кількість натуральних роз­в'язків систем рівнянь та нерівностей, яка може розглядатися як одна з фундаментальних частин комбінаторики.

Але головною заслугою Леонардо перед комбінаторикою було те, що він сформулював та розв'язав «задачу про кроликів». Ще за часів грецьких математиків були відомі дві послідовності, кожний член яких одержувався за визначеними правилами з попередніх членів — арифметична та геометрична прогресії. В задачі Леонардо з'явилася нова послідовність, кожний член якої (починаючи з третього) дорівнює сумі двох попередніх членів: ип = иn-1+ ип-2.Подібні формули одержали назву рекурентних (від латинського recurrere — повертатися). Метод рекурентних формул виявився з часом одним з найпотужніших для розв'язку комбінаторних задач.

Нарди, шашки, шахи, японські облавні шашки «го» — в цих іграх треба розглядати різноманітні з'єднання пересувних фігур, і перемагає той, хто їх краще вивчить, прорахує виграшні комбінації та уникне програшних.

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

Роботи Блеза Паскаля і Пьера Ферма (Франція, 17 ст.) поклали початок комбінаторної (дискретної) теорії ймовірностей. В 1666 р. Готфрид Вільгельм Лейбниць запропонував фундаментальні поняття комбінаторики. До області комбінаторики Лейбниць відносив і «універсальну характеристику» — математику суджень, тобто прообраз математичної логіки.

Після робіт Паскаля та Ферма, Лейбниця та Л. Ейлера можна було вже говорити про комбінаторику як про самостійну частину математики, тісно пов'язану з іншими розділами науки, як теорія ймовірностей, вчення про ряди і т. п. Наприкінці 18 ст. німецький вчений Гінденбург і його учні зробили навіть спробу вибудувати загальну теорію комбінаторного аналізу.

В 19 ст. під час дослідження з комбінаторики почали простежуватися зв'язки цієї теорії з визначниками, скінченними геометріями, групами, математичною логікою і т. д.

Однією з найбільш складних загадок у біології 20 ст. була будова «нитей життя» — молекул білка і нуклеїнових кислот. Виявилося, що молекули білка — це об'єднання кількох дов­гих ланцюгів, що складені з 20 амінокислот. Після відкриття будови ДНК виникло питання: яким чином молекули ДНК передають організму інструкції про побудову ланцюгів аміно­кислот, з яких складаються білки. Дослідження показали, що мова йде про 20 амінокислот. Американський фізик Г. Гамов сформулював задачу так: як за допомогою 4 видів нуклеотидів можна зашифрувати 20 видів амінокислот? Ця задача, як і багато інших задач генетики, має комбінаторний зміст і, зокрема, зв'язана з таким розділом комбінаторики, як кодування.

Криптографія — наука про шифрування — була відома з давніх часів; одна з областей криптографії — розшифровка письмен (текстів) древніх цивілізацій. Ключ до прочитання ієрогліфів, загублений кілька тисячоліть тому, було знову знайдено саме завдяки комбінаторним методам у читанні забутих письменностей, заснованих на спостереженнях за текстом, на зіставленні повторюваності комбінацій слів і граматичних форм. Також потрібний аналіз призначення надпису, часу та умов його складення і т. д. Типовий приклад з цієї області надає історія розшифровки клинописних надписів.
Деякі класичні задачі комбінаторики
Магічний квадрат. «Розмістити числа 1, 2, 3, 4, 5, 6, 7, 8, 9 у вигляді квадрату так, щоб сума чисел будь-якого із стовпців, рядків і діагоналей була однією й тією ж».

Магічний квадрат 3-го порядку було зображено раніше. Більш складна задача — побудова магічних квадратів 4-го порядку; доведена можливість побудови всього 880 типів таких квадратів. Існують алгоритми побудови квадратів вищих порядків і магічних кубів.

Шахові задачі. Добре відома задача про ферзі: «Поставити на шахову дошку найбільшу кількість ферзів таким чином, щоб жоден з них не зміг взяти іншого».

Розв'язок тут досить очевидний — більше 8 ферзів на дошку поставить не вдається. Оскільки ферзь б'є по горизонталі, вертикалі і діагоналі шахової дошки розміром 8x8 кліток, то більше 8 ферзів поставити неможливо, задачу можна розв'язати прямим перебором варіантів, і виявиться, що вісім ферзів можна розмістити таким чином, причому всього є 92 варіанти такого розміщення. Один з варіантів як приклад наведено на рис. В загальноприйнятих позначеннях шахових вертикалей і горизонталей вказаний варіант розміщення ферзів записується так:

(а, 6), (&, 3), (с, 5), (d, 8), 91), (Д 4), (g, 2), (А, 7).

Наведемо ще один припустимий варіант розміщення:

(а, 6), (&, 1), (с, 5), (d, 2), (є, 8), (Д 3), (g, 7), (Л, 4).

Розміщення ферзів таким чином, що жоден з них не може взяти іншого наведено на рис.

На дошці розміром п х п, де число п не повинне ділитися ані на 2, ані на 3, можна поставить по п ферзів п різноманітних кольорів таким чином, щоб ферзі одного кольору не били один одного.

Якщо розмістити шахових коней, то виявиться, що будь-який з них на дошці розміром 2x4 може бити тільки одну клітку і на цій дошці можна розмістити тільки чотирьох коней, які не б'ють один одного. На дошці 8 x 8 можна таким чином поставити тільки 8 ∙ 4 = 32 коня, оскільки дошка розміром

8 x8 кліток розбивається на вісім полів розміром 2 x 4. На дошці розміром п х п можна поставити ( nп)/2коней, що не б'ють один одного, якщо п парне, і

(п п + 1)/2 коней, якщо п непарне.

Латинські квадрати і блок-схеми. Квадрат розміром п рядків і п стовпців, складений з п літер таким чином, щоб кожна буква входила лише один раз у кожний стовпець і кожний рядок, називають латинським. Нижче зображено латинський квадрат розміром 4x4.

А В С D

В A D С

С D А В

D С В А Латинський квадрат 4x4
Якщо два латинських квадрати «накласти* один на один таким чином, щоб кожна пара букв (велика і маленька) А, В, С, Dі а, b, с, dзустрілися тільки один раз, то такі квадрати називають ортогональними.

Ортогональний латинський квадрат розміром 4x4 зображено нижче

Аb Dd Ba Сс

Bc Ca Ad Db

Cd Bb Dc Aa

DaAcCbBd. Пара ортогональних латинських квадратів

Першим задачу про ортогональні латинські квадрати розглянув Л. Ейлер (задача про «офіцерське каре»). Ця задача не має розв'язку при п = 2 і п = 6.

Теорема про представників

Нехай у деякій множині Xвиділені підмножини Х1 Х2, ..., Хп.

Для того, щоб у Xможна було обрати п різних елеменmiв-представників а1, а2, ..., ап, таких, що а1є Х1, а2є Х2, ..., апє Хп, необхідно і достатньо виконання такої умови: для кожного значення k= 1, 2, ..., п-1 об'єднання будь-яких kобраних підмножин Xповинне містити, щонайменше, kнеоднакових елементів.

Сформульована теорема про представників була доведена Ф. Холлом. Сама проблема пошуку представників має інші назви або тлумачення. Наприклад, назва «задача про селянські весілля» виникло тому, що Герман Вейль вперше сформулював подібну задачу у декілька жартівливому тоні: «В селі відносно кожного парубка і дівчини відомо, дружать вони чи ні. Якщо для будь-яких kпарубків об'єднання множин їх подруг містить, щонайменше, kдівчат, то кожний парубок може обрати собі дружину з числа своїх подруг». Тут X— множина всіх дівчат; Х1 Х2, ..., Хп— підмножини, які складаються з подруг першого, другого, ..., п-го парубка. Доводять цю теорему методом математичної індукції за кількістю парубків.

Зауважимо, що Ф. Холл довів справедливість теореми про різних представників для будь-якої системи підмножин Х1, Х2, ..., Хпмножини X, яка може містити і нескінченне число елементів. Остаточній варіант теореми Ф. Холла еквівалентний теоремі Д. Кеніга про матриці (будь-яка з теорем легко виводиться одна з одної). Теорема Кеніга стосується бульових матриць, які зустрічаються у логіці, цілочисловому програмуванні, в теорії графів і мереж. Будь-який стовпець або рядок матриці називаються її «лінією».

Теорема Д. Кеніга (про матриці). Нехай елементи прямокутної матриці складаються із нулів та одиниць. Мінімальне число ліній, які містять всі одиниці матриці, дорівнює максимальному числу q таких одиниць у матриці, серед яких не існує двох розміщених на одній лінії.

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

, .

У матриці А базисна множина одиниць позначена зірочками, вона єдина. Число qдорівнює двом, а мінімальна множина ліній, які містять всі одиниці А, не одна. Власне, існує 4 мінімальних множини ліній:

{рядок 2, рядок 1}, {стовпець 2, стовпець 3},

{рядок 1, стовпець 3}, {рядок 2, стовпець 2}.

У матриці В число qдорівнює трьом. Мінімальна множина ліній, які містять всі одиниці, одна:

{стовпець 1, стовпець 2, рядок 3}.

Базисна множина одиниць позначена зірочками, але вона не одна.

Правила суми і добутку

Правило суми. Якщо множина М — це об'єднання множин М1, М2, М3, ..., Мk, які не перетинаються попарно, тоді кількість елементів множини зв'язані співвідношенням |М| = |М1| + ... + |Mк|.

Тут |М|— кількість елементів множини М.

Нехай предмет а1можна обрати т1способами, предмет а2 — т2способами, ..., предмет акткспособами. Тоді вибір предмета а1 або а2, ..., або акможе бути зроблений т1+ т2+ ... + ткспособами.

Підкреслимо, що тут сполучник «або» вживається у розділовому вмісті, тобто вибір аi, виключає вибір будь-якого іншого предмета.

Приклад 1. З міста А у місто В вирушають 10 потягів, 5 літаків і 3 автобуси. Скількома способами одній людині можна дістатися з А до В?

За правилом суми всього існує 10 + 5 + 3 = 18 способів.

Правило добутку. Якщо М1, М2, М3, ..., Мк — скінченні множини і

М = М1 х М2 х ... х Мк — їх декартів добуток, то

|М| = | М1 х М2 х ... х Мк | = |М1| • |М2| • ... • |Мк|.

Нехай предмет а1можна обрати т1способами, предмет а2т2способами, ..., предмет акткспособами і нехай вибір предмета а1 не впливає на кількість способів вибору предметів а2, ..., ак; вибір предмета а2не впливає на кількість способів вибору предметів а1,а3, ..., акі т.д. Тоді вибір упорядкованої множини предметів (а1, а2, ..., ак) у вказаному порядку можна здійснити т1 т2 ...ткспособами.

Приклад 2. Є 17 парубків і 21 дівчина. Скільки танцювальних пар вони можуть утворити?

Спочатку оберемо парубка — це можна зробити 17 способами, після цього кожний парубок обере собі партнершу (21 спосіб). За правилом добутку вибір упорядкованої множини танцювальних пар (парубок, дівчина) складає

17 21 = 357 пар.

Складний вибір предметів

Часто у комбінаторних задачах вибір предметів здійснюється у кілька етапів, причому в деяких з них виконуються умови, за яких діють правила суми, в інших — правило добутку. Взагалі «складовий», «складний» вибір предметів, який здійснюється шляхом послідовного вибору «простих» предметів, у практичних задачах зустрічається досить часто. Зручним засобом аналізу можливостей і перебору випадків вибору є побудова кореневого дерева — кожній послідовності можливих виборів відповідає шлях, який спрямований від кореня Х0 до кінцевих вершин дерева. Кінець будь-якої з дуг першого рівня відповідає можливому результату вибору першого рівня і т. д. Таким чином, дерево будується рівень за рівнем, поки не будуть вичерпані всі можливості вибору в послідовності, яка розглядається. Кінець кожної дуги k-рівня дерева відповідає єдиній послідовності результатів перших kвиборів.

Приклад 3.Код Морзе. Скільки різних символів може бути записано кодом Морзе (•, -), якщо для їх запису використовується не більше п'яти знаків?

Існує п'ять способів вибору довжини символу: 1, 2, 3, 4 або 5 знаків. Із кореня Х0вийдуть 5 дуг: Х0Х1, Х0Х2, Х0Х3, Х0Х4, Х0Х5.

При довжині коду 1 існують 2 символи • і -, тому з вершини Х1відповідно вибору довжини символу, який дорівнює 1, проводимо дві дуги: Х1Х11 і Х1Х12.

При довжині коду, яка дорівнює 2, існують 4 символи: • •, • -, - •, - -; з вершини Х2 проводимо 4 дуги: Х2Х21, Х2Х22, Х2Х23, Х2Х24.

При довжині коду, яка дорівнює 3, маємо 8 символів: • • •, • • -, • - •, - • •, • - -, - • -, - - •, - - -. Отже, з вершини Х3проводимо 8 дуг: Х3Х31, Х3Х32, Х3Х33, Х3Х34, Х3Х35, Х3Х36, Х3Х37, Х3Х38. Аналогічно 16 символів довжини 4 і 32 символи довжини 5. Загальна кількість кінцевих вершин дорівнює 2+4+8+16+32 = 62. Це і є шукане число символів.
перейти в каталог файлов
связь с админом