Сочетания размещения и перестановки – Перестановки, размещения и сочетания. Формулы.

Размещения, перестановки, сочетания с повторениями. Формула включения — исключения

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

Определение. Отображение множества первых натуральных чисел в данное множество , называется размещением с повторениями, составленным из данных элементов по .

Размещения с повторениями называются также конечными последовательностями.

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

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

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

   

Теорема. Число всевозможных размещений с повторениями из элементов по равно

   

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

Предположим, что число размещений с повторениями из элементов по равно . Составим из данных элементов всевозможные размещения с повторениями по элементу. Во всяком размещении с повторениями по элементу

   

первые элементов

   

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

Таким образом, число всех размещений -го порядка равно

   

Задача. Имеется различных книг, каждая в экземплярах. Сколькими способами может быть сделан выбор книг из числа данных?

Перестановки с повторениями

Всякое размещение с повторениями, в котором элемент повторяется раз, элемент повторяется раз и т.д. элемент повторяется раз, где , , , — данные числа, называется перестановкой с повторениями порядка

   

в которой данные элементы повторяются соответственно , , раз.

Теорема. Число различных перестановок с повторениями из элементов , в которых элементы повторяются соответственно раз, равно

   

Доказательство. Если мы будем считать все элементов перестановки с повторениями различными, то всего различных вариантов перестановок элементов — . Однако среди этих перестановок не все различны. В самом деле, все элементы мы можем переставлять местами друг с другом, и от этого перестановка не изменится. Точно так же, можем переставлять элементы , , , . Таким образом, всякая перестановка может быть записана способами. Следовательно, число различных перестановок с повторениями равно

   

Задача. Дано различных предметов. Сколькими способами можно разбить эти предметы на 3 группы так, чтобы первая группа содержала предметов, вторая предметов, а третья предметов?

Показать решение

Ответ.

   

Сочетания с повторениями

Определение. Если каждому элементу некоторого конечного множества поставлено в соответствие целое неотрицательное число — кратность данного элемента, то говорят, что задано сочетание с повторениями. Сумма кратностей всех элементов называется порядком сочетания.

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

Если — кратности элементов , то по определению есть порядок сочетания

   

Теорема. Число сочетаний с повторениями из элементов по выражается формулой

   

Пример. В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и картошка. Сколькими способами можно купить 7 пирожных?

Решение. Положим пирожные в коробку, а чтобы они не перепутались, разделим их картонными разделителями. Нужно 3 разделителя. Обозначения: 0 (картонки-разделители) и 1 — пирожные. Примерная покупка: 1110101101 — три наполеона, 1 эклер, 2 песочных и 1 картошка.

Итак два класса объектов 1 (7 штук) и 0 (3 штуки) — покупка — 10 объектов.

Два способа рассуждения:

(1) задача сводится к выбору мест для 7 пирожных (или для 3 разделителей) среди 10 объектов.

(2) другой способ рассуждения (эквивалентный). Надо разбить 10 мест на две группы: для 7 пирожных и 3 разделителей.

В чем особенность: объекты повторяются, причем один эклер на вкус неотличим от другого. Отсюда название: сочетания с повторениями. Можно представлять себе, что пирожные непрерывно пекут, так что они не переводятся, сколько ни ешь. Это совсем другая ситуация, чем в обычных сочетаниях!!!

Пусть заданы два числа: — число выбираемых элементов, и — число типов элементов, из которых производится выбор. Число сочетаний с повторениями порядка из элементов типов равно числу способов выбора мест для собственно выбираемых элементов различных классов, или, что то же: для разделителей между ними.

Итак, основная формула:

   

Задача. Имеется одинаковых предметов. Сколькими способами можно распределить эти предметы между лицами?

Сочетания с повторениями с дополнительными условиями

Сколько существует сочетания с повторениями таких, что в них обязательно входят элементы фиксированных типов?

Сразу возьмем по одному элементу указанного типа, и тогда уже сразу окажутся заняты мест. Остальные мест можно заполнять элементами прежних типов.

В частности, пусть число типов — числа выбранных элементов. Сколько существует сочетаний с повторениями, так что представлены хотя бы по одному все типы элементов?

Пример. шаров размещаются по ящикам. Сколько существует способов разместить их так, что пустых ящиков нет?

Решение. Пусть нолики — шарики, а единички — стенки ящиков (потребуется единичек). Две единички сразу кладем по краям.

Теперь положим между ними шарики-нолики, а далее нужно заполнить некоторые промежутки между ними так, чтобы между любыми двумя ноликами находилась не более одной единички. Значит, из промежутков между шариками нужно выбрать места для единичек. Всего таких способов .

Метод координат. Подсчет числа путей

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

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

   

По прежнему остается справедливым свойство симметрии .

Формула включения — исключения

Определение. Число элементов множества называется мощностью множества и обозначается .

Теорема. Пусть даны множества . Тогда количество элементов в объединении этих множеств можно найти по формуле:

   

