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

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

Таким образом, полученные комбинации удовлетворяют различным условиям.

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

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

Произведение всех натуральных чисел от 1 до n включительно называют

Комбинация из n элементов, которые отличаются друг от друга только порядком элементов, называются перестановками.

Число перестановок можно вычислить по формуле

Запишем эту формулу в факториальной форме:

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

Источник

Сочетания и размещения — что это такое и в чем разница

Оба этих понятия – сочетание и размещение – относятся к науке комбинаторике. Это раздел математики, созданный учеными Б. Паскалем и П. Ферма в процессе исследования теории карточных игр. Комбинаторика используется в решении задач особенного рода: когда требуется вычислить количество потенциальных вариантов для какой-либо ситуации. Примером может служить подсчет возможных позиций на шахматной доске после первого хода «черных» и «белых».

О сочетании и размещении говорят, когда из множества необходимо выбрать какое-либо подмножество. Понятия эти весьма близки по своему смыслу, поэтому так трудно бывает понять разницу между ними. Но она существует (причем принципиальная!). Ниже об этом достаточно простым языком написано в статье.

Сочетания

Сочетание – это подмножество, состоящее из К элементов, выбранных из множества, включающего в себя N элементов. При этом выполняется такое условие: N > К.

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

Образно проиллюстрировать понятие можно на примере лотереи. Предположим, человеку предлагается угадать 3 выпавшие цифры из 15-ти. Он выбрал следующий набор – 1, 6, 10. И уже не важно, в каком порядке они выпадут: 1, 6, 10; 1, 10, 6; 10, 1, 6; 10, 6, 1; 6, 10, 1; 6, 1, 10. Главное – состав комбинации. Если он совпадает с загаданным накануне набором цифр, игрок считается победителем.

Сочетания обозначаются следующим образом: С К _N. Где N – количество элементов в множестве, а К – количество объектов в производимой выборке. Для нашего примера N = 15, а К = 3.

Существует формула для определения числа возможных сочетаний в множестве. Выглядит она так: N!/((N-K)!*K!) подставим цифры из нашего примера:

Это означает, что из 15 чисел можно составить 455 различных комбинаций, включающих в себя три разных числа.

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

Размещения

В самом названии этого термина присутствует корень, позволяющий понять его суть. Размещение – тоже подмножество, выбранное из первоначального множества. Но здесь уже существенное значение имеет место расположения элемента в комбинации. То есть если сочетания могут различаться только составом объектов, то размещения разнятся и составом, и порядком следования элементов.

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

Это легко проследить, если сделать выборку трех элементов из множества, состоящего всего из 4 объектов (от 1-го до 4-х).

Сочетаний здесь будет всего 4 (это легко проверить и по приведенной выше формуле):

Размещений же окажется гораздо больше:

123, 132, 321, 312, 231, 213, 234, 243, 324, 342 и т.д.

Существует формула, позволяющая подсчитать возможное количество размещений в представленном множестве:

Для нашего примера посчитаем количество потенциальных размещений:

Получается, что для состоящего из 4-х элементов множества существует 4 сочетания и целых 24 размещения.

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

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

Обозначим названия команд буквами: А, Б, В, Г, Д, Е.

Сначала определим команду, которая станет золотым призером чемпионата. Таких вариантов, очевидно, 6: А, Б, В, Г, Д, Е.

Затем выбираем один из вариантов (пусть это будет комбинация, в которой золото принадлежит команде А), и определяем для него потенциального серебряного призера. Таких комбинаций уже окажется всего 5, так как одна команда уже записана на 1-м месте: АБ, АВ, АГ, АД, АЕ.

Такую пятерку вариаций можно сформировать для каждой из команд. То есть всего претендентов на серебро оказывается 30 (5*6).

Для каждой двойки первых призеров (чемпион-серебряный призер) можно составить только 4 комбинации с бронзовым призером. Первые два места уже распределены, так что остается 4 команды (6-2). Подберем комбинации для варианта АБ: АБВ, АБГ, АБД, АБЕ.

Мы уже подсчитали выше количество возможных комбинаций для первых двух мест – их оказалось 30. Теперь это число умножаем на 4 – получаем 120.

Выходит, что если в турнире участвует 6 команд, вариантов их размещения по первым трем местам может быть целых 120. Угадать призеров не так просто.

Сочетания и размещения: в чем же разница?

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

Источник

Основные понятия

Перестановки

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

Итак, вернемся к задаче из примера: Сколькими способами можно создать числа, переставляя цифры в числе 12345?

У нас есть пять цифр (пусть это будет пять кубиков с цифрами): 1,2,3,4,5.

У нас есть пять, пока еще свободных, позиций под их размещение (пусть это будут пустые коробочки): ▢▢▢▢▢.

Начинаем постепенно заполнять эти позиции: на первую позицию (в первую коробочку) мы можем поместить одну из пяти цифр (один из пяти кубиков). То есть у нас есть пять вариантов заполнения первой позиции.

Предположим, мы взяли кубик с номером 4.

Теперь у нас осталось четыре цифры (кубика): 1,2,3,5.

Позиций (коробочек) у нас осталось пять, но первая уже заполнена, то есть свободных позиций четыре: 4▢▢▢▢.

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

Предположим, мы взяли кубик с номером 1.

