Комбинаторика: основные правила и формулы.

КОМБИНАТОРИКА

Комбинаторика – раздел математики, который изучает задачи выбора и расположения элементов из некоторого основного множества в соответствии с заданными правилами. Формулы и  принципы  комбинаторики  используются  в  теории  вероятностей для подсчета  вероятности  случайных  событий и,  соответственно, получения законов распределения случайных величин. Это,  в  свою  очередь,  позволяет  исследовать  закономерности массовых случайных явлений, что является весьма важным для правильного понимания  статистических  закономерностей, проявляющихся в природе и технике.

 

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

Правило суммы.  Если два действия А и В взаимно исключают друг друга, причем действие А можно выполнить m способами, а В – n способами, то выполнить одно любое из этих действий (либо А, либо В) можно n + m  способами.

 

Пример 1.

В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить одного дежурного?

Решение

Дежурным можно назначить либо мальчика, либо девочку, т.е. дежурным может быть любой из 16 мальчиков, либо любая из 10 девочек.

По правилу суммы получаем, что одного дежурного можно назначить 16+10=26 способами.

 

Правило произведения.  Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n₁ способами, второе действие n₂ способами, третье – n₃ способами и так до k-го действия, которое можно выполнить n_k  способами, то все k действий вместе могут быть выполнены:

способами.

Пример 2.

В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить двух дежурных?

Решение

Первым дежурным можно назначить либо мальчика, либо девочку. Т.к. в классе учится 16 мальчиков и 10 девочек, то назначить первого дежурного можно 16+10=26 способами.

После того, как мы выбрали первого дежурного, второго мы можем выбрать из оставшихся 25 человек, т.е. 25-ю способами.

По теореме умножения двое дежурных могут быть выбраны 26*25=650 способами.

 Сочетания без повторений. Сочетания с повторениями

 Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из n различных предметов?

Пример 3.

Необходимо выбрать в подарок 4 из 10 имеющихся различных книг. Сколькими способами можно это сделать?

Решение

Нам из 10 книг нужно выбрать 4, причем порядок выбора не имеет значения. Таким образом, нужно найти число сочетаний из 10 элементов по 4:

.

 Рассмотрим задачу о числе сочетаний с повторениями: имеется по r одинаковых предметов каждого из n различных типов; сколькими способами можно выбрать m () из этих (n*r) предметов?

.

Пример 4.

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

Решение

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

.

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

 Классической задачей комбинаторики является задача о числе размещений без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?

 

Пример 5.

В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии. Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?

Решение.

В  данной  задаче мы не просто выбираем фотографии, а размещаем их на определенных страницах газеты, причем каждая страница газеты должна содержать не более одной фотографии. Таким  образом,  задача сводится к классической задаче об определении числа размещений без повторений из 12 элементов по 4 элемента:

Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.

 

Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n предметов, среди которых есть одинаковые?

Пример 6.

У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих штампов нанести на все книги пятизначные номера– составить каталог. Сколько различных пятизначных номеров может составить мальчик?

Решение

Можно  считать,  что  опыт  состоит  в 5-кратном выборе  с возращением одной из 3 цифр (1, 3, 7). Таким образом,  число  пятизначных  номеров  определяется  числом  размещений с повторениями из 3 элементов по 5:

.

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

 Классической задачей комбинаторики является задача о числе перестановок без повторения, содержание которой можно выразить вопросом: сколькими способами можно разместить n различных предметов на n различных местах?

Пример 7.

Сколько можно составить четырехбуквенных «слов» из букв слова«брак»?

Решение

Генеральной  совокупностью  являются 4  буквы слова  «брак» (б, р, а, к). Число  «слов» определяется перестановками этих 4 букв, т. е.

Для случая, когда среди выбираемых n элементов есть одинаковые (выборка с возвращением), задачу о числе перестановок с повторениями можно выразить вопросом: сколькими способами можно переставить n предметов, расположенных на n различных местах, если среди n предметов имеются k различных типов (k < n), т. е. есть одинаковые предметы.

Пример 8.

