Справочник от Автор24
Найди эксперта для помощи в учебе
Найти эксперта
+2

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

Замечание 1

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

Основные элементы комбинаторики, используемые при решении комбинаторных задач, таковы:

  1. Правила суммы и произведения;
  2. Перестановки без повторений;
  3. Размещения без повторений;
  4. Сочетания без повторений;
  5. Перестановки с повторениями;
  6. Размещения с повторениями;
  7. Сочетания с повторениями.

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

Если элемент a множества $A$ можно выбрать $m$ способами и при каждом из этих выборов элемент $b$ множества $B$ можно выбрать $n$ способами, то упорядоченную пару ($a$;$b$) можно выбрать $m$•$n$ способами.

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

Если элемент $a$ из множества $A$ можно выбрать $m$ способами, а элемент $b$ из множества $B$ можно выбрать $n$ способами, то число способов, которыми можно осуществить выбор хотя бы одного элемента $a$ или $b$, равно сумме $m$+$n$.

Предполагается, что выборы $a$ и $b$ взаимно исключительны, то есть ни один из способов выбора элемента a не совпадает со способом выбора элемента $b$. При наличии таких совпадений результат выбора будет равен $m$+$n$-$p$,где $p$-количество совпадений.

Замечание 2

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

При выборе элементов по правилу суммы используется соединитель "или"' (выбираем элемент из первого конечного множества, или из второго, или из третьего и т.д.).

При образовании пары (тройки, четверки и т.д.) элементов по правилу произведения используется соединитель "и"' (из первого множества выбираем первый элемент и к нему присоединяем второй элемент из второго множества — образуется пара, и к паре присоединяем третий элемент из третьего множества — образуется тройка и т.д.).

«Комбинаторика» 👇
Помощь эксперта по теме работы
Найти эксперта
Решение задач от ИИ за 2 минуты
Решить задачу
Найди решение своей задачи среди 1 000 000 ответов
Найти

Количество перестановок без повторений

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

Например, из двухэлементного множества $M2$={$a$,$b$} можно образовать два упорядоченных двухэлементных множества: {$a$,$b$} или {$b$,$a$}.

Формула числа перестановок в комбинаторике: $Pn$ = $n$!

Комбинаторика: правило размещения без повторений

Подмножество, выбираемое из данного множества предметов, называют выборкой. Выборки бывают упорядоченные и неупорядоченные. Для упорядоченной выборки существенен порядок элементов. Иначе говоря, меняя порядок элементов, мы получаем другие выборки. Составим, например, из цифр 1, 2, 3, 4, 5 трехзначные числа: 123, 431, 524 и т.д. Это упорядоченные трехэлементные выборки, отличающиеся составом или порядком элементов.

Размещениями из $n$ элементов по $m$ элементов ($m$≤$n$) называют упорядоченные $m$-элементные выборки из данных $n$ элементов.

Формула размещения без повторений в комбинаторике $n$ по $m$ элементов имеет вид: $A_{n}^{m} =\frac{n!}{\left(n-m\right)!} $.

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

Сочетаниями из $n$ элементов по $m$ ($m$≤$n$) в комбинаторике называют неупорядоченные $m$-элементные выборки из данных $n$ элементов. Сочетания отличаются друг от друга хотя бы одним элементом, а порядок элементов не существенен.

Формула cочетания в комбинаторике выглядит следующим образом: $C_{n}^{m} =\frac{n!}{m!\cdot \left(n-m\right)!} $.

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

Разные упорядоченные последовательности длиной $m$, составленные из элементов данного множества, содержащего $n$ элементов, так, что эти элементы в последовательности могут повторяться, называются размещениями с повторениями из $n$ по $m$.

Формула числа размещений с повторениями: $\bar{A}_{n}^{m} =n^{m} $.

Комбинаторика: перестановка с повторением

Рассматриваем мультимножество M, то есть множество, которое может содержать одинаковые элементы.

Пусть заданы предметы $m$-типа. Сколько существует перестановок $n_1$ элементов первого типа, $n_2$ — второго типа и так далее, внутри предмета $m$-типа? Такие перестановки в комбинаторике называют перестановками с повторениями.

Формула числа перестановок с повторениями: $P\left(n_{1} ,n_{2} ,\ldots ,n_{m} \right)=\frac{n!}{n_{1} !\cdot n_{2} !\cdot \ldots \cdot n_{m} !} $, где $n=n_{1} +n_{2} +\ldots +n_{m} $ — общее число элементов множества.

Сочетания с повторениями

Имеем множество из $n$ элементов. Разные неупорядоченные наборы, составленные из $m$ элементов этого множества так, что могут повторяться и порядок их несущественен. Иначе говоря, это число способов, которыми можно разложить $m$ одинаковых предметов по $n$ ящикам.

Формула числа сочетаний с повторениями: $\bar{C}_{n}^{m} =\frac{\left(n+m-1\right)!}{m!\cdot \left(n-1\right)!} $.

Рассмотрим теперь как решать задачи на комбинаторику — ниже приведены различные примеры и задачи с сочетаниями, размещениями и перестановками.

Пример 1

Задание: химик использует семь ингредиентов для приготовления нужного состава. Сколькими способами можно осуществить порядок приготовления?

Решение. Давайте применим элементы комбинаторики и осуществим решение. Как известно, перестановками из $n$ элементов называются комбинации, состоящие из $n$ элементов и отличающиеся порядком расположения элементов.

Количество перестановок вычисляется по формуле $P_{n} =n!$.

Количество различных порядков вливания семи ингредиентов в сосуд — это число перестановок из семи элементов: $P_{7} =7!=1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7=5040$.

Разберём еще один пример задачи на размещение в комбинаторике с решением.

Пример 2

Задание: На собрании присутствуют 20 человек. Сколькими способами из присутствующих можно выбрать председателя, члена президиума и секретаря?

Решение. Как известно, количество размещений вычисляется по формуле $A_{n}^{m} =\frac{n!}{\left(n-m\right)!} $.

Количество различных способов выбора из двадцати присутствующих на собрании председателя, члена президиума и секретаря — это число размещений из двадцати элементов по три: $A_{20}^{3} =\frac{20!}{\left(20-3\right)!} =\frac{20!}{17!} =18\cdot 19\cdot 20=6840$.

Пример 3

Задание. Директор завода заполняет три вакансии из числа 10 претендентов. Сколькими способами директор может заполнить эти вакансии?

Решение. Количество различных способов выбора из десяти выпускников университета троих для заполнения вакансий — это число размещений из десяти элементов по три: $A_{10}^{3} =\frac{10!}{\left(10-3\right)!} =\frac{10!}{7!} =8\cdot 9\cdot 10=720$.

Дата последнего обновления статьи: 17.02.2024
Получи помощь с рефератом от ИИ-шки
ИИ ответит за 2 минуты
Все самое важное и интересное в Telegram

Все сервисы Справочника в твоем телефоне! Просто напиши Боту, что ты ищешь и он быстро найдет нужную статью, лекцию или пособие для тебя!

Перейти в Telegram Bot