Комбінаторний аналіз

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Зміст

1. Вступ………………………………………………………………………3
2. Основна частина:…………………………………………………………5
1. Історія виникнення комбінаторних задач…………………………...5
2. Способи розв’язання   задач………………………………………….10
• Логічний  спосіб……………………………………………………10

2.2  За допомогою  формул комбінаторики…………………………..11

3. Метод перебору……………………………………………………14
3. Розв’язання рівнянь……………………………………………………19

 

3.  Висновки………………………………………………………………….22
4. Література…………………………………………………………………23

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

І. Вступ

     Комбінаторика (Комбінаторний аналіз) — розділ математики, присвячений розв'язанню задач вибору та розташування елементів деякої, зазвичай скінченної, множини відповідно до заданих правил. Кожне таке правило визначає спосіб побудови деякої конструкції із елементів даної множини, що зветься комбінаторною конфігурацією. Тому на меті комбінаторного аналізу стоїть дослідження комбінаторних конфігурацій, алгоритмів їх побудови, оптимізація таких алгоритмів, а також розв'язання задач переліку.[ 1]

     Комбінаторика - важливий розділ математики, знання якого  необхідно представникам різноманітних  спеціальностей. З комбінаторними задачами доводиться мати справу фізикам, хімікам, біологам, лінгвістам, спеціалістам по кодам та ін. Комбінаторні методи лежать в основі рішення багатьох задач  теорії ймовірностей та її застосувань.

     Не  так давно (з 1995 року) до шкільної програми з математики включений курс «Елементи комбінаторики, теорії  ймовірностей і статистики». Комбінаторні задачі і раніше зустрічалися на сторінках підручників та інших навчальних посібників із математики, а вчителі використовували їх у практичній роботі на уроках,заняттях гуртків та в позакласних заходах (вікторини, олімпіади, ігротеки тощо), у завданнях ЗНО. Сьогодні, з огляду на актуальність теми, ця науково-дослідницька робота набуває особливого значення. Кожен учень повинен розуміти, що будь-які вміння, у тому числі й уміння розв’язувати комбінаторні задачі, слід формувати виважено й поступово, повільно ускладнюючи пропоновані задачі.

     Об’єктом  дослідження в даній роботі є комбінаторні задачі.

     Предметом дослідження – досить нескладні  задачі, які розв’язуються  за допомогою  декількох певних дій. 

     Основна мета роботи — скласти алгоритм( схему) розв’язання нескладниз задач з комбінаторики.

     Задачі, що ведуть до досягнення мети — навчитися розрізняти види сполук, розв’язувати нескладні комбінаторні задачі; формувати вміння знаходити число сполук за допомогою правил, формувати вміння аналізувати, здатність швидко адаптуватись в нестандартних умовах використовуючи життєвий досвід. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

II. Основна частина

1. Історія виникнення комбінаторних задач

     Комбінаторика - гілка математики, що вивчає комбінації та перестановки предметів, - виникла  в XVII ст. Довгий час здавалося, що комбінаторика  лежить поза основної течії розвитку математики та її застосувань. Хід справ  різко змінився після появи ЕОМ. Зараз комбінаторні методи застосовуються в теорії випадкових процесів, статистиці, математичному програмуванні, обчислювальній математиці, плануванні експериментів і т.д. В математиці комбінаторика використовується при вивченні кінцевих геометрій, комбінаторної геометрії, представлень груп, неасоціативних алгебр і т.д.

     Перша згадка про питання,що близькі до комбінаторних, зустрічається в китайських рукописах, що відносяться до XII - XIII ст. до н.е. (точно датувати ці рукописи неможливо, тому що вони в 213 р. до н.е. імператор Цин Шихуан наказав спалити всі книги, тому до нас дійшли пізніше зроблені копії). В цих книгах писалося, що усе в світі являється поєднанням двох початків - чоловічого та жіночого, які автори позначали символами ------ та --- ---. В рукописи "Же-ким" ("Книга перестановок") показані різні з'єднання цих знаків по два і по три (рис. 1). Вісім малюнків з трьох рядів символів відображали землю, гори, воду, вітер, грозу, вогонь, хмари і небо (деякі малюнки мали інше значення). Сума перших 8 натуральних чисел (тобто число 36) втілювала в уяві давніх китайців весь світ.

------ --- --- ------ --- --- ------ --- --- ------ --- ---

------ ------ --- --- --- --- ------ ------ --- --- --- ---

------ ------ ------ ------ --- --- --- --- --- --- --- ---