Доказательство проводится по индукции. Пусть . Нужно доказать формулу

   

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

Предположим, что формула включения — исключения справедлива для множеств.
Докажем ее для множеств. Множество можно представить в виде

   

Тогда получаем (первое равенство по формуле включения — исключения для двух множеств):

   

Используя формулу

   

и формулу включения — исключения для множеств, получаем

   

В эту формулу  подставляем выражение, полученное ранее, и теорема доказана.

Задачи.

1. Есть три билета в различные театры. Сколькими способами они могут быть распределены между 25 школьниками, если каждый школьник может получить только один билет?
2. Есть три билета на КВН 1 апреля. Сколькими способами они могут быть распределены между 25 школьниками (более одного билета в руки не давать!!!)?
3. Телефонный номер состоит из 7 цифр. Насколько легче угадать правильный номер, если знать, что все его цифры различны?

4. В буфете продаются 5 сортов пирожков: с яблоками, с капустой, картошкой, мясом и грибами (цена всех пирожков одинакова). Скольким числом способов можно сделать покупку из 10 пирожков?

5. (Продолжение). Скольким числом способов можно сделать покупку так, чтобы попробовать пирожков всех видов?

6. (Продолжение). Скольким числом способов можно сделать покупку так, чтобы в нее вошло не менее двух пирожков с мясом и хотя бы один пирожок с яблоками?

7. Скольким числом способов можно вывести на арену цирка 5 львов и 4 тигра так, чтобы никакие два тигра не шли друг за другом (оказавшись рядом, они начинают драться)?

8. За круглым столом короля Артура сидят 12 рыцарей. Из них каждый враждует со своими соседями. Для участия в спецоперации по освобождению заколдованной принцессы нужно выбрать 5 рыцарей, но при этом нельзя посылать вместе рыцарей, враждующих друг с другом. Скольким числом способов это можно сделать?

9. Докажите формулу

   

10. Докажите, что число различных решений уравнения

   

в неотрицательных целых числах равно .

11. Докажите, что число различных решений уравнения

   

в натуральных числах равно .

12. Сколькими способами можно разложить 15 одинаковых шаров по 5 различным ящикам так, чтобы оказалось не более двух пустых ящиков?

13. Сколькими способами можно разложить 20 одинаковых шаров по 5 различным ящикам так, чтобы в каждом ящике оказалось не менее двух шаров?

14. Сколькими способами можно разложить 20 одинаковых шаров по 6 различным ящикам так, чтобы в каждом ящике оказалось не более 5 шаров?

15. Докажите, что число таких перестановок чисел , которые удовлетворяют условию при всех , равно

   

hijos.ru

11 Размещения, перестановки, сочетания » СтудИзба

§3. Размещения, перестановки, сочетания

При решении комбинаторных задач мы имеем дело с комбинациями из некоторых предметов. Эти комбинации могут отличаться одна от другой числом предметов, их составом или порядком.

Пример 1. Пять бойцов сержанта Сбруева.

В отделении сержанта Сбруева проходят службу 5 новобранцев: Белкин, Пенкин, Фенькин, Свечкин и Овечкин. В свободное от нарядов время сержант обучает их, как рассчитаться по порядку. По команде «В одну шеренгу становись!» солдаты выстраиваются справа от Сбруева и по команде «По порядку номеров рассчитайсь!» производят расчет: «первый-второй-третий-четвертый-пятый». После этого сержант перестраивает новобранцев по-новому и расчет повторяется. Сколько раз может Сбруев повторить это упражнение, используя только разные способы построения солдат?

Решение. Договоримся указывать порядок расположения солдат первыми буквами их фамилий. Например, комбинация ПСОФБ означает, что первым является Пенкин, вторым — Свечкин и т.д. Все комбинации отличаются одна от другой порядком букв и называются перестановками из пяти букв. Нам нужно найти число всех таких перестановок. Сначала мы выведем общую формулу, а потом закончим обсуждение примера.

Пусть дано множество из п элементов. Занумеруем все элементы каким-нибудь способом от 1 до п (в случае с новобранцами п = 5). Ясно, что занумеровать можно многими способами.

Определение. Перестановкой из п элементов называется всякий способ нумерации этих элементов.

Теорема 2. Число всех различных перестановок из п элементов равно п!

Доказательство. Всякую перестановку из п элементов можно получить с помощью п действий: первое действие — выбор первого элемента, второе действие — выбор второго элемента, и т.д., наконец, n-е действие — выбор элемента с номером п.

Первый элемент можно выбрать п различными способами; второй выбирается из оставшихся п — 1 элементов, поэтому число всех способов выполнения второго действия будет п — 1. После выбора второго элемента их останется п — 2, следовательно, число способов, которыми можно выполнить третье действие, будет п — 2. Таким образом, число способов, которыми выполняется очередное действие, будет на единицу меньше предыдущего. Следовательно, четвертое действие можно выполнить (п — 2) способами, пятое — (п — 4) способами и т.д., наконец, последнее действие — одним способом.