Сколько разных буквосочетаний можно сделать из букв слова «Миссисипи»?

Решение

Здесь 1 буква  «м», 4 буквы «и», 3 буквы «c» и 1 буква  «п», всего 9 букв. Следовательно, число перестановок с повторениями равно

ОПОРНЫЙ КОНСПЕКТ ПО РАЗДЕЛУ «КОМБИНАТОРИКА»

Комбинаторика | это… Что такое Комбинаторика?

Комбинато́рика (Комбинаторный анализ) — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка).

Комбинаторика связана со многими другими областями математики — алгеброй, геометрией, теорией вероятностей и имеет широкий спектр применения в различных областях знаний (например в генетике, информатике, статистической физике).

Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».

Иногда под комбинаторикой понимают более обширный раздел дискретной математики, включающий, в частности, теорию графов.

Содержание 1 Примеры комбинаторных конфигураций и задач 2 Разделы комбинаторики 2.1 Перечислительная комбинаторика 2.2 Структурная комбинаторика 2.3 Экстремальная комбинаторика 2.4 Теория Рамсея 2.5 Вероятностная комбинаторика 2.6 Топологическая комбинаторика 2.7 Инфинитарная комбинаторика 3 Открытые проблемы 4 Исторический очерк 5 См. также 6 Примечания 7 Литература 8 Ссылки

Примеры комбинаторных конфигураций и задач

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

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

Примерами комбинаторных задач являются:

1. Сколькими способами можно разместить n предметов по m ящикам так, чтобы выполнялись заданные ограничения?
2. Сколько существует функций из m-элементного множества в n-элементное, удовлетворяющих заданным ограничениям?
3. Сколько существует различных перестановок из 52 игральных карт?

   Ответ: 52! (52 факториал), то есть, 80658175170943878571660636856403766975289505440883277824000000000000 или примерно 8,0658 × 10⁶⁷.

4. При игре в кости бросаются две кости, и выпавшие очки складываются; сколько существует комбинаций, таких, что сумма очков на верхних гранях равна двенадцати?

   Решение: Каждый возможный исход соответствует функции (аргумент функции — это номер кости, значение — очки на верхней грани). Очевидно, что лишь 6+6 даёт нам нужный результат 12. Таким образом существует лишь одна функция, ставящая в соответствие 1 число 6, и 2 число 6. Или, другими словами, существует всего одна комбинация, такая, что сумма очков на верхних гранях равна двенадцати.

Разделы комбинаторики

Перечислительная комбинаторика

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

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

Типичным примером задач данного раздела является подсчёт количества перестановок. Другой пример — известная Задача о письмах.

Структурная комбинаторика

К данному разделу относятся некоторые вопросы теории графов, а также теории матроидов.

Экстремальная комбинаторика

Примером этого раздела может служить следующая задача: какова наибольшая размерность графа, удовлетворяющего определённым свойствам.

Теория Рамсея

Основная статья: Теория Рамсея

Теория Рамсея изучает наличие регулярных структур в случайных конфигурациях элементов. Примером утверждения из теории Рамсея может служить следующее:

в группе из 6 человек всегда можно найти трёх человек, которые либо попарно знакомы друг с другом, либо попарно незнакомы.

В терминах структурной комбинаторики это же утверждение формулируется так:

в любом графе с 6 вершинами найдётся либо клика, либо независимое множество размера 3.

Вероятностная комбинаторика

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

Топологическая комбинаторика

Топологическая комбинаторика (англ.) применяет идеи и методы комбинаторики в топологии, при изучении дерева принятия решений, частично упорядоченных множеств, раскрасок графа и др.

Инфинитарная комбинаторика

Инфинитарная комбинаторика (англ.) — применение идей и методов комбинаторики к бесконечным (в том числе, несчётным) множествам.

Открытые проблемы

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

Исторический очерк

Основная статья: История комбинаторики

См. также

• Комбинаторная оптимизация
• Теория вероятностей

Примечания

1. ↑ Weisstein, Eric W. Числа Рамсея (англ.) на сайте Wolfram MathWorld.

Литература

