Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 17 апреля 2022 года; проверки требуют 3 правки.
В комбинаторике размеще́нием (из n по k) называется упорядоченный набор из k различных элементов из некоторого множества различных n элементов.
Пример 1: 
Пример 2: некоторые размещения элементов множества
В отличие от сочетаний, размещения учитывают порядок следования предметов. Так, например, наборы 
Заполнить ряд – значит надо поместить на каком-нибудь месте этого ряда какой-либо объект из данного множества (причём каждый объект можно использовать всего лишь один раз). Ряд, заполненный объектами данного множества, называется размещением , т. е. мы разместили объекты на данных местах. [1]
Число размещений[править | править код]
Число размещений из n по k, обозначаемое 
.
Элементарным образом выражается через символ Похгаммера:
.
Последнее выражение имеет естественную комбинаторную интерпретацию: каждое размещение из n по k однозначно соответствует некоторому сочетанию из n по k и некоторой перестановке элементов этого сочетания; число сочетаний из n по k равно биномиальному коэффициенту 
При k = n число размещений равно числу перестановок порядка n:[2][3][4]
.
Справедливо следующее утверждение:
.
Все 60 вариаций без повторения трех из пяти чисел
Размещение с повторениями[править | править код]
Размещение с повторениями или выборка с возвращением[5] — это размещение «предметов» в предположении, что каждый «предмет» может участвовать в размещении несколько раз.
Число размещений с повторениями[править | править код]
По правилу умножения число размещений с повторениями из n по k, обозначаемое 
.
Например, число вариантов 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 вариантов с повторением трех из пяти чисел
См. также[править | править код]
- Обобщённая схема размещения
- Сочетание
- Перестановка
Ссылки[править | править код]
- ↑ ISBN 978-5-406-05433-8 Учебник по математике для СПО под редакцией Башмакова М.И. Архивная копия от 9 декабря 2019 на Wayback Machine
- ↑ 1 2 Виленкин Н.Я. Глава III. Комбинаторика кортежей и множеств. Размещения с повторениями // Популярная комбинаторика. — М.: Наука, 1975. — С. 80. — 208 с.
- ↑ Теория конфигураций и теория перечислений. Дата обращения: 30 декабря 2009. Архивировано 23 января 2010 года.
- ↑ Глава 3. Элементы комбинаторики Архивная копия от 4 января 2010 на Wayback Machine. // Лекции по теории вероятностей.
- ↑ 1 2 Корн Г., Корн Т. Табл. 18.7-2(2.b), 18.7-3(2.b) // Справочник по математике для научных работников и инженеров. — М.: Наука, 1973. — С. 568. — 832 с.
- ↑ Комбинаторный анализ // Математическая энциклопедия / Под ред. И. М. Виноградова. — М., 1977. — Т. 2. — С. 974. — (Сов. энциклопедия).
Формула числа размещений
Спасибо за ваши закладки и рекомендации
Определение числа размещений
Пусть имеется $n$ различных объектов.
Будем выбирать из них $k$ объектов и переставлять всеми возможными способами между собой (то есть меняется и состав выбранных объектов, и их порядок). Получившиеся комбинации называются размещениями из $n$ объектов по $k$, а их число равно
$$A_n^k=frac{n!}{(n-k)!}=ncdot (n-1)cdot … cdot (n-k+1) $$
Если вы уже знакомы с сочетаниями, то легко заметите, что чтобы найти размещения, надо взять все возможные сочетания, а потом в каждом еще поменять порядок всеми возможными способами (то есть фактически сделать еще перестановки). Поэтому число размещений еще выражается через число перестановок и сочетаний так:
$$A_n^k= C_n^k cdot k! = C_n^k cdot P_k.$$
Получилась такая изящная формула, объединяющая три других формулы комбинаторики (три концепции: размещений, сочетаний и перестановок).
Пример всех размещений из $n=3$ объектов (различных фруктов) в группы по $m=2$ с учетом порядка – на картинке справа. Согласно формуле, их должно быть ровно $$A_3^2=3cdot (3-2+1)=3cdot 2 =6.$$
Чтобы вычислить число размещений $A_n^k$ онлайн, используйте калькулятор ниже.
Видеоролик о размещениях
Не все понятно? Посмотрите наш видеообзор для формулы размещений: как использовать Excel для нахождения числа размещений, как решать типовые задачи и использовать онлайн-калькулятор.
Расчетный файл из видео можно бесплатно скачать
Полезная страница? Сохрани или расскажи друзьям
Полезные ссылки
- Онлайн-учебник по теории вероятностей
- Как решать задачи по комбинаторике?
- Примеры решений задач по теории вероятностей
- Решить теорию вероятности на заказ
Решенные задачи
Размещением из (n) элементов по (m) элементов (
m≤n
) называется упорядоченная выборка элементов (m) из данного множества элементов (n).
Количество размещений из (n) элементов по (m) элементов обозначается
Anm
(читается как «размещение из (n) элементов по (m) элементов»).
 |
