Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

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



План:


Введення

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

Термін "комбінаторика" був введений в ужиток математичний Лейбніцем, який в 1666 опублікував свою працю "Міркування про комбінаторному мистецтві".

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


1. Приклади комбінаторних конфігурацій і завдань

Для формулювання і рішення комбінаторних завдань використовують різні моделі комбінаторних конфігурацій. Прикладами комбінаторних конфігурацій є:

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

Прикладами комбінаторних завдань є:

  1. Скількома способами можна розмістити n предметів за m скриньках так, щоб виконувалися задані обмеження?
  2. Скільки існує функцій F з m-елементного безлічі в n-елементне, що задовольняють заданим обмеженням?
  3. Скільки існує різних перестановок з 52 гральних карт?
    Відповідь: 52! (52 факторіал), тобто, 80658175170943878571660636856403766975289505440883277824000000000000 або приблизно 8,0658 10 67.
  4. При грі в кістки кидаються дві кістки, і випали окуляри складаються; скільки існує комбінацій, таких, що сума очок на верхніх гранях дорівнює дванадцяти?
    Рішення: Кожен можливий результат відповідає функції F: \ {1, 2 \} \ to \ {1, 2, 3, 4, 5, 6 \} (Аргумент функції - це номер кістки, значення - окуляри на верхній грані). Очевидно, що лише 6 +6 дає нам потрібний результат 12. Таким чином існує лише одна функція, яка ставить у відповідність 1 число 6, і 2 число 6. Або, іншими словами, існує лише одна комбінація, така, що сума очок на верхніх гранях дорівнює дванадцяти.

2. Розділи комбінаторики

2.1. Перечислительного комбінаторика

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

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

Типовим прикладом завдань даного розділу є підрахунок кількості перестановок. Інший приклад - відома Завдання про листи.


2.2. Структурна комбінаторика

До даного розділу належать деякі питання теорії графів, а також теорії матроідов.

2.3. Екстремальна комбінаторика

Прикладом цього розділу може служити наступне завдання: яка найбільша розмірність графа, що задовольняє певним властивостям.

2.4. Теорія Рамсея

Теорія Рамсея вивчає наявність регулярних структур у випадкових конфігураціях елементів. Прикладом твердження з теорії Рамсея може служити наступне:

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

У термінах структурної комбінаторики це ж твердження формулюється так:

в будь-якому графі з 6 вершинами знайдеться або кліка, або незалежне безліч розміру 3.

2.5. Імовірнісна комбінаторика

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

2.6. Топологічна комбінаторика

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

3. Відкриті проблеми

Комбінаторика, і зокрема, теорія Рамсея, містить багато відомих відкритих проблем, часом з досить нескладною формулюванням. Наприклад, невідомо, при якому найменшому N в будь-якій групі з N осіб знайдуться 5 осіб, або попарно знайомих один з одним, або попарно незнайомих (хоча відомо, що 49 людей достатньо). [1]

4. Історичний нарис

Примітки

  1. Weisstein, Eric W. Числа Рамсея - mathworld.wolfram.com / RamseyNumber.html (Англ.) на сайті Wolfram MathWorld.

Література

  • Андерсон Джеймс Дискретна математика і комбінаторика = Discrete Mathematics with Combinatorics - М .: "Вільямс", 2006. - С. 960. - ISBN 0-13-086998-8.
  • Віленкін Н.Я. Популярна комбінаторика - ilib.mccme.ru / djvu / combinatorika.htm - М .: Наука, 1975.
  • Ерош І. Л. Дискретна математика. Комбінаторика - СПб.: СПбГУАП, 2001. - 37 c.
  • Липський В. Комбінаторика для програміста - www.tnu.in.ua/study/books.php?do=file&id=3218 - М .: Світ, 1988. - 213 с.
  • Раізер Г. Дж. Комбінаторна математика - пер. з англ .. - М ., 1966.
  • Райгородська А. М. Лінійно-алгебраїчні та ймовірнісні методи в комбінаториці - www.mccme.ru/dubna/2006/notes/raygorodsky.pdf - Літня школа "Сучасна математика". - Дубна, 2006.
  • Рейнгольд Е., Нівергельт Ю., Део Н. Комбінаторні алгоритми. Теорія і практика - М .: Світ, 1980. - 476 с.
  • Ріордан Дж. Введення в комбінаторний аналіз - пер. з англ .. - М ., 1963.
  • Р. Стенлі перечислительного комбінаторика = Enumerative Combinatorics - М .: "Мир", 1990. - С. 440. - ISBN 5-03-001348-2.
  • Р. Стенлі перечислительного комбінаторика. Дерева, що виробляють функції і симетричні функції = Enumerative Combinatorics. Volume 2 - М .: "Мир", 2009. - С. 767. - ISBN 978-5-03-003476-8.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Перерахування (комбінаторика)
Правило додавання (комбінаторика)
Принцип Діріхле (комбінаторика)
© Усі права захищені
написати до нас
Рейтинг@Mail.ru