Что такое размещение в математике
Сочетания и размещения — что это такое и в чем разница
Оба этих понятия – сочетание и размещение – относятся к науке комбинаторике. Это раздел математики, созданный учеными Б. Паскалем и П. Ферма в процессе исследования теории карточных игр. Комбинаторика используется в решении задач особенного рода: когда требуется вычислить количество потенциальных вариантов для какой-либо ситуации. Примером может служить подсчет возможных позиций на шахматной доске после первого хода «черных» и «белых».
О сочетании и размещении говорят, когда из множества необходимо выбрать какое-либо подмножество. Понятия эти весьма близки по своему смыслу, поэтому так трудно бывает понять разницу между ними. Но она существует (причем принципиальная!). Ниже об этом достаточно простым языком написано в статье.
Сочетания
Сочетание – это подмножество, состоящее из К элементов, выбранных из множества, включающего в себя 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. Угадать призеров не так просто.
Сочетания и размещения: в чем же разница?
И сочетания, и размещения являются выборкой из определённого множества. Принципиальная разница между понятиями заключается лишь в том, что в случае сочетаний порядок расположения элементов не имеет значения, а в случае размещений он важен. Именно поэтому в пределах одного и того же множества количество сочетаний всегда оказывается меньше числа размещений.
Размещение (комбинаторика)
В комбинаторике размещением называется расположение «предметов» на некоторых «местах» при условии, что каждое место занято в точности одним предметом и все предметы различны. Более формально, размеще́нием (из 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 … Википедия
Перестановки, размещения и сочетания. Формулы.
Чтобы в материале было легче ориентироваться, добавлю содержание данной темы:
Введение. Множества и выборки.
В этой теме рассмотрим основные понятия комбинаторики: перестановки, сочетания и размещения. Выясним их суть и формулы, по которым можно найти их количество.
Для работы нам понадобятся кое-какие вспомогательные сведения. Начнём с такого фундаментального математического понятия как множество. Подробно понятие множества было раскрыто в теме «Понятие множества. Способы задания множеств».
Очень краткий рассказ про множества: показать\скрыть
Заметьте, что в определении выборки ничего не сказано про повторения элементов. В отличие от элементов множеств, элементы выборки могут повторяться.
Запись «n!» (читается «эн факториал») обозначает произведение всех чисел от 1 до n, т.е.
Нас же интересует общее количество этих размещений. Согласно формуле (1) количество размещений без повторений из 5 элементов по 3 будет таким:
Т.е. можно составить 60 трёхсимвольных слов, буквы которых не будут повторяться.
Следовательно, из заданных цифр можно составить 243 пятизначных числа.
В морозилке лежат пять порций мороженого от различных фирм. Сколькими способами можно выбрать порядок их съедения?
Следовательно, существует 120 порядков выбора очередности съедения.
Перестановки с повторениями
Общее количество перестановок с повторениями определяется формулой:
Следовательно, общее количество искомых слов равно 105.
В корзине размещены карточки, на которых написаны целые числа от 1 до 10. Из корзины вынимают 4 карточки и суммируют числа, написанные на них. Сколько различных наборов карточек можно вытащить из корзины?
Следовательно, общее количество искомых наборов равно 210.
Представьте себе, что мы находимся на конфетном заводе, – прямо возле конвейера, по которому движутся конфеты четырёх сортов. Мы запускаем руки в этот поток и вытаскиваем двадцать штук. Сколько всего различных «конфетных комбинаций» может оказаться в горсти?
Следовательно, общее количество искомых комбинаций равно 1771.
Заметили ошибку, опечатку, или некорректно отобразилась формула? Отпишите, пожалуйста, об этом в данной теме на форуме (регистрация не требуется).
Размещения
п.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
Вывод: вариантов для размещения с повторениями получается больше, т.к. они включают слова с одной, тремя и четырьмя «М» и «А». А в перестановки с повторениями входят только слова с двумя «М» и двумя «А».
Пример 4. В базе данных с номерами телефонов содержатся все 7-значные номера.
1) Сколько в книге номеров, в которых цифры не повторяются?
2) Сколько в книге всего номеров?
3) Сколько в книге номеров, у которых 4 последних цифры одинаковые?
4) Сколько в книге номеров, у которых 4 последних цифры одинаковые, а 3 первых цифры отличаются от 4 последних?
1) Цифр – всего 10:
Размещение
В комбинаторике размещением называется расположение «предметов» (объектов) на некоторых «местах» при условии, что каждое место занято в точности одним предметом и все предметы различны. Более формально, размеще́нием (из n по k) называется упорядоченный набор из k различных элементов из некоторого множества различных же n элементов.
Пример 1: 
— это 4-х элементное размещение из 6-ти элементного множества 
.
Пример 2: некоторые размещения элементов множества по 2: 
. 
. 
.
В отличие от сочетаний, размещения учитывают порядок следования предметов. Так, например, наборы 
и 
являются различными, хотя состоят из одних и тех же элементов 
(то есть совпадают как сочетания).
Содержание
Количество размещений
Количество размещений из n по k, обозначаемое 
, равно убывающему факториалу:
Последнее выражение имеет естественную комбинаторную интерпретацию: каждое размещение из n по k однозначно соответствует некоторому сочетанию из n по k и некоторой перестановке элементов этого сочетания; число сочетаний из n по k равно биномиальному коэффициенту 
, в то время как перестановок на k элементах ровно k! штук.
При k=n количество размещений равно количеству перестановок порядка n: [1] [2] [3]
Размещение с повторениями
Размещение с повторениями или выборка с возвращением [4] — это размещение «предметов» в предположении, что каждый «предмет» может участвовать в размещении несколько раз.
Количество размещений с повторениями
По правилу умножения количество размещений с повторениями из n по k, обозначаемое 
, равно: [5] [1] [4]
Например, количество вариантов 3-значного кода, в котором каждый знак является цифрой от 0 до 9 и может повторяться, равно:
См. также
Ссылки
Полезное
Смотреть что такое «Размещение» в других словарях:
РАЗМЕЩЕНИЕ — (flotation) Процесс первого запуска публичной/открытой компании путем приглашения публики подписываться на ее акции (его называют также выходом на публику ). Это относится к эмиссии акций как частных, так и национализированных компаний и может… … Финансовый словарь
РАЗМЕЩЕНИЕ — РАЗМЕЩЕНИЕ, размещения, ср. 1. только ед. Действие по гл. разместить размещать. Размещение капиталов. Размещение средств. 2. только ед. Порядок, система расположения чего нибудь. Размещение производительных сил в СССР. Сохранить прежнее род.… … Толковый словарь Ушакова
размещение — См. положение. Словарь русских синонимов и сходных по смыслу выражений. под. ред. Н. Абрамова, М.: Русские словари, 1999. размещение расположение, расстановка, распределение; местоположение; вселение, букировка, расквартирование, рассовывание,… … Словарь синонимов
Размещение — популяций, распределение организмов (популяций) в пространстве. Известны три основных типа пространственного размещения организмов в популяции: равномерное, агрегированное и случайное. Размещение популяций зависит от биологических особенностей… … Экологический словарь
РАЗМЕЩЕНИЕ — (placing) Продажа компанией своих акций определенной группе юридических или физических лиц. Размещение может быть использовано либо как средство выпуска новых акций на свободный рынок (flotation), либо акционерной компанией – для расширения… … Словарь бизнес-терминов
РАЗМЕЩЕНИЕ — (placing) Предпочтительная продажа акций английской компанией отдельным физическим лицам или учреждениям, прямо связанным с ней, без выхода акций на свободный рынок. Размещение может быть преимущественным по причине более низких издержек или же… … Экономический словарь
РАЗМЕЩЕНИЕ — см. Комбинаторика … Большой Энциклопедический словарь
РАЗМЕЩЕНИЕ — РАЗМЕЩЕНИЕ, я, ср. 1. см. разместить, ся. 2. Порядок, система в расположении чего н. Рациональное р. средств. Толковый словарь Ожегова. С.И. Ожегов, Н.Ю. Шведова. 1949 1992 … Толковый словарь Ожегова
размещение — — [Я.Н.Лугинский, М.С.Фези Жилинская, Ю.С.Кабиров. Англо русский словарь по электротехнике и электроэнергетике, Москва, 1999 г.] Тематики электротехника, основные понятия EN constructionarrangement … Справочник технического переводчика
размещение — Конкретное расположение природных или антропогенных объектов и явлений на поверхности Земли. Syn.: распространение; географическое распределение … Словарь по географии
размещение — 3.9 размещение: Физическое размещение ИО, а также подсоединенных периферийных устройств и/или подключаемого оборудования в пределах зоны испытаний. Источник … Словарь-справочник терминов нормативно-технической документации