Формула количества размещений без повторений

Формула количества размещений без повторений

Пусть имеется $k$ различных шаров, и их нужно разложить по $n$ различным ящикам (на число шаров в ящиках ограничений нет — ящик может вместить как все шары, так и остаться пустым).

Берем последовательно каждый из $k$ шаров. Размещаем его в любой из $n$ ящиков — это можно сделать $n$ способами (все ящики одинаково привлекательны:)). И так повторяем $k$ раз для всех шаров. Получится произведение из $k$ сомножителей:

Это и есть число размещений с повторениями из $n$ объектов по $k$. Более содержательная и сложная формула — размещений без повторений — рассмотрена здесь.

Примеры решений

Рассмотрим типичные задачи на эту комбинаторную формулу.

Пример 1. В лифт 8-этажного дома вошли 4 пассажира. Сколькими способами они могут выйти (выход возможен на любом этаже, начиная со второго).

Решение. Сначала порассуждаем. Рассмотрим пассажира, у него есть 7 способов выбрать этаж для выхода (2, 3, 4, 5, 6, 7 или 8). И так поступает каждый из пассажиров, поэтому способов выхода $N=7 cdot 7 cdot 7 cdot 7 =7^4=2401$.

Или иначе, с помощью формулы: считаем, что у нас есть $n=7$ этажей и на них нужно разместить произвольно $k=4$ пассажиров, то по формуле размещений с повторениями $N=overline_7^4= 7^4=2401$.

Пример 2. Сколько трехзначных чисел можно составить из нечетных цифр?

Решение. Пусть у нас есть $k=5$ нечетных цифр (1, 2, 3, 4, 5). Их нужно расставить на $n=3$ места (так как число трехзначное: единицы, десятки, сотни). По формуле размещений с повторениями $N=overline_5^3= 5^3=125$ чисел.

Найти число размещений c повторениями из n элементов по k

Видеоролик о размещениях с повторениями

Не все понятно? Посмотрите наш видеообзор для формулы размещений: как использовать Excel для нахождения числа размещений с повторениями, как решать типовые задачи.

Читайте также:  Септик для дачи непостоянного проживания отзывы

Расчетный файл из видео можно бесплатно скачать

Подсчет числа перестановок, размещений и сочетаний.

Ниже калькулятор, подсчитывающий число перестановок, размещений и сочетаний. Под ним, как водится, ликбез, если кто подзабыл.

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

Итак, есть множество из n элементов.

Вариант упорядочивания данного множества называется перестановкой (permutation).
Например, есть множество, состоящее из 3 элементов — А, В, и С. Пример перестановки — СВА. Число всех перестановок из n элементов:

Пример: Для случая А, В, С число всех перестановок 3! = 6. Перестановки: АВС, АСВ, ВАС, ВСА, САВ, СВА

Если из множества n элементов выбирают m в определенном порядке, это называется размещением (arrangement).
Пример размещения из 3 по 2: АВ или ВА — это два разных размещения. Число всех размещений из n по m

Пример: Для случая А, В, С число всех размещений из 3 по 2 равно 3!/1! = 6. Размещения: АВ, ВА, АС, СА, ВС, СВ

Также бывают размещения с повторениями, как ясно из названия, элементы на определенных позициях могут повторяться.
Число всех размещений из n по m с повторениями:

Пример: Для случая А, В, С число всех размещений из 3 по 2 с повторениями равно 3*3 = 9. Размещения: AA, АВ, АС, ВА, BB, ВС, СА, СВ, CC

Если из множества n элементов выбирают m, и порядок не имеет значения, это называется сочетанием (combination).
Пример сочетания из 3 по 2: АВ. Число всех сочетаний из n по m

Пример: Для случая А, В, С число всех сочетаний из 3 по 2 равно 3!/(2!*1!) = 3. Сочетания: АВ, АС, СВ

Приведем до кучи формулу соотношения между перестановками, размещениями и сочетаниями:

Рассмотрим задачу подсчета числа выборок из данного множества в общем виде. Пусть имеется некоторое множество N, состоящее из n элементов. Любое подмножество, состоящее из m элементов можно рассматривать без учета их порядка, так и с его учетом, т.е. при изменении порядка переходим к другой m – выборке.

Читайте также:  Тормозит звук на компе

Сформулируем следующие определения:

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

Размещением без повторения из n элементов по m называется всякое упорядоченное подмножество множества N, содержащее m различных элементов.

Из определения следует, что два размещения отличаются друг от друга, как элементами, так и их порядком, даже если элементы одинаковы.

Теорема 3. Число размещений без повторения равно произведению m сомножителей, наибольшим из которых является число n. Записывают:

Перестановки без повторений

Перестановками из n элементов называются различные упорядочения множества N.

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

Теорема 4. Число различных перестановок без повторений вычисляется по формуле

Сочетания без повторений

Сочетанием без повторения из n элементов по m называется любое неупорядоченное подмножество множества N, содержащее m различных элементов.

Из определения следует, что два сочетания различаются только элементами, порядок не важен.

Теорема 5. Число сочетаний без повторений вычисляют по одной из следующих формул:

Пример 1. В комнате 5 стульев. Сколькими способами можно разместить на них

а) 7 человек; б) 5 человек; в) 3 человека?

Решение: а) Прежде всего надо выбрать 5 человек из 7 для посадки на стулья. Это можно сделать способом. С каждым выбором конкретной пятерки можно произвестиперестановок местами. Согласно теореме умножения искомое число способов посадки равно.

Замечание: Задачу можно решать, используя только теорему произведения, рассуждая следующим образом: для посадки на 1-й стул имеется 7 вариантов, на 2-й стул-6 вариантов, на 3-й -5, на 4-й -4 и на 5-й -3. Тогда число способов посадки 7 человек на 5 стульев равно . Решения обоими способами согласуются, так как

б) Решение очевидно —

в) — число выборов занимаемых стульев.

— число размещений трех человек на трех выбранных стульях.

Общее число выборов равно .

Читайте также:  Как взломать стр в контакте

Не трудно проверить формулы ;

;

— число всех подмножеств множества, состоящего из n элементов.

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

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

Число размещений с повторением обозначают и вычисляют по формуле, представляющей собой следствие из теоремы умножения:

Пример 2. Пусть дано множество из трех букв N = . Назовем словом любой набор из букв, входящих в это множество. Найдем количество слов длиной 2, которые можно составить из этих букв: .

Замечание: Очевидно, размещения с повторением можно рассматривать и при .

Пример 3. Требуется из букв , составить всевозможные слова длиной 3. Сколькими способами это можно сделать?

Ответ:

Ссылка на основную публикацию
Филипс диамонд вижн h7
Заказав на экзисте лампы для ближнего света Philips Blue Vision Ultra (пост удалил), понял, что сильно поторопился, поскольку ничего не...
Усилитель сигнала для тв антенны отзывы
Характеристика в рейтинге 1 Alcad AL-200 Высокое качество во всех аспектах эксплуатации. Самый популярный усилитель в России 2 Eurosky SWA-105...
Усилитель сотового сигнала отзывы
Нашел вот еще информацию что Mobi-900 стал занял 1 место в рейтинге репитеров по версии журнала Provider-Review: http://provider-review.ru/reyting-usiliteley-sotovoy-svyazi.html А вот...
Фигуры для оформления текста
Методические рекомендации В Word 2007 можно добавлять два типа графики – Рисунки и Фигуры. Рисунок – изображение, созданное в другом...
Adblock detector