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

Реферат на тему:

Виконав учень 10 класу «У» середньої школи № 53.

Глухів Михайло Александрович.

р. Набережні Челны.

2002 г.

Зміст |З |3 | |комбінаторики_________________________________________ | | |Правило |4 | |суми___________________________________________________ | | |Приклади |- | |завдань____________________________________________________ | | |Правило |4 | |твори_____________________________________________ | | |Приклади |- | |завдань____________________________________________________ | | |Пересічні |5 | |безлічі________________________________________ | | |Приклади |- | |завдань____________________________________________________ | | |Кола |- | |Эйлера_____________________________________________________ | | |Розміщення без |6 | |повторень________________________________________ | | |Приклади |- | |завдань____________________________________________________ | | |Перестановки без |7 | |повторень_______________________________________ | | |Приклади |- | |завдань____________________________________________________ | | |Поєднання без |8 | |повторень__________________________________________ | | |Приклади |- | |завдань____________________________________________________ | | |Розміщення й поєднання без |9 | |повторень______________________________ | | |Приклади |- | |завдань____________________________________________________ | | |Перестановки з |9 | |повтореннями_______________________________________ | | |Приклади |- | |завдань____________________________________________________ | | |Завдання для самостійного |10 | |рішення________________________________ | | |Список використовуваної |11 | |літератури___________________________________ | |.

З комбинаторики.

Комбінаторика займається різноманітних сполуками, які можна утворити з елементів кінцевого безлічі. Деякі елементи комбінаторики були відомі у Індії ще у ІІ. до зв. е. Нидийцы вміли обраховувати числа, які називають «поєднання ». У XII в. Бхаскара підраховував деяких видів поєднань і перестановок. Припускають, що індійські вчені вивчали з'єднання перетворені на зв’язки України із застосуванням в поетику, науці про структуру вірша і поетичних творах. Наприклад, у зв’язку з підрахунком можливих поєднань ударних (довгих) і ненаголошених (коротких) складів стопи з n складів. Як наукову дисципліну, комбінаторика сформувалася XVII в. У вашій книзі «Теорія і практика арифметики «(1656 р.) французький автор А. Також присвячує сполученням і перестановкам цілу главу.

Б. Паскаль в «Трактаті про арифметическом трикутнику «й у «Трактаті про числових порядках «(1665 р.) виклав вчення про биномиальных коефіцієнти. П. Ферма знав зв’язки математичних квадратів і фігурних чисел з теорією сполук. Термін «комбінаторика «став вживатися після опублікування Лейбніцем в 1665 р. роботи «Міркування про комбинаторном мистецтві «, у якій вперше дано наукове обгрунтування теорії поєднань і перестановок. Вивченням розміщень вперше займався Я. Бернуллі у другій частині своєї книжки «Ars conjectandi «(мистецтво передбачення) в 1713 р. Сучасна символіка поєднань було запропоновано різними авторами навчальних посібників лише у XIX в.

Усі розмаїтість комбінаторних формул то, можливо виведено із двох основних тверджень, що стосуються кінцевих множин — правило суми і правило произведения.

Правило суммы.

Якщо кінцеві безлічі не перетинаються, то число елементів X U Y {чи} дорівнює сумі допомоги числа елементів безлічі X і кількості елементів безлічі Y.

Тобто, якби першої поличці стоїть X книжок, але в другий Y, то вибрати книжку з першого або ж другий полки, можна X+Y способами.

Приклади задач.

Учень має виконати практичну роботу з математиці. Йому запропонували вплинув на вибір 17 то за алгебри та 13 то за геометрії. Скількома способами може вибрати однієї теми для практичної работы?

Рішення: X=17, Y=13.

За правилом суми X U Y=17+13=30 тем.

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

Рішення: Оскільки денежно-вещевая лотерея у виборі не бере участь, чи всього 6+10=16 вариантов.

Правило произведения.

Якщо елемент X можна вибрати k способами, а елемент Y-m способами то пару (X, Y) можна вибрати k*m способами.

Тобто, якби першої поличці стоїть 5 книжок, але в другий 10, то вибрати одну книжку з першого полиці та одну з іншою можна 5*10=50 способами.

Приклади задач.

Палітурник повинен переплести 12 різних книжок на червоний, зелений і коричневі халепи. Скількома способами він це сделать?

Рішення: Є 12 книжок і трьох кольору, отже за правилом твори можливо 12*3=36 варіантів переплета.

Скільки існує пятизначных чисел, які однаково читаються зліва праворуч і справа налево?

Рішення: У цих числах остання цифра буде така сама, як й перша, а передостання — як й інша. Третя цифра буде будь-який. Це можна як XYZYX, де Y і Zбудь-які цифри, а X — не нуль. Отже за правилом твори кількість цифр однаково читающихся як зліва-направо, і справа-наліво одно 9*10*10=900 варіантів. Пересічні множества.