←
(m) показывает количество элементов размещения (сколько элементов выбирается) |
|
↑ (n) показывает количество элементов данного множества |
Размещения вычисляются по формуле
Anm=n!(n−m)!
.
1. Сколько двузначных чисел можно составить из цифр (2; 3; 4; 5; 6) (если цифры не должны повторяться)?
Решение:
выбираются (2) элемента из множества (5) элементов.
В данном случае (n = 5) (т. к. дано множество с (5) цифрами), а (m = 2) (т. к. нужно выбрать (2) цифры для числа).
По формуле:
A52=5!5−2!=5!3!=5⋅4⋅3!3!=5⋅4⋅3!3!=20
.
Ответ: из данных цифр можно составить (20) двузначных чисел с различными цифрами.
2. Даны элементы (3) разных цветов: 
. Сколькими различными способами можно выбрать (2) из них, если порядок важен?
Решение:
эту задачу можно решить двумя способами: полным перебором или подставив величины в формулу.
1) 
2) 
3) 
4) 
5) 
6) 
Как видно на картинке, два элемента из всех данных можно выбрать (6) различными способами.
Подставив величины в формулу ((n = 3) и (m= 2)), получаем такой же результат:
A32=3!(3−2)!=3!1!=1⋅2⋅31=61=6
.
3. У стола осталось (6) свободных мест. Сколькими различными способами места могут занять (4) человека?
Решение:
основное множество составляют (6) свободных мест, значит, (n = 6), выборку составляют (4) человека, значит, (m = 4). Так как важен порядок, в котором люди займут места, количество выборок равно количеству размещений из (6) элементов по (4) элемента, т. е.
A64=6!6−4!=6!2!=2!⋅3⋅4⋅5⋅62!=3⋅4⋅5⋅6=360
.
Ответ: за столом (6) свободных мест четыре человека могут занять (360) различными способами.
4. Упрости выражение:
a)
An−13=(n−1)!(n−1−3)!=(n−1)!(n−4)!=(n−4)!⋅(n−3)⋅(n−2)⋅(n−1)(n−4)!==(n−3)⋅(n−2)⋅(n−1).
b)
Ann−1=n!(n−(n−1))!=n!1!=n!1=n!
(Запомни, (0! = 1) и (1! = 1)).
c)
Ann=n!(n−n)!=n!0!=n!1=n!
5. Вычисли значение выражения:
A74−A53A52=7!(7−4)!−5!(5−3)!5!(5−2)!=7!3!−5!2!5!3!=7!2!⋅3−5!2!5!3!=7!−5!⋅33!5!3!==5!⋅6⋅7−5!⋅33!5!3!=5!6⋅7−3⋅3!3!⋅5!=6⋅7−3=42−3=39.
Размещения
- Размещения без повторений
- Размещения с повторениями
- Примеры
п.1. Размещения без повторений
Размещениe без повторений – это упорядоченная ⟨n,k⟩ – выборка без повторений, k ≤ n. Общее количество размещений без повторений: $$ mathrm{ A_n^k=frac{n!}{(n-k)!} } $$
Например:
Для создания 3-значного пароля используются символы из алфавита {+,*,A,!,2}.
Сколько всего паролей без повторения символов можно составить?
По условию n = 5, k = 3. Рассматриваем размещение 5 символов по 3 позициям без повторений: (mathrm{ A_5^3=frac{5!}{(5-3)!}=5cdot 4cdot 3 = 60 })
Всего 60 паролей.
Результат можно получить непосредственно из правила произведения. Действительно, на первой позиции – 5 вариантов символов, на второй – 4 оставшихся, на третьей – 3 оставшихся. Итого, по правилу произведения: 5 · 4 · 3 = 60 паролей.
п.2. Размещения с повторениями
Размещение с повторением – это упорядоченная ⟨n,k⟩ – выборка с повторениями. Общее количество размещений с повторениями: $$ mathrm{ overline{A}_n^k=n^k } $$
Например:
Для создания 3-значного пароля используются символы из алфавита {+,*,A,!,2}.
Сколько всего паролей можно составить?
По условию n=5, k=3. Рассматриваем размещение 5 символов по 3 позициям с повторениями: (mathrm{ overline{A}_5^3=5^3=125. })
Всего 125 паролей.
Результат можно получить непосредственно из правила произведения. Действительно, на первой позиции 5 вариантов символов, на второй – 5 вариантов, и на третьей – 5 вариантов. Итого, по правилу произведения: 5 · 5 · 5 = 53 = 125 паролей.
п.3. Примеры
Пример 1. Исследуйте различие между перестановкой без повторений и размещением без повторений ⟨3,2⟩-выборок для трёх разноцветных фишек. Изобразите полученные решения.
Рассматриваем фишки: 
1) Для перестановок, ⟨3,3⟩-выборок, получаем:
 |