По правилу умножения (теорема 1) число всех способов выполнения действий, т.е. число всех перестановок, равно п(п — 1)(п — 2) • … • 1 = п!. Теорема доказана.

Число всех перестановок из п элементов обозначают Р_п. Согласно теореме 1 его можно найти по формуле

Р_п = п!.                                                                 (4)

Например, в случае с новобранцами (п = 5) мы получим Р₅ = 5! = 120.

УПРАЖНЕНИЯ

7. Выпишите все перестановки из букв а, b, с.

8. Сколько различных четырехзначных чисел можно составить из цифр 7, 2, 4, 9, если каждая цифра используется в записи числа только один раз?

9. Проверьте равенство Р₆ = 6Р₅.

10. Что больше: Р₇ или 2⁷?

11. С помощью цифр 1, 2, 3, 4, 5, 6, 7, 8, 9 закодируйте буквы А, В, Д, Е, Л, О, С, Т, Ь, заменив каждую букву какой-нибудь цифрой, и зашифруйте слово СЛЕДОВАТЕЛЬ. Каково число возможных вариантов кода?

Пример 2. Однажды утром

Однажды утром по улицам города Дрюкова на высокой скорости пронеслась машина. Она сбила зазевавшегося поросенка и скрылась в неизвестном направлении. Возвращавшийся из ресторана житель N, заметил номер автомобиля. Но когда появилась милиция, он с перепугу вспомнил только, что номер четырехзначный, все цифры разные, причем первая цифра 1, а последняя 4. Сколько автомобилей должна проверить автоинспекция?

Решение. Второй и третьей цифрами номера могут быть любые две из следующих: 2, 3, 5, 6, 7, 8, 9, 0. Выбрав любую пару цифр, автоинспектор получит номер какого-либо автомобиля. Например, пара 5, 7 дает номер 1574. Эти же цифры, но в другом порядке дают номер 1754. Следовательно, нужно перебрать столько номеров, сколько будет всевозможных комбинаций из восьми перечисленных цифр по две с учетом их порядка. Такие комбинации называют размещениями. В данном случае мы ищем число размещений из восьми цифр по две.

Определение. Размещением из п элементов по k называется всякая перестановка из k элементов, выбранных каким-либо способом из данных п.

Число всех размещений из п элементов по k обозначается А_п.

Теорема 3. Число всех размещений из п элементов по k вычисляется по формуле

                                                     (5)

Эта теорема доказывается так же, как и теорема 2. Каждое размещение можно получить с помощью k действий. Первое действие — выбор первого элемента — осуществляется п способами, второе действие — выбор второго элемента — (п — 1) способами, и т.д., наконец, последнее действие — выбор k-того элемента — (п — k + 1) способами. По правилу умножения число всех размещений будет п(п — 1) • • • (п — k + 1), что и требовалось доказать.

Вернемся к примеру 2. Согласно формуле (5) автоинспекция должна проверить  = 8 • 7 = 56 автомобилей.

УПРАЖНЕНИЯ

12. На трех карточках написаны буквы Р, А, К. Сколько различных слов можно составить, если словом считается любой набор из двух букв? Запишите эти слова.

13. В домоуправлении трудится 6 человек. Поступило распоряжение о премировании трех сотрудников (различными суммами). Сколькими способами можно это сделать?

14. На железнодорожной ветке Дрюково—Стуково имеется 10 станций. В течение дня с каждой станции на каждую другую выехало в точности по одному пассажиру. Сколько билетов было куплено в этот день?

15. Сколькими способами можно выбрать из семи разных книг какие-либо четыре и подарить их четырем милиционерам, занявшим первые четыре призовых места на конкурсе «Настоящий мужчина города Брюкова»?

16. Студенты одной группы должны сдать 5 экзаменов в течение восемнадцати дней. Сколькими способами можно составить расписание экзаменов, если в один день разрешается сдавать не более одного экзамена?

17. В течение дня из Брюкова в Стуково отправляется 8 автобусов. Разведенные супруги гражданин N и гражданка М не хотят ехать в одном автобусе. Сколькими способами они могут отправиться в разных автобусах?

Пример 3. День Брюквы

Согласно древнему обычаю, самый главный праздник в Брюкове — День Брюквы, проводится за счет средств городского бюджета и празднуется столько дней, сколько депутатов проголосует за то, чтобы праздник состоялся. Из десяти депутатов «за» проголосовали семь.

Каково число всех возможных вариантов голосования?

Решение. Мы должны найти число всех возможных групп из семи депутатов. Здесь порядок выбора не играет никакой роли, поэтому рассматриваемые комбинации отличаются одна от другой только составом лиц. Комбинации такого типа называются сочетаниями.

Определение. Сочетанием из п элементов по k называется всякая совокупность k элементов, выбранных каким-либо способом из данных п элементов.