• Андерсон Джеймс. Дискретная математика и комбинаторика = Discrete Mathematics with Combinatorics. — М.: «Вильямс», 2006.  — С. 960. — ISBN 0-13-086998-8
• Виленкин Н.Я. Популярная комбинаторика. — М.: Наука, 1975.
• Ерош И. Л. Дискретная математика. Комбинаторика — СПб.: СПбГУАП, 2001. — 37 c.
• Липский В. Комбинаторика для программиста. — М.: Мир, 1988. — 213 с.
• Раизер Г. Дж. Комбинаторная математика. — пер. с англ. — М., 1966.
• Райгородский А. М. Линейно-алгебраические и вероятностные методы в комбинаторике. — Летняя школа «Современная математика». — Дубна, 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

Ссылки

• Теория вероятностей. 3. Элементы комбинаторики
• Белешко Д. Комбинаторика. 2004.

большой список — Почему важно изучать комбинаторику?

спросил 9 лет, 10 месяцев назад

Изменено 3 года, 7 месяцев назад

Просмотрено 27 тысяч раз

$\begingroup$

У меня был разговор с моим другом Саяном Мукерджи о том, почему нам нужно изучать комбинаторику, которая, по общему признанию, не является нашим любимым предметом, потому что мы видим очень мало мотивации для ее изучения (я не говорю, что не существует мотивации для ее изучения, просто я его не нашел).

Вот некоторые из «использований» комбинаторики, которые мы могли бы придумать:

1. Подсчет — количество способов, которыми мы можем выполнить конечную последовательность операций, и способов расположения или выбора объектов. Например, количество способов, которыми мы можем выбрать $k$ нечетных и четных элементов из множества $S=\{1,2,\dots, 2n\}$ так, чтобы в секция.

2. Рисование биекций. Классическая задача о звездах и полосах дает нам ключевые идеи для подсчета числа интегральных решений уравнений вида $x_1+x_2+\dots x_n=k$.

3. Семь мостов Кенигсберга, которые пленили меня в детстве.

Я воздержался от упоминания рекурсий и генерирующих функций, так как считаю их скорее инструментами.

Но я ищу больше мотивации; подсчет, как описано в задачах, кажется верхушкой айсберга, и я буду признателен за дополнительные примеры, в которых комбинаторика и теория графов могут быть мощными инструментами. Можно, пожалуйста, список применений комбинаторики? Я не ищу применения в промышленности, только чистая математика.

Не обязательно, чтобы ответы были представлены на уровне средней школы; дополнительную информацию, безусловно, будет интересно пересмотреть!

• комбинаторика
• большой список
• мотивация

$\endgroup$

6

$\begingroup$

По запросу вот список приложений комбинаторики к другим темам чистой математики.

• Подсчет широко используется в оригинальном доказательстве теоремы Чебышева, которое вы можете найти в главе 5 (бесплатная онлайн-версия) этой книги. Теорема Чебышева — первая часть теоремы о простых числах, глубокого результата аналитической теории чисел.

• В теории групп принцип сортировки используется, чтобы показать, что каждый элемент конечной группы имеет порядок. Можно утверждать, что доказательство того, что каждая конечная область целостности является полем, вытекает из аналогичной логики.

• Здесь дается доказательство теоремы Брауэра о неподвижной точке с использованием принципа сортировки и леммы Шпернера.

• ОБНОВЛЕНИЕ: Графики в теории конечных групп. Я знаю несколько примеров, где графы появляются в теории конечных групп: графов простых чисел , графов степеней символов и коммутирующих графов . Графы простых чисел (о которых я написал несколько ответов MSE, например, $[1]$,$[2]$) относятся к набору порядков элементов в конечной группе, графы степеней символов связаны со степенями неприводимых символов группы. , а коммутирующие графы показывают, какие элементы коммутируют с какими другими элементами. $$$$ В большинстве случаев применение теории графов к теории конечных групп лингвистический — то есть эти графы естественным образом возникают из вопросов теории групп, которые лучше всего формулировать с использованием языка теории графов. Другими словами, теоремы из теории графов обычно не используются для решения задач теории конечных групп, даже когда вышеупомянутые графы являются предметом исследования. Однако иногда теорию графов можно применять и более непосредственно, как это видно, например, из этой моей статьи.

