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

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

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

Поясним это на следующем примере. Пусть имеется три элемента: a, b и c. Тогда из этих трёх элементов можно составить девять размещений с повторениями по два элемента: ab, ac, ba, bc, ca, cb, aa, bb, cc.

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

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

. (10.1)

Пример 10.1. В лифт восьмиэтажного дома вошли 5 пассажиров. Сколькими способами могут выйти пассажиры на каждом этаже, начиная со второго?

Решение. Задача сводится к распределению 5 пассажиров по 7 этажам (т. е. набор упорядоченный), причем возможны повторения (т. е. несколько пассажиров могут выйти на одном этаже). Таким образом, задача сводится к нахождению числа размещений с повторениями:

Пример 10.2. Сколькими способами можно 5 шариков разбросать по 8 лункам, если каждая лунка может вместить все 5 шариков?

Решение. Данная задача есть задача на отыскание числа размещений с повторениями

.

Пример 10.3. Буквы азбуки Морзе состоят из символов – точка и тире. Сколько букв получим, если потребуем, чтобы каждая буква состояла не более чем из пяти указанных символов?

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

Число всех букв, каждая из которых записывается двумя символами, равно .

Число всех букв, каждая из которых записывается тремя символами, равно .

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

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

Число всех указанных букв будет равно 62.

10.1. Сколькими способами девочка Яна может разложить 12 кукол по трём ящикам, если каждый ящик может вместить все куклы?

Ответ: .

10.2. Сколькими способами Пончик может рассовать 6 конфет по 9 карманам, если каждый карман может вместить все конфеты?

Ответ: .

10.3. Сколькими способами можно разместить 8 пассажиров по трем вагонам?

Ответ: .

10.4. Сколькими различных восьмизначных чисел можно написать, пользуясь только тремя цифрами 3, 5, 7 при условии, что цифра 5 в каждом числе встречается ровно два раза?

Ответ: .

10.5. Из цифр 1, 2, 3, 4, 5 составлены всевозможные пятизначные числа (повторение цифр разрешается). Сколько среди них чисел, у которых: 1) a=1; 2) a¹2; 3) a=3, b=2; 4) a=3, b=4, c=5?

Ответ: .

10.6. Сколько чисел, меньших миллиона, можно написать с помощью цифр: а) 8 и 9; б) 7, 8, 9; в) 0, 8, 9 (с цифры 0 число начинаться не может)?

Ответ: а) Так как с помощью двух цифр 8 и 9 можно написать 2k k-значных числа, то общее количество искомых чисел равно . б) Для трёх цифр аналогично получаем . в) Учтём, что для первой цифры есть только две возможности выбора. Тогда получим чисел.

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

Ответ: Каждая курица может либо войти, либо не войти в число выбранных. Поэтому имеем 23 способов выбора кур. Так как по условию хотя бы одна курица должна быть выбрана (т. е. не может быть случая, когда ни одной курицы не будет выбрано), то число выбора кур будет на единицу меньше: способов выбора кур. Точно так же есть способов выбора уток и способов выбора гусей. Всего способов.

Источник

Размещения

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

Например:
Для создания 3-значного пароля используются символы из алфавита <+,*,A. 2>.
Сколько всего паролей без повторения символов можно составить?
По условию n = 5, k = 3. Рассматриваем размещение 5 символов по 3 позициям без повторений: \(\mathrm< A_5^3=\frac<5!><(5-3)!>=5\cdot 4\cdot 3 = 60 >\)
Всего 60 паролей.
Результат можно получить непосредственно из правила произведения. Действительно, на первой позиции – 5 вариантов символов, на второй – 4 оставшихся, на третьей – 3 оставшихся. Итого, по правилу произведения: 5 · 4 · 3 = 60 паролей.

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

п.3. Примеры

Пример 1. Исследуйте различие между перестановкой без повторений и размещением без повторений 〈3,2〉-выборок для трёх разноцветных фишек. Изобразите полученные решения.

Рассматриваем фишки:

1) Для перестановок, 〈3,3〉-выборок, получаем:

В каждом ряду – отдельная перестановка. Видно, как образуется факториал. Для каждой отдельной фишки – одна перестановка. Для каждой пары фишек – две перестановки: 2 · 1. Когда добавляем третью, получаем: 3 · 2 · 1 Итого: P3 = 3 · 2 · 1 = 6 перестановок.