Число всех сочетаний из п элементов по k обозначается . В примере 3 нужно найти .

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

                                       (6)

Доказательство. Возьмем какое-нибудь сочетание из п элементов по k

Переставляя эти элементы всевозможными способами, получим k! всех размещений из п по k одного и того же состава. Таким образом, из одного сочетания получается k! размещений. Следовательно, из С_п сочетаний получится С_п • k! размещений, т.е.

Отсюда, с учетом формулы (5) получаем:

,

что и требовалось доказать.

В примере 3 было п = 10, k = 7, поэтому число всех вариантов голосования присяжных равно

УПРАЖНЕНИЯ

18. В группе 30 студентов. Сколькими способами можно выбрать 6 делегатов для переговоров с администрацией института по вопросу о свободной продаже пива в студенческом буфете?

19. Сколькими способами можно поставить три пешки на белые клетки шахматной доски?

20. Для участия в соревнованиях тренер отбирает 5 спортсменов из двенадцати. Сколькими способами он может составить команду?

21. На окружности выбрано 7 точек. Сколько можно построить треугольников с вершинами в этих точках?

22. На карточке спортлото 36 клеток. Играющий должен отметить 4. Каково число всех возможных вариантов?

Числа сочетаний  обладают многими важными свойствами. Некоторые из них понадобятся нам в дальнейшем. Например,

=                                                                              (7)

Доказательство. Если из п элементов выбрать k элементов, то останется n — k элементов. Следовательно, каждому сочетанию из п элементов по k соответствует определенное сочетание из п элементов по п — k. Поэтому число тех и других сочетаний одинаково. Доказательство закончено.

Формула (7) сокращает вычисления, например:

Заметим, что формулы (4)-(6) допускают более широкое толкование. По определению полагают 0! = 1, А_п =1, =1.

Числа  также называют биномиальными коэффициентами, с их помощью записывается так называемая формула бинома Ньютона:

(а + b)^п = аⁿ + a^n-1b + a^n-1b² + … + аb^n-1 +bⁿ

Эту формулу можно доказать, например, методом математической индукции. Попробуйте сделать это самостоятельно .

ТИПОВЫЕ ЗАДАНИЯ

1. Анкета по изучению общественного мнения содержит 10 вопросов, на каждый из которых отвечающий дает один из трех ответов: «да», «нет», «не знаю». Найти число всех различных способов заполнения анкеты.

2. Одна из воюющих сторон захватила в плен 12 солдат, а вторая 14. Сколькими способами можно обменять 5 военнопленных?

3. В партии из ста деталей имеется 10 бракованных. Наудачу выбирают 4 детали. Сколькими способами можно это сделать? Сколько будет четверок, не содержащих бракованных деталей? Найдите отношение числа последних к числу первых.

studizba.com

перестановки, сочетания, размещения, правило умножения и сложения — Мегаобучалка

Классификация событий. Классическое определение вероятности.

Опытом или испытанием назыв. всякое осуществление опр. комплекса условий или действий при которых происходит соотв. явление. возможный результат опыта называется событием (А, В, С). Событие называется достоверным в данном опыте, если оно обязательно произойдет в этом опыте (Е). Событие называется невозможным в данном опыте, если оно не может произойти в этом опыте (О). Событие называется случайным в данном опыте если оно может произойти или не произойти в данном опыте. Два события называются совместными в данном опыте, если появление одного из них не исключает появление другого в этом опыте. Два события называются несовместными если они не могут произойти вместе при одном и том же испытании. Несколько событий называются несовместными если они попарно несовместны. Множество событий А1, А2, …, Аn называются полной группой событий, если они попарно несовместны, появление одного и только одного из них является достоверным событием. Два события называются противоположными, если появление одного из них равносильно не появлению другого ( ).События считают равновозможными, если нет оснований полагать, что одно событие является более возможным, чем другие. Каждое событие, которое может наступить в результате опыта называется элементарным исходом (элементарным событием). Элементарные исходы, при которых данное событие наступает называется благоприятствующим этому событию.

2. Вероятностью события А называется отношение числа элементарных исходов благоприятствующих данному событию к числу всех равновозможных образующих полную группу элементарных исходов опыта, в котором может появиться это событие. Обозначается как Р( А).

, где m – число элементарных исходов благоприятствующих событию А; n – число всех равновозможных элементарных исходов опыта, в котором может появиться событие А. Св-ва вероятности события: 1. вероятность достоверного события равна 1, т.е. Р (Е) = 1; 2. вероятность невозможного события равна 0, т.е. Р (Е) = 0; вероятность любого события удовл-ет неравенству 0 ≤ Р

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

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

Число возможных перестановок из n-элементов вычисляется по ф-ле: Рn = n!, где n !- произведение первых натуральных чисел, n! = 1*2*3*…*n. По определению 0!=1.

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

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

