Размещение

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

Пример 1:  — это 4-элементное размещение из 6-элементного множества .

Пример 2: некоторые размещения элементов множества по 2:

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

Заполнить ряд - значит надо поместить на каком-нибудь месте этого ряда какой-либо объект из данного множества (причем каждый объект можно использовать всего лишь один раз). Ряд, заполненный объектами данного множества, называется размещением , т.е мы разместили объекты на данных местах. [1]

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

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

 .

Элементарным образом выражается через символ Похгаммера:

 .

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

При k = n количество размещений равно количеству перестановок порядка n:[2][3][4]

 .

Справедливо следующее утверждение: . Доказывается тривиально:

 .
 
Все 60 вариаций без повторения трех из пяти чисел

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

Размещение с повторениями или выборка с возвращением[5] — это размещение «предметов» в предположении, что каждый «предмет» может участвовать в размещении несколько раз.

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

По правилу умножения количество размещений с повторениями из n по k, обозначаемое  , равно:[6][2][5]

 .

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

 .

Ещё один пример: размещений с повторениями из 4 элементов a, b, c, d по 2 равно 42 = 16, эти размещения следующие:

aa, ab, ac, ad, ba, bb, bc, bd, ca, cb, cc, cd, da, db, dc, dd.
 
Все 125 вариантов с повторением трех из пяти чисел

См. такжеПравить

СсылкиПравить

  1. ISBN 978-5-406-05433-8 Учебник по математике для СПО под редакцией Башмакова М.И.
  2. 1 2 Виленкин Н.Я. Глава III. Комбинаторика кортежей и множеств. Размещения с повторениями // Популярная комбинаторика. — М.: Наука, 1975. — С. 80. — 208 с.
  3. Теория конфигураций и теория перечислений
  4. Глава 3. Элементы комбинаторики. // Лекции по теории вероятностей.
  5. 1 2 Корн Г., Корн Т. Табл. 18.7-2(2.b), 18.7-3(2.b) // Справочник по математике для научных работников и инженеров. — М.: Наука, 1973. — С. 568. — 832 с.
  6. Комбинаторный анализ // Математическая энциклопедия / Под ред. И. М. Виноградова. — М., 1977. — Т. 2. — С. 974. — (Сов. энциклопедия).