$\endgroup$

1

$\begingroup$

Мы можем задаться вопросом: насколько важна «важность»? 🙂

Но для более серьезного общего ответа на опасения, которые, возможно, лежат в основе вашего вопроса, стоит прочитать эту замечательную статью сэра Тимоти Гауэрса, в которой он говорит о двух культурах или стилях математики, решении задач и теории. здание, иллюстрируемое, как может показаться на первый взгляд, напр. комбинаторики против теоретиков топоса (последний — мой пример). Гауэрс продолжает защищать математический интерес и важность комбинаторики и явно стремится «опровергнуть предположение, что предмет комбинаторики имеет очень слабую структуру и состоит только из большого количества задач».

$\endgroup$

$\begingroup$

Весь современный мир опирается на комбинаторные алгоритмы. Если вы хотите сделать программу быстрее, вам нужна комбинаторика. Если вы хотите понять современное программирование, вам нужна комбинаторика. Без комбинаторики некоторым программам, которые сейчас выполняются за доли секунды, потребовались бы недели.

Связь с мобильным телефоном — коды исправления ошибок, вейвлет и оптимизация Фурье.
Программирование игр — оптимизация полигонов
Этот веб-сайт — иерархия комментариев

Везде, где у вас есть сотня или более фрагментов данных — а это почти каждый сайт, магазин, программа, место или проект — скорее всего, используется какое-то комбинаторное усовершенствование. Особенно в программах. Если быстро, то комбинаторика выручает.

$\endgroup$

2

$\begingroup$

Другим важным приложением комбинаторики является теория представлений, симметрические функции и изучение многообразий с большим количеством симметрий (грассманианы, флаговые многообразия, торические многообразия, симметричные многообразия, сферические многообразия).

В общем, объекты с достаточной симметрией часто могут быть описаны дискретными (часто конечными) данными. Комбинаторика вступает в игру для параметризации данных и, в более общем смысле, потому что отношения между объектами часто описываются в терминах комбинаторики данных.

В качестве простого примера предположим, что вы хотите изучить $k$-мерные подпространства $n$-мерного векторного пространства $V$. Один из способов понять такое подпространство $W$ — рассмотреть «флаг» $V$, представляющий собой последовательность подпространств $$0 = V_0 \subset V_1 \subset \dots \subset V_i \subset \dots \subset V_n = V,$$ с $\dim(V_i) = i$. Вы можете разделить различные подпространства $W$ на основе слабо возрастающей последовательности чисел $$0 = \dim(W \cap V_0) \leq \dim(W \cap V_1) \leq \dots \leq \dim(W \cap V_i) \leq \dots \leq \dim(W \cap V_n) = k,$$ с тем ограничением, что на каждом этапе размерность может увеличиваться только на 1 или оставаться неизменной. Эквивалентный способ описания положения $W$ относительно флага состоит в том, чтобы задать последовательность длины $n$, состоящую из $k$ единиц и $n-k$ нулей, где $1$ стоит на $i$-й позиции. именно тогда, когда $\dim(W \cap V_i) > \dim(W \cap V_{i-1})$.

Простое наблюдение состоит в том, что количество различных «ячеек», на которые вы разделили подпространства, равно $n \choose k$, так как это подсчитывает количество таких строк из нулей и единиц. Это только начало богатого взаимодействия комбинаторики и геометрии. Мораль заключается в том, что если вы хотите изучить объект с симметриями, вы, скорее всего, встретите на своем пути какую-нибудь интересную комбинаторику.

$\endgroup$

$\begingroup$

Вы пропустили статистику. Если вы имеете дело с конечным набором возможных событий, многие статистические вопросы сводятся к комбинаторике. Если вы, например. есть $n$ случайных величин $X_n$ с конечными областями и вы хотите найти распределение $X_1+\ldots+X-n$, вам нужно выяснить, каким образом возможные результаты $X_1,\ldots,X_n$ могут суммироваться до определенного значения.