Число сочетаний из n-элементов по m: . Разница между сочетаниями и размещениями: в сочетании не учитывается порядок элементов. Замечание: выше предполагалось, что все n элементов различны. Если же некоторые элементы повторяются, то в этом случае множества с повторениями вычисляются по другим формулам. При решении задач комбинаторики используют следующие правила: правила суммы; если некоторый объект А может быть выбран из мн-ва объектов m способами, а другой объект В может быть выбран n способами, то выбрать либо А, либо В можно m+n способами; правило произведения: если объект А можно выбрать из мн-ва объектов m способами и после каждого такого выбора объект В можно выбрать n способами, то пара объектов АВ в указанном порядке может быть выбрана m*n способами.

 

 

megaobuchalka.ru

Формула для вычисления числа размещения. Перестановки, сочетания и размещения без повторений. Основная формула комбинаторики

Комбинаторика — это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Основы комбинаторики очень важны для оценки вероятностей случайных событий, т.к. именно они позволяют подсчитать принципиальновозможное количество различных вариантов развития событий.

Основная формула комбинаторики

Пусть имеется k групп элементов, причем i-я группа состоит из n i элементов. Выберем по одному элементу из каждой группы. Тогда общее число N способов, которыми можно произвести такой выбор, определяется соотношением N=n 1 *n 2 *n 3 *…*n k .

Пример 1. Поясним это правило на простом примере. Пусть имеется две группы элементов, причем первая группа состоит из n 1 элементов, а вторая — из n 2 элементов. Сколько различных пар элементов можно составить из этих двух групп, таким образом, чтобы в паре было по одному элементу от каждой группы? Допустим, мы взяли первый элемент из первой группы и, не меняя его, перебрали все возможные пары, меняя только элементы из второй группы. Таких пар для этого элемента можно составить n 2 . Затем мы берем второй элемент из первой группы и также составляем для него все возможные пары. Таких пар тоже будет n 2 . Так как в первой группе всего n 1 элемент, всего возможных вариантов будет n 1 *n 2 .

Пример 2. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если цифры могут повторяться?
Решение: n 1 =6 (т.к. в качестве первой цифры можно взять любую цифру из 1, 2, 3, 4, 5, 6), n 2 =7 (т.к. в качестве второй цифры можно взять любую цифру из 0, 1, 2, 3, 4, 5, 6), n 3 =4 (т.к. в качестве третьей цифры можно взять любую цифру из 0, 2, 4, 6).
Итак, N=n 1 *n 2 *n 3 =6*7*4=168.

В том случае, когда все группы состоят из одинакового числа элементов, т.е. n 1 =n 2 =…n k =n можно считать, что каждый выбор производится из одной и той же группы, причем элемент после выбора снова возвращается в группу. Тогда число всех способов выбора равно n k . Такой способ выбора в комбинаторики носит название выборки с возвращением.

Пример 3. Сколько всех четырехзначных чисел можно составить из цифр 1, 5, 6, 7, 8?
Решение. Для каждого разряда четырехзначного числа имеется пять возможностей, значит N=5*5*5*5=5 4 =625.

Рассмотрим множество, состоящие из n элементов. Это множество в комбинаторике называется генеральной совокупностью .

Число размещений из n элементов по m

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

Пример 4. Различными размещениями из трех элементов {1, 2, 3} по два будут наборы (1, 2), (2, 1), (1, 3), (3, 1), (2, 3),(3, 2). Размещения могут отличаться друг от друга как элементами, так и их порядком.

Число размещений в комбинаторике обозначается A n m и вычисляется по формуле:

Замечание: n!=1*2*3*…*n (читается: «эн факториал»), кроме того полагают, что 0!=1.

Пример 5 . Сколько существует двузначных чисел, в которых цифра десятков и цифра единиц различные и нечетные?
Решение: т.к. нечетных цифр пять, а именно 1, 3, 5, 7, 9, то эта задача сводится к выбору и размещению на две разные позиции двух из пяти различных цифр, т.е. указанных чисел будет:

Определение 2. Сочетанием из n элементов по m в комбинаторике называется любой неупорядоченный набор из m различных элементов, выбранных из генеральной совокупности в n элементов.

Пример 6 . Для множества {1, 2, 3}сочетаниями являются {1, 2}, {1, 3}, {2, 3}.

Число сочетаний из n элементов по m

Число сочетаний обозначается C n m и вычисляется по формуле:

Пример 7. Сколькими способами читатель может выбрать две книжки из шести имеющихся?

Решение: Число способов равно числу сочетаний из шести книжек по две, т.е. равно:

Перестановки из n элементов

Определение 3. Перестановкой из n элементов называется любой упорядоченный набор этих элементов.

Пример 7a. Всевозможными перестановками множества, состоящего из трех элементов {1, 2, 3} являются: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3), (3, 2, 1), (3, 1, 2).

Число различных перестановок из n элементов обозначается P n и вычисляется по формуле P n =n!.

Пример 8. Сколькими способами семь книг разных авторов можно расставить на полке в один ряд?

