Что такое размещение в комбинаторике
Размещение (комбинаторика)
В комбинаторике размещением называется расположение «предметов» на некоторых «местах» при условии, что каждое место занято в точности одним предметом и все предметы различны. Более формально, размеще́нием (из 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 элементов. При этом выполняется такое условие: 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 … Википедия
Что такое размещение в комбинаторике
Таким образом, полученные комбинации удовлетворяют различным условиям.
В зависимости от правил составления можно выделить три типа комбинаций: перестановки, размещения, сочетания.
Предварительно познакомимся с понятием факториала.
Произведение всех натуральных чисел от 1 до n включительно называют
Комбинация из n элементов, которые отличаются друг от друга только порядком элементов, называются перестановками.
Число перестановок можно вычислить по формуле
Запишем эту формулу в факториальной форме:
Кроме того, при решении задач используются следующие формулы, выражающие основные свойства сочетаний:
Комбинаторика: размещения и сочетания
При решении задач по комбинаторике используют следующие важные понятия
 Факториалы |
| Перестановки |
| Размещения |
| Сочетания |
Размещения
Рассмотрим следующую задачу.
На первое место можно положить одну из 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 элементов можно познакомиться в разделе «Комбинаторика: факториалы и перестановки» нашего справочника.