6. (Анализ) Комбинаторика. Размещение

По | 14 июня, 2022
размещение

В комбинаторике размещением называется расположение «предметов» на некоторых «местах» при условии, что каждое место занято в точности одним предметом и все предметы различны. Если говорить кратко, то размещение – комбинации из n элементов по m (m<n), которые отличаются друг от друга или самими элементами или их порядком. 

Условно можно выделить два вида размещений:

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

В прошлой статье я кратко описал, что из себя представляет размещения. Теперь давайте рассмотрим их подробнее.

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

Размещение без повторений ( Anm — читается ”а из n по m“).

Anm = n * (n − 1) * … * (n − m + 1) = n! / (n − m)!

Рассмотрим множество объектов A = {a1, …, an}. Выберем первый объект из n, но назад его не возвращаем. Так как наш выбор может пасть на любой объект множества, то количество способов извлечения одного объекта равно количеству все этих объектов. Теперь выберем второй объект из оставшихся и его тоже возвращать не будем. Так как в предыдущий раз мы извлекли из множества А один объект и его не вернули обратно, то общее количество объектов в множестве уменьшилось на единицу. Поэтому второй объект извлекается из количества n − 1. Далее повторяем действие с остальными объектами, пока количество извлечённых объектов не будет равно m. Объект m мы сможем извлечь n − m + 1 способами. В нашем случае двумя способами.

Далее применяется правило умножения. Почему именно правило умножения? Дело в том, что мы имеем дело с несколькими множествами.

Первое множество представлено всеми объектами a. Следующее множество содержит на один объект а меньше, так как один объект был извлечён, но не возвращён обратно. Последующее множество ещё меньше на один объект и так далее.

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

a1b1c1d1e1, a1b2c1d1e1, a1b2c2d1e1, a1b2c2d2e1 … a1bmcqdres,

a1b1c1d1e1, a1b1c2d1e1, a1b1c2d2e1, a1b1c2d2e2 … a1b1cqdres,

a1b1c1d1e1, a1b1c1d2e1, a1b1c1d2e2, a1b1c2d2e3 … a1b1c1dres,
……..

Например: У нас, в коробке, есть пять(n) шаров. Сколькими способами мы можем извлечь четыре(m) шара?

A54 = ( 5 * (5-1) * (5-2) * (5-3) ) / (5-4)! = (5*4*3*2)/ 1! = 120 / 1 =120

Для начала извлечем из пяти шаров любой шар. Это мы можем сделать пятью способами. Так как мы шар не возвращаем, то в коробке остаётся четыре шара. Второй шар мы извлекаем четырьмя способами. После этого в коробке остаётся три шара. Третий шар извлекается тремя способами. В коробке осталось два шара. Теперь извлекаем четвёртый шар двумя (5-4+1 или 5-3) способами. Таким образом мы имеем дело с четырьмя множествами.

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

Размещения с повторениями (A̅nm).

Рассмотрим множество объектов A = {a1, …, an}. Мы выбираем объект из этого множества. Так как наш выбор может пасть на любой объект множества, то количество способов извлечения одного объекта равно количеству(n) все этих объектов. Но сейчас взятый нами объект возвращается обратно. После этого извлекаем второй объект. Количество способов извлечения второго объекта опять равно количеству(n) все этих объектов, так как мы возвратили первый извлечённый нами объект. Второй извлекаемый нами объект может быть отличен от первого или же им может оказаться первый извлечённый объект.

Так как нам надо извлечь m объектов, то мы повторяем подобные действия m раз. Согласно правилу умножения, которое мы рассмотрели в самом начале, получаем количество способов выбрать m объектов равным: n * n * … * n= nm.

nm = nm

Поскольку каждый новый извлекаемый объект мог извлекаться ранее, то поэтому данный вид размещения называется «размещение с повторениями».

Например: У нас, в коробке, есть пять(n) шаров. Сколькими способами мы можем извлечь четыре(m) шара?

54 = 5 * 5 * 5 * 5 =625

Для начала извлечем из пяти шаров любой шар. Это мы можем сделать пятью способами. Так как мы шар возвращаем в коробку, то в там снова находятся пять шаров. Второй шар мы извлекаем тоже пятью способами. Возвращаем второй шар обратно. После этого в коробке снова пять шаров. Третий шар извлекается опять пятью способами и возвращаем его. В коробке снова пять шаров. Сколькими способами мы можем извлечь четвёртый шар? Правильно пятью. В итоге мы имеем дело с четырьмя множествами и все они имеют одинаковое количество объектов a(шаров). И чтобы перечислить все возможные варианты выбора m шаров, у нас уйдёт очень много времени. Но в итоге мы получим 625 способов.

Что дальше?

Теперь можно перейти к перестановкам. Почему именно к ним? Потому что…

Вы поймёте, как только прочитаете соответствующую статью.