Та буває, що безлічі X і Y перетинаються, тоді користуються формулой[pic], де X і Y — безлічі, а [pic] - область пересечения.

Приклади задач.

20 людина знають англійської і 10 — німецький, їх 5 знають і англійська, і «німецький. Скільки Людина всего?

Відповідь: 10+20−5=25 человек.

Також часто для наочного виконання завдання застосовуються кола Эйлера. Например:

З 100 туристів, що вирушають у закордонне подорож, німецькою мовою володіють 30 людина, англійським — 28, французьким — 42. Англійським і німецьким одночасно володіють 8 людина, англійським і французьким — 10, німецькою і французькою — 5, всіма трьома мовами — 3. Скільки туристів не володіють жодним языком?

Рішення: Висловимо умова це завдання графічно. Означимо колом тих, хто знає про англійський, іншим колом — тих, хто знає про французький, і третім колом — тих, хто знає немецкий.

Всіма трьома мовами володіють три туриста, отже, у спільній частини кіл уписуємо число 3. Англійським і французькою мовою володіють 10 людина, а 3 їх володіють що й німецьким. Отже, лише англійським і французьким володіють 10−3=7 человек.

Аналогічно отримуємо, що тільки англійським і німецьким володіють 8−3=5 людина, а німецькою і французькою 5−3=2 туриста. Вносимо ці дані на відповідні части.

Визначимо тепер, скільки людина володіють тільки із перелічених мов. Німецький знають 30 людина, але 5+3+2=10 їх володіють ще й іншими мовами, отже, лише німецький знають 20 людина. Аналогічно отримуємо, що однією англійським володіють 13 людина, а одним французьким — 30 человек.

За умовою завдання усього сто туристів. 20+13+30+5+7+2+3=80 туристів знають хоча б тільки мову, отже, 20 людина не володіють жоден із даних языков.

Розміщення без повторений.

Скільки скласти телефонних номерів з 6 цифр кожен, те щоб все ігри були различны?

Це приклад завдання розміщення без повторень. Розміщуються тут 10 цифри 6. А варіанти, у яких однакові цифри перебувають у різному порядку вважаються разными.

Якщо X-множество, які з n елементів, m? n, то розміщенням без повторень з n елементів безлічі X по m називається упорядкований безліч X, що містить m елементів називається упорядкований безліч X, що містить m элементов.

Кількість всіх розміщень з n елементів по m позначають [pic] n! — n-факториал (factorial анг. множене) твір чисел натурального низки від 1 до якого або числа n n≠1*2*3*…*n 0≠1 Отже, у відповідь вышепоставленную завдання буде [pic] Завдання Скількома способами 4 юнаки можуть 4 з 6 про танець? Рішення: два юнаки що неспроможні одночасно запросити те ж дівчину. І варіанти, у яких одні й самі дівчини танцюють з різними юнаками вважаються, різними, тому: [pic] Можливо 360 вариантов.

Перестановки без повторений.

Що стосується n=m (див. розміщення без повторень) з n елементів по m називається перестановкою безлічі x.

Кількість всіх перестановок з n елементів позначають Pn.

Pn=n!

Справді при n=m:

[pic].

Приклади задач.

Скільки різних шестизначных чисел можна скласти з цифр 0, 1, 2, 3, 4,5, якщо цифри серед не повторяются?

Рішення: 1) Знайдемо кількість всіх перестановок з цих цифр: P6=6≠720 2) 0 неспроможна стояти попереду числа, тому цього числа необхідно забрати кількість перестановок, у якому 0 стоїть попереду. І це P5=5≠120.

P6-P5=720−120=600.

Квартет.

Пустуха Мартышка.

Осел,.

Козел,.

Так клишоногий Мишка.

Затіяли грати квартет.

…

Стій, братці стій! -.

Кричить Мавпа, — погодите!

Як музиці идти?

Ви ж негаразд сидите…

І, і сяк пересідали — знову музика добре не идет.

Тут пущі колишнього пішли у низ раздоры.

І споры,.

Кому як і сидеть…

Мабуть, крыловские музиканти не перепробували всіх можливі місця. Проте способів непогані і багато. Сколько?

Тут теж триває перестановка з чотирьох, отже, возможно.

P4=4≠24 варіанта перестановок.

Поєднання без повторений.

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

Будь-яке підмножина X що складається з m елементів, називається поєднанням з n елементів по m.

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

Кількість поєднань з n елементів по m позначається [pic].

[pic].

Приклади задач.

Скільки трехкнопочных комбінацій існує на кодовому замку (все три кнопки натискаються одночасно), якби ньому лише 10 цифр.

Решение:

Оскільки кнопки натискаються одночасно, то вибір цих кнопок — поєднання. Звідси можливо [pic]вариантов.