2) Для размещений без повторений, 〈3,2〉-выборок, получаем:

В каждом ряду – отдельное размещение. В первом столбце слева – 3 варианта по цвету. Во втором столбце остается только 2 варианта. Итого: \(\mathrm\) размещений.

Пример 2. Исследуйте перестановки без повторений и размещения для 〈4,3〉 выборок и для 〈4,2〉 выборок без повторений из 4 разноцветных фишек.
Изобразите полученные решения.

Рассматриваем фишки:

В каждом ряду – отдельная перестановка. Итого: P4=4·3·2·1=24 перестановки.

В каждом ряду – отдельное размещение. Итого: \(\mathrm\) размещения.

В каждом ряду – отдельное размещение. Итого: \(\mathrm\) размещений.

Пример 3. Исследуйте различие между перестановкой с повторениями и размещением с повторениями. Сделайте вывод.
Перестановка с повторениями: сколько слов можно получить, переставляя буквы в слове «МАМА»? Запишите все эти слова в лексикографическом порядке.
Размещение с повторениями: сколько 4-буквенных слов можно получить, используя две буквы: «М» и «А»? Запишите все эти слова в лексикографическом порядке.

1) Для перестановки с повторениями получаем: \begin \mathrm< a_1=M,k_1=2,\ \ \ a_2=A,k_2=2 >\\ \mathrm< k=k_1+k_2=2+2=4 >\\ \mathrm< P_4(2;2)=\frac<4!><2!\cdot 2!>=\frac<24><2\cdot 2>=6 > \end Все 6 слов в лексикографическом порядке:

Вывод: вариантов для размещения с повторениями получается больше, т.к. они включают слова с одной, тремя и четырьмя «М» и «А». А в перестановки с повторениями входят только слова с двумя «М» и двумя «А».

Пример 4. В базе данных с номерами телефонов содержатся все 7-значные номера.
1) Сколько в книге номеров, в которых цифры не повторяются?
2) Сколько в книге всего номеров?
3) Сколько в книге номеров, у которых 4 последних цифры одинаковые?
4) Сколько в книге номеров, у которых 4 последних цифры одинаковые, а 3 первых цифры отличаются от 4 последних?
1) Цифр – всего 10:

Источник

Перестановки, размещения и сочетания. Формулы.

Чтобы в материале было легче ориентироваться, добавлю содержание данной темы:

Введение. Множества и выборки.

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

Для работы нам понадобятся кое-какие вспомогательные сведения. Начнём с такого фундаментального математического понятия как множество. Подробно понятие множества было раскрыто в теме «Понятие множества. Способы задания множеств».

Очень краткий рассказ про множества: показать\скрыть

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

Запись «n!» (читается «эн факториал») обозначает произведение всех чисел от 1 до n, т.е.

Нас же интересует общее количество этих размещений. Согласно формуле (1) количество размещений без повторений из 5 элементов по 3 будет таким:

Т.е. можно составить 60 трёхсимвольных слов, буквы которых не будут повторяться.

Следовательно, из заданных цифр можно составить 243 пятизначных числа.

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

Следовательно, существует 120 порядков выбора очередности съедения.

Перестановки с повторениями

Общее количество перестановок с повторениями определяется формулой:

Следовательно, общее количество искомых слов равно 105.

В корзине размещены карточки, на которых написаны целые числа от 1 до 10. Из корзины вынимают 4 карточки и суммируют числа, написанные на них. Сколько различных наборов карточек можно вытащить из корзины?

Следовательно, общее количество искомых наборов равно 210.

Представьте себе, что мы находимся на конфетном заводе, – прямо возле конвейера, по которому движутся конфеты четырёх сортов. Мы запускаем руки в этот поток и вытаскиваем двадцать штук. Сколько всего различных «конфетных комбинаций» может оказаться в горсти?

Следовательно, общее количество искомых комбинаций равно 1771.

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

Источник

Размещение (комбинаторика)

В комбинаторике размещением называется расположение «предметов» на некоторых «местах» при условии, что каждое место занято в точности одним предметом и все предметы различны. Более формально, размеще́нием (из n по k) называется упорядоченный набор из k различных элементов некоторого n-элементного множества.

Например, — это 4-элементное размещение 6-элементного множества <1,2,3,4,5,6>.