Многие школьные комбинаторики делаются с учетом таких приложений, то есть печально известного

.

Вы выбираете то-то и то-то много предметов из урны, содержащей то-то и то-то какова вероятность того, что вы выбрали предметы с некоторым свойством выбора

$\endgroup$

$\begingroup$

Я хотел бы упомянуть о рекурсиях и генерирующих функциях ( инструменты , на которые вы ссылаетесь). Рекуррентные соотношения (или разностных уравнений ) (более или менее) эквивалентны дифференциальным уравнениям в физике или любой другой области науки. Чтобы примерно понять разностные уравнения, они определены в целочисленной области, тогда как дифференциальные уравнения — в реальной области (разница гораздо более фундаментальна, чем это, поскольку дифференциальное уравнение также может быть определено в целочисленной области, вы можете найти это).

Уравнение рекурсии — это функциональное уравнение любой системы, помогающей в перечислении . Например, каталонские числа имеют около 150 различных применений (обсуждается в книге Ричарда П. Стэнли «Перечислительная комбинаторика »), есть даже полный том о каталонских числах, написанный Томасом Коши.

Генерация функций — прекрасный инструмент для решения повторяющихся ситуаций. Это прекрасный математический прием для нахождения уравнения в замкнутой форме для рекурсивных соотношений. Если вы студент компьютерных наук (или программист), вам вряд ли понадобятся эти инструменты.

Если вы специализируетесь на компьютерных науках (как я предполагаю), вам редко понадобятся эти инструменты (то есть G.F.), но уравнения рекурсии — это то, от чего вы никогда не убежите, и к тому же это чертовски весело!!!

$\endgroup$

$\begingroup$

Комбинаторика оказалась очень важной для теории групп и вероятностей. Это также актуально для топологии, анализа и т. д.

$\endgroup$

образование — Что я должен изучать после вводной комбинаторики?

Задавать вопрос

спросил 4 года 10 месяцев назад

Изменено 4 года, 9 месяцев назад

Просмотрено 530 раз

$\begingroup$

Итак, я учусь в старшей школе, и мой первоначальный план состоял в том, чтобы специализироваться на информатике и дополнительно на математике. Недавно я обнаружил большой интерес к математике и подумываю о двойной специализации в области компьютерных наук и математики. В настоящее время я изучаю Алгебру 2 и планирую пройти предварительное исчисление летом, чтобы быть в курсе всех математических курсов, которые предлагает моя школа. Кроме того, мне разрешили самостоятельно заниматься дискретной математикой в ​​следующем году, и в настоящее время я прохожу вводный онлайн-курс по комбинаторике. Я почти уверен, что закончу курс комбинаторики в течение следующего месяца или около того, что приводит меня к моему вопросу: что мне следует изучать дальше, чтобы дополнить знания по комбинаторике? Я изучаю вещи в невыгодном порядке?

• комбинаторика
• образование

$\endgroup$

5

$\begingroup$

Вот как я прошел курс «Статистика и вероятность» на уровне A (выпуск 2017 г., h3 Math + h3 FMath, Сингапур), который, на мой взгляд, имеет очень хороший ход:

1. Введение в комбинаторику
2. Введение в вероятность
3. Дискретный RV (Intro, Binom, Geo, Poisson)
4. Continuous RV (Intro, Normal, Uniform, Expo)
5. Процесс Пуассона (Poisson+Expo)
6. Проверка гипотез + доверительные интервалы (Z, T, хи-квадрат)

Возможно, вам захочется освоить чистую математику:

До (3): Серии и последовательности; приемы суммирования; Рекуррентные отношения (линейные 1-го и 2-го порядка)

До (4): Исчисление с одной переменной

Хорошо иметь, но не очень нужно: Введение в линейную алгебру

$\endgroup$

4

$\begingroup$

Прежде всего убедитесь, что вы владеете комбинаторикой на 100%, потому что комбинаторика сама по себе широко используется в программировании и необходима для изучения вероятности, которая также широко используется в программировании.