В каждом ряду – отдельная перестановка. Видно, как образуется факториал. Для каждой отдельной фишки – одна перестановка. Для каждой пары фишек – две перестановки: 2 · 1. Когда добавляем третью, получаем: 3 · 2 · 1 Итого: P3 = 3 · 2 · 1 = 6 перестановок. |
2) Для размещений без повторений, ⟨3,2⟩-выборок, получаем:
 |
В каждом ряду – отдельное размещение. В первом столбце слева – 3 варианта по цвету. Во втором столбце остается только 2 варианта. Итого: (mathrm{A_3^2=3cdot 2=6}) размещений. |
Пример 2. Исследуйте перестановки без повторений и размещения для ⟨4,3⟩ выборок и для ⟨4,2⟩ выборок без повторений из 4 разноцветных фишек.
Изобразите полученные решения.
Рассматриваем фишки: 
Пример 3. Исследуйте различие между перестановкой с повторениями и размещением с повторениями. Сделайте вывод.
Перестановка с повторениями: сколько слов можно получить, переставляя буквы в слове «МАМА»? Запишите все эти слова в лексикографическом порядке.
Размещение с повторениями: сколько 4-буквенных слов можно получить, используя две буквы: «М» и «А»? Запишите все эти слова в лексикографическом порядке.
1) Для перестановки с повторениями получаем: begin{gather*} 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}{2cdot 2}=6 } end{gather*} Все 6 слов в лексикографическом порядке:
AAMM≺AMAM≺AMMA≺MAAM≺MAMA≺MMAA
2) Для размещения с повторениями получаем: begin{gather*} mathrm{ n=2, k=4 }\ mathrm{ overline{A}_2^4=2^4=16 } end{gather*} Все 16 слов в лексикографическом порядке:
AAAA≺AAAM≺AAMA≺AAMM≺AMAA≺AMAM≺AMMA≺AMMM≺
≺MAAA≺MAAM≺MAMA≺MAMM≺MMAA≺MMAM≺MMMA≺MMMM
Вывод: вариантов для размещения с повторениями получается больше, т.к. они включают слова с одной, тремя и четырьмя «М» и «А». А в перестановки с повторениями входят только слова с двумя «М» и двумя «А».
Пример 4. В базе данных с номерами телефонов содержатся все 7-значные номера.
1) Сколько в книге номеров, в которых цифры не повторяются?
2) Сколько в книге всего номеров?
3) Сколько в книге номеров, у которых 4 последних цифры одинаковые?
4) Сколько в книге номеров, у которых 4 последних цифры одинаковые, а 3 первых цифры отличаются от 4 последних?
1) Цифр – всего 10: {0;1;2;…;9}
n=10, k=7
Количество семизначных номеров без повторений равно количеству размещений без повторений: $$ mathrm{ A_{10}^7=10cdot 9cdot 8cdot 7cdot 6cdot 5cdot 4=604800 } $$ 2) Количество всех семизначных номеров равно количеству размещений с повторениями: $$ mathrm{ overline{A}_{10}^7=10^7=10 000 000 } $$ 3) 4 последних одинаковых цифры рассматриваем как одну «склеенную» цифру;
а 7-значный номер – как 4-значный, с последней «склеенной цифрой».
Количество всех4-значных номеров равно количеству размещений с повторениями: $$ mathrm{ overline{A}_{10}^4=10^4=10 000 } $$ 4) Если 10 вариантов 4 последних цифр: {0;1;2;…;9}, тогда для каждой из 3 первых цифр остается 9 вариантов. Если 10 вариантов для 3 первых цифр, тогда для 4 последних остается 9 вариантов.
По правилу суммы и произведения общее количество таких номеров: $$ mathrm{ N=frac{9^3cdot 10+10^3cdot 9}{2}=8145 } $$ Ответ: 1) 604 800 2) 10 000 000; 3) 10 000; 4) 8145.
Комбинаторика в школе теперь изучается с начальной школы.
Комбинаторика – это область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из элементов, принадлежащих данному множеству.
Рассмотрим сегодня, чем отличаются следующие условия: перестановка, размещение, сочетание.
Перестановка
Берутся все элементы и меняются только их места.
Например:
Сколько трехзначных чисел можно составить из цифр 1, 2, 6 без повторения цифр в числе?
Чтобы получить трехзначные числа без повторения необходимо переставить данные цифры.
126, 162, 216, 261, 621, 612.
Всего 6 вариантов.
Если речь пойдет о четырехзначном числе, то комбинаций получится гораздо больше. Но это количество подчиняется закону:
“!” – знак факториала.
Факториал числа — это произведение натуральных чисел от 1 до самого числа (включая данное число).
Сколько четырехзначных чисел можно получить из цифр 3, 7 , 4, 2 без повторения цифр в числе?
А теперь тоже самое, только с небольшим подвохом.
Сколько четырехзначных чисел можно получить из цифр 3, 0 , 4, 2 без повторения цифр в числе?
Подумайте какие числа необходимо исключить из подсчета и какое их количество?
Размещение
Размещения – это упорядоченные совокупности элементов, отличающиеся друг от друга либо составом, либо порядком элементов.
Для более простого понимания размещения рассмотрим следующий пример.
Есть буквы А, Б, В и Г. Сколько комбинаций из 2ух различных букв можно получить?
AБ, АВ, АГ, БА, БВ, БГ, ВА, ВБ, ВГ, ГА, ГБ, ГВ
Размещением (из n по k) называется упорядоченный набор из k различных элементов из некоторого множества различных n элементов.
В данном примере n=4, k=2, т.е. это размещение из 4 по 2 без повторения.
Общая формула, по которой можно всегда рассчитать число размещений без повторения:
Для создания 3-значного пароля используются символы из алфавита {+,*,A,!,2}. Сколько всего паролей без повторения символов можно составить?
По условию задачи n=5, k=3.
А если элементы могут повторяться?
Тогда
Смотрите как поменяется решение, если убрать одну фразу из задачи
Для создания 3-значного пароля используются символы из алфавита {+,*,A,!,2}. Сколько всего паролей без повторения символов можно составить?
Сочетание
Сочетание отличается от размещения тем, что в этом случае не важен порядок элементов.
В классе 4 человека (Петя, Света, Игорь, Ваня) наиболее успешно занимаются математикой. Сколькими способами можно выбрать из них двоих для участия в математической олимпиаде?
В данном случае комбинация ПС и СП будет одной и той же (Света и Петя)
Давайте посмотрим сколько сочетаний можно получить в данном примере:
ПС, ПИ, ПВ, СИ, СВ, ИВ
Т.е. всего 6 вариантов.
Есть и для сочетаний своя формула:
В классе 8 человек наиболее успешно занимаются математикой. Сколькими способами можно выбрать из них двоих для участия в математической олимпиаде?
Заданий связанных с комбинаторикой на экзамене в 9-ом классе НЕТ, но они могут косвенно встретиться в задании 10 на теорию вероятности.
Понимание таких тем будет полезно в дальнейшем…
Всем успешной подготовки
Продолжение следует…