В отличие от сочетаний размещения учитывают порядок следования предметов. Так, например, наборы и являются различными, хотя состоят из одних и тех же элементов <1,2,3>(то есть, совпадают как сочетания).

Содержание

Количество размещений

Количество размещений из n по k, обозначаемое , дается формулами:

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

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

Например, количество вариантов 3-x значного кода, в котором каждый знак является цифрой от 0 до 9 и может повторяться, равно 10 3 = 1000.

Пример алгоритма получения размещений с повторениями для массива объектов на Java

Пример получения размещений с повторениями для списка на Haskell

Ссылки

Полезное

Смотреть что такое «Размещение (комбинаторика)» в других словарях:

Размещение:Комбинаторика — В комбинаторике размещением называется расположение «предметов» на некоторых «местах» при условии, что каждое место занято в точности одним предметом и все предметы различны. Более формально, размещением (из n по k) называется упорядоченный набор … Википедия

РАЗМЕЩЕНИЕ — см. Комбинаторика … Большой Энциклопедический словарь

Размещение — В комбинаторике размещением называется расположение «предметов» (объектов) на некоторых «местах» при условии, что каждое место занято в точности одним предметом и все предметы различны. Более формально, размещением (из n по k) называется… … Википедия

размещение — я; ср. 1. к Разместить размещать и Разместиться размещаться. Р. людей по квартирам. Р. нового оборудования в цехе. Дать время на р. 2. Порядок, система расположения чего л. Р. электродов. Р. производительных сил. Р. промышленных объектов по… … Энциклопедический словарь

РАЗМЕЩЕНИЕ — см. Комбинаторика … Естествознание. Энциклопедический словарь

История комбинаторики — освещает развитие комбинаторики раздела конечной математики, который исследует в основном различные способы выборки заданного числа m элементов из заданного конечного множества: размещения, сочетания, перестановки, а также перечисление и смежные… … Википедия

Сочетание — В комбинаторике сочетанием из по называется набор элементов, выбранных из данного множества, содержащего различных элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания… … Википедия

КОМБИНАТОРНЫЙ АНАЛИЗ — комбинаторная математика, комбинаторика, раздел математики, посвященный решению задач выбора и расположения элементов нек рого, обычно конечного, множества в соответствии с заданными правилами. Каждое такое правило определяет способ построения… … Математическая энциклопедия

Числа Каталана — числовая последовательность, встречающаяся во многих задачах комбинаторики. Последовательность названа в честь бельгийского математика Каталана, хотя была известна ещё Л. Эйлеру. Первые несколько чисел Каталана: 1, 1, 2, 5, 14, 42, 132, 429, 1430 … Википедия

Источник

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

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

Когда так бывает? Ну, конечно, при выборе цифр и букв. Как говорится, если 10 раз сказать «а», то буква «а» из алфавита никуда не денется.

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

Задача 14
Сколько существует четырёхзначных пин-кодов?

Решение: на самом деле для разруливания задачи достаточно знаний правил комбинаторики: способами можно выбрать первую цифру пин-кода и способами – вторую цифру пин-кода и столькими же способами – третью и столькими же – четвёртую. Таким образом, по правилу умножения комбинаций, четырёхзначный пин-код можно составить:
способами.

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

Ответ: 10000

Что тут приходит на ум… …если банкомат «съедает» карточку после третьей неудачной попытки ввода пин-кода, то шансы подобрать его наугад весьма призрачны.

И кто сказал, что в комбинаторике нет никакого практического смысла?

Ещё одна познавательная и практически важная задача:

Задача 15
Согласно государственному стандарту, автомобильный номерной знак состоит из 3 цифр и 3 букв. При этом недопустим номер с тремя нулями, а буквы выбираются из набора А, В, Е, К, М, Н, О, Р, С, Т, У, Х (используются только те буквы кириллицы, написание которых совпадает с латинскими буквами).

Сколько различных номерных знаков можно составить для региона?

Не так их, кстати, и много. В крупных регионах такого количества не хватает, и поэтому для них существуют несколько кодов к надписи RUS.

…хотел похвастаться эксклюзивом, да оказалось не эксклюзивом =) Заглянул в Википедию – там есть расчёты, правда, без комментариев.

И теперь во всеоружии мы возвращаемся к основному курсу:

Также вы можете изучить эту тему подробнее – просто, доступно, весело и бесплатно!

С наилучшими пожеланиями, Александр Емелин

Источник