У нас осталось три цифры (кубика): 2,3,5.

Позиций (коробочек) у нас осталось пять, но первые две уже заполнены: 41▢▢▢.

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

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

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

Обозначается число перестановок из n так:

В итоге мы получаем следующую формулу для вычисления количества перестановок для n элементов:

Размещения

Размещение очень похоже на перестановку, с одной лишь разницей: у нас обычно «не хватает» позиций (коробочек) для размещения всех элементов (кубиков).

Обозначается размещение n из k так:

При k = n (то есть когда число «коробочек» равно числу «кубиков») количество размещений равно количеству перестановок порядка n.

Возьмем задачу из примера: Сколько трехзначных чисел можно создать из цифр от 1 до 5?

Если мы по аналогии с перестановками попробуем по шагам считать, то увидим, что мы остановились после заполения третьей (последней) «коробочки»:

Мы можем записать так:

а в общем виде так:

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

Существует вариант, когда мы можем повторно использовать один и тот же элемент, независимо от того, использовали мы его до этого, или нет. В случае с кубиками и коробочками это будет выглядеть так: у нас есть не по одному кубику с каждым номером, а неограниченное число кубиков с каждым из чисел. Это называется размещение n из k с повторением и обозначается:

Начнем заполнять «коробочки».

У нас есть пять кубиков с цифрами: 1,2,3,4,5.

У нас есть пять, пока еще свободных, позиций под их размещение (пусть это будут пустые коробочки): ▢▢▢▢▢.

Положим, в первую мы кладем номер 4.

Значит у нас осталось четыре свободных «коробочки»: 4▢▢▢▢.

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

Соотвественно две первые коробочки мы можем заполнить 5⋅ 5 = 25 способами (а не 5⋅ 4 = 20, как в случае без повторения).

Повторяя рассуждения мы вычислим, что три коробочки мы можем заполнить 5⋅ 5⋅ 5 = 125 способами.

В общем случае число размещений равно числу элементов (кубиков) в степени числа возможных позиций для размещения (коробочек).

Сочетания

Сочетания похожи на размещения, однако для сочетаний совершенно не важно, в каком порядке расположены коробочки. Обозначаются сочетания так:

Как нам вывести формулу для сочетаний? Для начала возьмем число размещений и разделим на число всех вариантов «перемешивания» каждого набора (ведь при «перемешивании» получается тот же набор, просто расположенный в другом порядке). Но чему равно число этих «перемешиваний», спросите вы? А если не спросите, то значит я не зря писал эту статью, потому что внимательный читатель сам заметит, что в данном случае речь идет о перестановках. Обратите внимание, что тут мы переставляем не кубики, а коробочки, которых k штук, поэтому речь идет не о P_n, а о P_k. В итоге мы получаем формулу:

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

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

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

А теперь задание для особо внимательных: могли ли мы совершить такой же «фокус» в случае с размещением с перестановками? Если могли, то почему не сделали? А если не могли, то почему? Жду ответов в комментариях.

Ну и пара примеров задач.

Есть гвоздики двух цветов. Нужно собрать букеты из трех цветков так, чтобы у каждого был уникальный набор. Скольким букетов можно собрать?

Есть гвоздики четырех цветов. Нужно собрать букеты из трех цветков так, чтобы у каждого был уникальный набор. Скольким букетов можно собрать?

Проведем аналогию с кубиками и коробочками. Можно преобразовать эту задачу к виду «Нужно разместить шесть кубиков в трех коробочках». И решение:

Источник

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

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

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

Правило суммы. Если два действия А и В взаимно исключают друг друга, причем действие А можно выполнить 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

Пример 8.

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

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

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

Источник

Комбинаторика: размещения и сочетания

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

Факториалы

Перестановки

Размещения

Сочетания

Размещения

Рассмотрим следующую задачу.

На первое место можно положить одну из 9 карточек. Для этого есть 9 способов. В каждом из этих 9 способов на второе место можно положить одну из оставшихся 8 карточек. Таким образом, существует

способа, чтобы положить карточки на первое и второе места. В каждом из этих 72 способов на третье место можно положить одну из оставшихся 7 карточек. Следовательно, существует

способа, чтобы положить карточки на первое, второе и третье места. В каждом из этих 504 способов на четвертое место можно положить одну из оставшихся 6 карточек. Отсюда вытекает, что существует

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

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

В соответствии с определением факториала, формулу (1) можно также записать в виде:

В задаче множеством из n элементов является исходный набор из 9 пронумерованных карточек, а упорядоченным подмножеством из k элементов – 4 карточки, выложенные в ряд.

Таким образом, при решении задачи мы на частном примере подсчитали, чему равно число размещений из 9 элементов по 4 элемента, т.е. число

В соответствии с формулой (1),

что и было получено в задаче.

смысл которой заключается в следующем.

Сочетания

Число сочетаний из n элементов по k элементов обозначается символом

Таким образом, справедлива формула:

откуда вытекает формула

(2)

Теперь рассмотрим несколько примеров подсчета числа сочетаний, которые непосредственно вытекают из формулы (2):

В заключение приведем часто используемое равенство, также непосредственно вытекающее из формулы (2):

С понятиями факториала числа n и перестановок из n элементов можно познакомиться в разделе «Комбинаторика: факториалы и перестановки» нашего справочника.

Источник