Решение: эта задача о числе перестановок семи разных книг. Имеется P 7 =7!=1*2*3*4*5*6*7=5040 способов осуществить расстановку книг.

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

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

Во-вторых, результат зависит от того, какой величины наборы элементов нам нужны.

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

Пример 9. На родительском собрании присутствует 20 человек. Сколько существует различных вариантов состава родительского комитета, если в него должны войти 5 человек?
Решение: В этом примере нас не интересует порядок фамилий в списке комитета. Если в результате в его составе окажутся одни и те же люди, то по смыслу для нас это один и тот же вариант. Поэтому мы можем воспользоваться формулой для подсчета числа сочетаний из 20 элементов по 5.

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

Задачи для самопроверки
1. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если цифры могут повторяться?

2. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?

3. В классе десять предметов и пять уроков в день. Сколькими способами можно составить расписание на один день?

4. Сколькими способами можно выбрать 4 делегата на конференцию, если в группе 20 человек?

5. Сколькими способами можно разложить восемь различных писем по восьми различным конвертам, если в каждый конверт кладется только одно письмо?

6. Из трех математиков и десяти экономистов надо составить комиссию, состоящую из двух математиков и шести экономистов. Сколькими способами это можно сделать?

Перестановками называют комбинации, состоящие из одних и тех же n различных элементов и отличающиеся только порядком их расположения. Число всех возможных перестановок

Рассмотрим пример : сколько трехзначных чисел можно составить из цифр 1,2,3, если каждая цифра входит в изображение числа только один раз?

Решение:

Или такой пример . Порядок выступления семи участников на студенческой конференции определяется жребием. Сколько различных вариантов жеребьевки при этом возможно?

Ре

www.chalt-1school.ru

Персональный сайт — Размещения. Перестановки. Сочетания

НАЗАД

Лемма. Пусть в множестве элементов, а в множестве — элементов. Тогда число всех различных пар , где будет равно .

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

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

Пусть у нас есть множество из трех элементов . Какими способами мы можем выбрать из этих элементов два? .

Определение. Размещениями множества из различных элементов по элементов называются комбинации, которые составлены из данных элементов по элементов и отличаются либо самими элементами, либо порядком элементов.

Число всех размещений множества из элементов по элементов обозначается через (от начальной буквы французского слова “arrangement”, что означает размещение), где и .

Теорема. Число размещений множества из элементов по элементов равно

Доказательство. Пусть у нас есть элементы . Пусть — возможные размещения. Будем строить эти размещения последовательно. Сначала определим — первый элемент размещения. Из данной совокупности элементов его можно выбрать различными способами. После выбора первого элемента для второго элемента остается способов выбора и т.д. Так как каждый такой выбор дает новое размещение, то все эти выборы можно свободно комбинировать между собой. Поэтому имеем:

Пример. Сколькими способами можно составить флаг, состоящий из трех горизонтальных полос различных цветов, если имеется материал пяти цветов?

Решение. Искомое число трехполосных флагов:

Определение. Перестановкой множества из элементов называется расположение элементов в определенном порядке.

Так, все различные перестановки множества из трех элементов — это

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

Число всех перестановок из элементов обозначается (от начальной буквы французского слова “permutation”, что значит “перестановка”, “перемещение”). Следовательно, число всех различных перестановок вычисляется по формуле

Пример. Сколькими способами можно расставить 8 ладей на шахматной доске так, чтобы они не били друг друга?

Решение. Искомое число расстановки 8 ладей

по определению!

Определение. Сочетаниями из различных элементов по элементов называются комбинации, которые составлены из данных элементов по элементов и отличаются хотя бы одним элементом (иначе говоря, -элементные подмножества данного множества из элементов).

Как видим, в сочетаниях в отличие от размещений не учитывается порядок элементов. Число всех сочетаний из элементов по элементов в каждом обозначается (от начальной буквы французского слова “combinasion”, что значит “сочетание”).

 

Числа

Все сочетания из множества по два — .

.

Свойства чисел

 

1. .

Действительно, каждому -элементному подмножеству данного элементного множества соответствует одно и только одно -элементное подмножество того же множества.

2. .

Действительно, мы можем выбирать подмножества из элементов следующим образом: фиксируем один элемент; число -элементных подмножеств, содержащих этот элемент, равно ; число -элементных подмножеств, не содержащих этот элемент, равно .

Треугольник Паскаля

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

.

Теорема.

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

1 способ. Выбираем первый член последовательности, затем второй, третий и т.д. член

2 способ. Выберем сначала элементов из данного множества, а затем расположим их в некотором порядке

Домножим числитель и знаменатель этой дроби на :

Пример. Сколькими способами можно в игре “Спортлото” выбрать 5 номеров из 36?

Искомое число способов

Задачи.