(Рис.1) 

 
 

        По мірі поглиблення знань знадобилось виразити і інші елементи, що входять до складу світу за допомогою тих самих знаків ------ та --- ---. Були складені 64 фігури, що складалися з п'яти рядів рисочок. Треба вважати, що автор рукопису "Же-ким" помітив подвоєння числа малюнків при додаванні одного ряду символів. Це можна розглядати як перший загальний результат комбінаторики.

     У рукописі "Же-ким" є і більш  складні малюнки. Як стверджує поданий в ній додаток, імператор Ію, котрий жив приблизно 4000 років тому назад, побачив на березі річки священну черепаху, на панцирі якої був зображений малюнок з білих і чорних кружків(мал.2)

       (4   9   2

       3   5   7

       8   1   6)

   

   (Мал.2)

     При додаванні чисел в кожному  рядку, стовпчику та по діагоналі  отримаємо одне і те саме число 15. При тому містичному поясненні, яке  надавали числам давні китайці, відкриті таблиці з такими магічними властивостями  справило невиправні враження. Рис. 2 назвали "ло-шу", і почали вважати його магічним символом і використовувати при закляттях. Тому зараз будь-яку квадратну таблицю чисел з однаковими сумами по кожному рядку, стовпчику та по діагоналі називають магічним квадратом.

     По  цим натякам можна все ж  таки судити, що певні уявлення про  комбінаторику у грецьких вчених були. Філософ Ксенократ, що жив в ІV ст.. до. н.е. підраховував кількість складів. В ІІІ ст.. до н.е. стоїк Хрисипп вважав, що кількість тверджень, отримуваних з 10 аксіом, перевищує мільйон. На думку Геппарха, із стверджуючих аксіом можна скласти 103 049 сполучень, а додавши до них заперечні, 310 952. ми не знаємо який саме зміст надавали ці філософи своїм ствердженням і як вони отримували свої результати - числа, що наводив Геппарх дуже точні, щоб вважати їх результатом грубої оцінки, і в той же час їх не можна пояснити. Напевно, у грецьких вчених були якісь, невідомі нам, правила комбінаторних розрахунків, які, скоріше всього, були невірними.

     Велику  увагу грецькі вчені приділяли  питанням, граничним між комбінаторикою та теорією чисел. Ще в VІ ст. до н.е. в школі філософа-ідеаліста і  математика Піфагора виникло твердження, що світом правлять числа, а речі лише відображення чисел (можливо, ці ідеї виникли  у Піфагора під впливом вавилонської культури). Тому, щоб пізнати світ, пафігорейці почали вивчати властивості натуральних чисел. Їхні досліди про парні і непарні числа, ділення чисел, прості і складені числа поклали основу теорії чисел (в науці буває, що невірні похідні основи дають поштовх до корисних досліджень). Як і китайці, піфагорейці надавали особливе значення числу 36 - воно було для них не тільки сумою перших 4 парних і перших 4 непарних чисел, але й сумою перших трьох кубів: 36 = 13 + 23 + 33. Символом бездоганності піфагорейці вважали бездоганні числа, що дорівнювали сумі своїх дільників, наприклад, 6 = 1 + 2 + 3, 28 = 1 + 2 + 4 + 7 + 14, а символом дружби - дружні числа, кожне з яких дорівнює сумі дільників іншого числа (наприклад, 220 і 284). Пошук таких чисел потребував комбінаторної майстерності.

     В школі Піфагора була доведена знаменита теорема про сторони прямокутного трикутника. Це викликало інтерес до представлення чисел у вигляді суми двох квадратів, до квадратних чисел 1, 4, 9, 16 і т.д. Квадрати натуральних чисел відображались при цьому геометрично. Але піфагорейці розглядали і інші конфігурації крапок, такі.Кожний трикутник отримується з попереднього збільшенням довжини його сторони на 1. Підраховуючи кількість крапок у кожному трикутнику, отримуємо послідовність трикутних чисел 1, 3, 6, 10... Ці числа можна отримати, послідовно додаваючи натуральні числа: 1, 1 + 2, 1 + 2 + 3, 1 + 2 + 3 + 4 і т.д. Так само шестикутники призводять до послідовності шестикутних чисел 1, 6, 15 ... отриманій при послідовному додаванні арифметичної прогресії 1 + 5 + 9 + ...

     В 1713 р. була опублікована книга "Мистецтво  припущень" Якоба Бернуллі, в якій вказувались формули для числа  розміщень з n елементів по k, виводились вираження для степеневих сум  та ін. Чудові досягнення в області  комбінаторики належать одному з  найбільших математиків XVIII ст., Леонарду Ейлеру, швейцарцю, що прожив майже  все життя в Росії, де він був  членом Петербурзької академії наук. Основна частина наукової роботи Ейлера присвячена математичному аналізу, в якому він проклав нові шляхи, створив цілий ряд нових областей і закінчив досліди інших областей. Але у Ейлера вистачало часу думати і про задачі, які, здавалося б, не заслуговували його уваги, - про  те, чи можна обійти мости в Кенігсберзі (нині Калінінграді) так, щоб не побувати двічі на одному і тому самому мості, чи можна поставити 36 офіцерів з 6 різних полків так, щоб у кожній шерензі  і у кожній колоні було по одному офіцеру кожного військового  звання з полку, скількома способами можна розбити число на частини і т.д. Але, дивна справа, робота про мости виявилась так званим зерном, з якого потім виросли топологія і теорія графів, задача про офіцерів виявилась зараз пов'язаною з плануванням експериментів, а методи, що використовувалися при розв'язуванні задачі про розбиття чисел, після довгого та важкого шляху розвитку перетворилась в науку про інтегральні перетворення, що використовується для розв'язання рівнянь математичної фізики.

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

     В ХІХ ст. в ході досліджень по комбінаториці  стали помічатися зв'язки цієї теорії з визначеннями кінцевими геометріями, групами вона не отримала успіху - в той час ще не було накопичено достатньої кількості важливих і, математичної логіки і т.д.[8]

                                                                                                                            
 
 
 
 
 
 
 

2. Способи розв’язання задач

  Комбінаторні  задачі – це задачі, де мова йде про  будь-які комбінації об’єктів.[1]