У одну людину 7 книжок з математиці, а й у другого — 9. Скількома способами можуть обміняти друг в одного дві книжки на дві книги.

Решение:

Оскільки треба порядок прямування книжок має значення, то вибір 2ух книжок — поєднання. Перша людина може вибрати 2 книжки [pic][pic] способами. Другий то вона може вибрати 2 книжки [pic]. Отже лише правилу твори можливо 21*36=756 вариантов.

При гру доміно 4 гравця ділять порівну 28 кісток. Скількома способами вони це сделать?

Перший гравець робить вибір з 28 кісток. Другий з 28−7=21 кісток, третій 14, а четвертий гравець забирає решта кістки. Отже, можливо [pic]. Розміщення і незвичні сполучення з повторениями.

Часто в завдання щодо комбінаториці зустрічаються безлічі, у яких будь-які компоненти повторюються. Наприклад: в завданнях на числа — цифри. Для завдань при розміщеннях використовується формула [pic], а поєднань [pic].

Приклади задач.

Скільки тризначних чисел можна скласти з цифр 1, 2, 3, 4, 5?

Рішення. Оскільки порядок цифр серед істотний, цифри можуть повторюватися, це будуть розміщення з повтореннями з п’яти елементів по три, які число одно [pic].

У кондитерському магазині продавалися 4 сорти пироженных: эклеры, пісочний, наполеоны і слоєні. Скількома способами можна 7 пироженных.

Рішення: Купівля залежить від цього у якому порядку вкладають куплені пироженные в коробку. Придбання будуть різними, якщо вони різняться кількістю куплених тістечок хоча самого сорти. Отже, кількість різних покупок одно числу поєднань чотирьох видів пироженных по сім — [pic].

Мавпу посадили за друкарську машинку з 45 клавішами, визначити число спроб, необхідні здобуття права вона напевно надрукувала перший рядок роману Л. Н. Толстого «Ганна Кареніна», якщо рядок містить 52 знака і повторень не будет?

Рішення: порядок літер має значення. Букви можуть повторюватися. Отже, всього є [pic] вариантов.

Перестановки з повторениями.

[pic][pic], де n-количество всіх елементів, n1, n2,…, nr-количество однакових элементов.

Приклади задач.

Скількома способами можна переставити літери слова «ананас»?

Рішення: всього літер 6. У тому числі однакові n1"а"=3, n2"н"=2, n3"с"=1. Отже, число різних перестановок одно [pic].

Завдання для самостійного решения.

Скільки перестановок можна зробити щось із літер слова «Миссисипи».

Відповідь: 2520.

Є п’ять різних стільців і сім рулонів обивочной тканини різних кольорів. Скількома способами можна здійснити оббивку стульев.

Відповідь: 16 807.

На пам’ятні сувеніри в «Поле Див» спонсори пропонують кавоварки, праски, телефонні апарати, духи. Скількома способами 9 учасників гри можуть одержати ці сувеніри? Скількома способами може бути обрані 9 предметів учасники игры?

Відповідь: 49, 220.

Скількома способами можна розставити на шахівниці 8 тур те щоб на одне з них могла бити другую?

Відповідь: 40 320.

Скільки то, можливо випадку вибору 2 олівців і трьох ручок з п’яти різних олівців та шість різних ручек?

Ответ:200.

Скільки способів роздачі карт на виборах 4 людини існує у игре.

«Вірю — не вірю» (карти лунають повністю, 36 карт).

Відповідь: [pic].

У перебігу 30 днів вересня було 12 дощових днів, 8 вітряних, 4 холодних, 5 дощових і вітряних, 3 дощових та холодних, а одного дня був і дощовим, і вітряним, і холодним. Протягом скількох днів, у вересні стояла хороша погода.

Відповідь: 15.

На фермі є 20 овець і 24 свині. Скількома способами можна вибрати одну вівцю й одне свиню? Якщо такий вибір вже зроблено, скількома способами можна зробити ще й раз?

Відповідь: 480, 437.

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

«здание»?

Відповідь: 9.

Скільки існує парних пятизначных чисел, які починаються нечетной цифрой?

Відповідь: 25 000.

У книгарню надійшли романи Ф. Купера «Прерія», «Зверобой»,.

«Шпигун», «Піонери», «Слідопит» по однаковою ціні. Скількома способами бібліотека може закупити 17 книжок на обраний чек?

Відповідь: 2985.

Список використовуваної литературы.

Савіна Л. Н., Попырев А. В. «КОМБІНАТОРИКА» видавництво Елабужский державний педагогічний інститут 1999 г.

Халамайзер А. Я. «Математика? — Цікаво!» видання автора 1989 г.

Інтернет http: internet ———————————- Якщо множин більше, наприклад 5 мов, то також складається кількість людина які знають англійську, німецький, французький тощо., віднімається кількість людина, знають 2 мови одночасно, додається по 3, віднімаються про й т.д.