1. Номера машин состоят из 3 букв русского алфавита (33 буквы) и 4 цифр. Сколько существует различных номеров автомашин?
2. На рояле 88 клавиш. Сколькими способами можно извлечь последовательно 6 звуков?
3. Сколько есть шестизначных чисел, делящихся на 5?
4. Сколькими способами можно разложить 7 разных монет в три кармана?
5. Сколько можно составить пятизначных чисел, в десятичной записи которых хотя бы один раз встречается цифра 5?
6. Сколькими способами можно усадить 20 человек за круглым столом, считая способы одинаковыми, если их можно получить один из другого движением по кругу?
7. Сколько есть пятизначных чисел, делящихся на 5, в записи которых нет одинаковых цифр?
8. На клетчатой бумаге со стороной клетки 1 см нарисована окружность радиуса 100 см, не проходящая через вершины клеток и не касающаяся сторон клеток. Сколько клеток может пересекать эта окружность?
9. Сколькими способами можно расставить в ряд числа так, чтобы числа стояли рядом и притом шли в порядке возрастания?
10. Сколько пятизначных чисел можно составить из цифр 1, 2, 3, 5, 7, 8, если каждую цифру можно использовать только один раз?
11. Из слова РОТ перестановкой букв можно получить еще такие слова: ТОР, ОРТ, ОТР, ТРО, РТО. Их называют анаграммами. Сколько анаграмм можно составить из слова ЛОГАРИФМ?
12. Назовем разбиением натурального числа представление его в виде суммы натуральных чисел. Вот, например, все разбиения числа 4:

Разбиения считаются разными, если они отличаются либо числами, либо порядком слагаемых.

Сколько существует различных разбиений числа 11 на 4 слагаемых?
13. Сколько существует трехзначных чисел с невозрастающим порядком цифр?
14. Сколько существует четырехзначных чисел с невозрастающим порядком цифр?
15. Сколькими способами можно рассадить в ряд 17 человек, чтобы и оказались рядом?
16. девочек и мальчиков рассаживаются произвольным образом в ряду из мест. Сколькими способами можно их рассадить так, чтобы никакие две девочки не сидели рядом?
17. девочек и мальчиков рассаживаются произвольным образом в ряду из мест. Сколькими способами можно их рассадить так, чтобы все девочки сидели рядом?

matklass.ucoz.ru

Дискретная математика — Формулы комбинаторики

Перестановки    

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

Перестановки — это комбинации, состоящие из одних и тех же элементов и отличающиеся только порядком расположения этих элементов. Возьмем n различных элементов a₁, a₂, a₃, … a_n; будем переставлять эти элементы всевозможными способами, оставляя без изменения число элементов и меняя только порядок их расположения. Обозначим общее число полученных таким образом перестановок P(n). P — первая буква французского словаpermutation — перестановка.

Составив таблицу перестановок для n элементов и применив (n — 1) раз правило произведения, получим число всех возможных перестановок:

P(n) = n • (n -1) • (n — 2) • … • 3 • 2 • 1 = n!

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

Задача: шесть человек могут в разном порядке сесть за круглый стол, сколько существует способов разместить эти шесть человек за столом?

Решение: т.к. все люди различны и  их комбинации различаются только порядком следования, то мы имеем перестановки без повторений. Определим их число:

Р(6) = 6! = 1 • 2 • 3 • 4 • 5 • 6 = 720.

2) Перестановки с повторениями

Рассматривая различные перестановки, мы предполагали, что все n элементов различны. Если же некоторые элементы повторяются, то в этом случае комбинации с повторениями вычисляют по другим формулам.

Если среди n элементов есть n₁ элементов одного вида, n₂ элементов другого вида и т.д., n_k элементов к-го вида, то имеем перестановки с повторениями, их число:

, где n₁+…+n_k = n.

Задача: сколько различных «слов» можно составить из букв слова ДЕД, МАТЕМАТИКА.

Решение: имеем перестановки с повторениями.

А) ДЕД    n=3, k=2, n₁=2, n₂=1

P₃(2, 1) = 3!/(2! • 1!) = 6 / 2 = 3;

Б) МАТЕМАТИКА n=10, k=6, n₁=2, n₂=3, n₃=2, n₄=n₅=n₆=1

P₁₀(2,3,2,1,1,1)=10!/(2! • 3! • 2!)=2•4•5•6•7•9•10 = 134 400.

 Размещения

1) Размещения без повторений.

Размещениями называют комбинации, составленные из n данных элементов по k элементов (k<=n, k>0), которые отличаются либо составом элементов, либо порядком расположения элементов. Обозначаются размещения A_n^k . А — первая буква французского слова arrangement, что в переводе означает «размещение», «приведение в порядок». Число всех возможных размещений находится по формуле:

.

Задача: расписание одного дня состоит из двух пар. Определить число вариантов расписания при выборе из пяти дисциплин, если не может быть одинаковых пар.

Решение: имеем размещения без повторений из пяти элементов по два, из число: .

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

Пусть существуют n различных элементов. Выберем из них m штук, действуя по следующему принципу: возьмем любой элемент, но не будем устанавливать его в какой-либо ряд, а просто запишем под номером 1 его название, сам же элемент вернем к остальным элементам. Затем опять из всех n элементов выберем один, запишем его название под номером 2 и снова вернем элемент обратно. Будем выполнять эти операции, пока не получим m названий. Размещения с повторениями вычисляются по формуле:

.

Задача: сколько четырехзначных номеров можно составить из 10 цифр?

Решение: имеем размещения с повторениями из 10 элементов по 4, их число: .

Сочетания

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

Сочетаниями называют комбинации, составленные из n различных элементов по k (k =< n) элементов, которые отличаются хотя бы одним элементом. Сочетания обозначаются: C_n^k C — первая буква французского слова combinasion— сочетание.

Составим из n элементов всевозможные сочетания по k элементов в каждом. Их будет C_n^k . Внутри каждого сочетания, состоящего из k элементов, образуем всевозможные комбинации, учитывающие порядок следования в них элементов. Таких комбинаций будет P_k, т.к. мы в нашем сочетании образовываем перестановки. Всего различных комбинаций из n элементов по k в каждой, отличающихся друг от друга либо составом (элементами), либо порядком их следования, будет C_n^k • P_k . Но такие комбинации называются размещениями. Таким образом, A_n^k = C_n^k • P_k, тогда:

.

Задача: в шахматном турнире участвует 7 человек; сколько партий будет сыграно, если между любыми двумя участниками должна быть сыграна партия?

Решение: имеем сочетания без повторений из 7 элементов по 2; их число:  .

2) Сочетания с повторениями.

Если в сочетаниях некоторые элементы (или все) могут оказаться одинаковыми, то такие сочетания называются сочетаниями с повторениями. Их число определяется по формуле:                               .

Задача: сколько наборов из 7 пирожных можно составить, если в продаже имеется 4 сорта пирожных?

Решение: имеем сочетания с повторениями из четырех по 7 по, их число: .

 

_{Вопросы и задания!}

 1. Города A,B,C,D,E попарно соединены дорогами. Сколько разных маршрутов путешествия из города А в город Е с посещением еще каких-то двух городов можно составить? Предполагается, что в маршруте каждый город присутствует не более одного раза, и маршруты, отличающиеся порядком следования городов, различны.

 

2. Сколькими способами можно распределить среди 20 студентов группы четыре билета в театр, если

• билеты на один спектакль, и каждый студент может получить не более одного билета; 
• билеты на один спектакль, и каждый студент может получить сколько угодно билетов;
• все билеты на разные спектакли, и каждый студент может получить не более одного билета;
• все билеты на разные спектакли, и каждый студент может получить сколько угодно билетов?  

3. Есть 4 билета на концерт, 5 билетов в театр и 7 билетов в цирк. Сколькими способами их можно распределить среди 25 студентов группы, если каждый студент может получить не более одного билета на каждое мероприятие? Билеты на одно мероприятие считаются равнозначными.

 

4. Девочка нанизала n разных бусин на английскую булавку. Сколько различных украшений может получиться таким образом? Два украшения различны, если они отличаются порядком следования бусин на булавке. 

 

5. У англичан принято давать детям несколько имен. Сколькими способами можно назвать ребенка, если ему дадут не более трех имен из 300 возможных, и при этом

• имена могут повторяться;
• все имена различны?

Назад  В начало  Далее

diskmat.ucoz.ru

Перестановки сочетания и размещения (с и без повторений) — Дискретная математика. Теория множеств . Теория графов . Комбинаторика.

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

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

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

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

 

Содержание

• 1 Количество размещений
• 2 Размещение с повторениями
  • 2.1 Количество размещений с повторениями
• 3 См. также
• 4 Ссылки

 

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

Количество размещений из 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 и может повторяться, равно:

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

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

Так, например, наборы (3-элементные сочетания, подмножества, ) {2, 1, 3} и {3, 2, 1} 6-элементного множества {1, 2, 3, 4, 5, 6} () являются одинаковыми (в то время как размещения были бы разными) и состоят из одних и тех же элементов {1,2,3}.

В общем случае число, показывающее, сколькими способами можно выбрать  элементов из множества, содержащего  различных элементов, стоит на пересечении -й диагонали и -й строки треугольника Паскаля.^[1]

 

Содержание

• 1 Число сочетаний
• 2 Сочетания с повторениями
• 3 См. также
• 4 Примечания
• 5 Ссылки

 

Число сочетаний[править ]

Основная статья: Биномиальный коэффициент

Число сочетаний из  по  равно биномиальному коэффициенту

При фиксированном  производящей функцией последовательности чисел сочетаний , , , … является:

Двумерной производящей функцией чисел сочетаний является

Сочетания с повторениями[править ]

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

Число сочетаний с повторениями из  по  равно биномиальному коэффициенту

Доказательство  

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

Двумерной производящей функцией чисел сочетаний с повторениями является:

intellect.icu