Онлайн калькулятор: Комбинаторика. Генератор сочетаний.

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

Описание алгоритма генерации под калькулятором.

Комбинаторика. Генератор сочетаний из N по M.

addimport_exportmode_editdelete

Множество

Размер страницы: chevron_leftchevron_right

Множество

Сохранить Отменить

Импортировать данныеОшибка импорта

Импортировать Назад Отменить

save Сохранить share Поделиться extension Виджет

Алгоритм

Комбинации генерируются в лексикографическом порядке. Алгоритм работает с порядковыми индексами элементов множества.
Рассмотрим алгоритм на примере.
Для простоты изложения рассмотрим множество из пяти элементов, индексы в котором начинаются с 1, а именно, 1 2 3 4 5.
Требуется сгенерировать все комбинации размера m = 3.
Сначала инициализуется первая комбинация заданного размера m — индексы в порядке возрастания

1 2 3
Далее проверяется последний элемент, т. е. i = 3. Если его значение меньше n — m + i, то он инкрементируется на 1.
1 2 4
Снова проверяется последний элемент, и опять он инкрементируется.
1 2 5
Теперь значение элемента равно максимально возможному: n — m + i = 5 — 3 + 3 = 5, проверяется предыдущий элемент с i = 2.
Если его значение меньше n — m + i, то он инкрементируется на 1, а для всех следующих за ним элементов значение приравнивается к значению предыдущего элемента плюс 1.
1 (2+1)3 (3+1)4 = 1 3 4
Далее снова идет проверка для i = 3.
1 3 5
Затем — проверка для i = 2.
1 4 5
Потом наступает очередь i = 1.
(1+1)2 (2+1)3 (3+1)4 = 2 3 4
И далее,
2 3 5
2 4 5
3 4 5 — последнее сочетание, так как все его элементы равны n — m + i.

planetcalc.ru

Урок 8: Комбинаторика — 100urokov.ru

План урока:

Комбинаторика и ее основные принципы

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

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

Размещения

Сочетания

 

Комбинаторика и ее основные принципы

Очень часто приходится решать задачи, в которых надо посчитать количество возможных вариантов для той или иной ситуации. Например, сколько позиций может возникнуть на шахматной доске после первого хода обоих игроков? Сколько разных паролей длиною в десять символов можно записать, если ни один символ не использовать дважды? Сколько разнообразных комбинаций чисел может выпасть при игре в лотерею «6 из 49»? На все эти вопросы помогает ответить специальный раздел математики, называемый комбинаторикой. Почти всегда комбинаторную задачу можно сформулировать так, чтобы ее вопрос начинался словами «сколькими способами…».

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

 

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

Ответ. Таких способов ровно 15.

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

Несмотря на формулировку, по сути это очень простое правило.

 

Пример. В магазине продается 14 телевизоров Panasonic и 17 телевизоров Sony. Петя хочет купить один телевизор. Сколько у него вариантов покупки?

Решение. По правилу сложения Петя может выбрать один из 14 + 17 = 31 телевизоров.

Ответ: 31 телевизор.

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

Проиллюстрируем это правило.

 

Пример. В секции бадминтона 15 мальчиков и 20 девочек. Тренер должен отправить на соревнования смешанную пару. Сколько вариантов действий у него?

Решение. Тренер может составить 15•20= 300 разнополых пар из своих воспитанников.

Ответ: 300

 

Пример. Пете нужно купить технику для компьютера. В магазине продается 20 различных клавиатур, 25 моделей геймпадов и 30 компьютерных мышей. Купить надо по одному экземпляру каждого из этих устройств. Сколько вариантов покупки есть у него?

Решение. Сначала подсчитаем число возможных пар «клавиатура-геймпад». Их количество равно 20•25 = 500. Теперь составим «тройку» из одной из 500 пар и одной из 30 мышей. Число троек равно 500•30 = 15000.

Ответ: 15000

Правила сложения и умножения можно комбинировать.

 

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

Решение. Очевидно, что слов из одной буквы можно составить ровно 30. Количество двухбуквенных слов равно количеству пар, которые можно составить из этих букв, то есть 30•30 = 900. Трехбуквенных слов можно составить 30•30•30 = 27000. Всего же слов длиною не более 3 букв будет

30 + 900 + 27000 = 27930

Ответ: 27930

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

 

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

Рассмотрим простейшую комбинаторную задачу. На полке расставляют по порядку книги. Их ставят вертикально друг за другом. Сколькими способами можно расставить на полке 2 книги? Очевидно, что двумя:

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

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

Например, если в забеге на 100 метров стартует 8 спортсменов, то они образуют множество участников забега. После финиша становится известно, кто занял 1-ое место, кто оказался вторым или третьим, а кто стал последним. Результат забега будет перестановкой, ведь он представляет собой список спортсменов с указанием их мест, то есть он определяет порядок между ними.

Вернемся к примеру с книгами. Обозначим количество возможных перестановок

n элементов как Р_n. Две книжки можно расставить двумя разными способами, поэтому Р₂ = 2. Обозначим эти перестановки как АБ и БА. Сколько способов расстановки есть в случае трех книжек? Их все можно получить из вариантов с 2 книжками, добавляя между ними книгами ещё один том:

Видно, что между 2 книгами есть три позиции, на которые можно поставить 3-ий том. Общее количество вариантов равно произведению числа этих позиций и количества вариантов для 2 книг, то есть Р₃ = 3•Р₂ = 3•2 = 6:

Итак, мы имеем 6 перестановок для 3 книг:

ВАБ

АВБ

АБВ

ВБА

ВБА

БАВ

А сколько перестановок существует для 4 книг? Снова-таки, между тремя книгами 4-ый том можно поставить четырьмя способами:

То есть из перестановки трех книг АБВ можно получить 4 перестановки:

ГАБВ

АГБВ

АБГВ

АБВГ

Всего существует 6 перестановок для 3 книг (Р₃ = 6), и для каждой из них можно построить 4 перестановки из 4 книг. Получается, что общее количество перестановок 4 книг равно

Р₄ = 4Р₃ = 4•6 = 24.

Продолжая подобные рассуждения, можно убедиться, что количество перестановок 5 предметов в 5 разбольше, чем перестановок для 4 объектов:

Р₅ = 5Р₄

И вообще, если число перестановок n объектов равно Р_n, то количество перестановок (n + 1)объекта равно в (n + 1)раз больше:

Р_n+1 = (n + 1)Р_n

При этом отметим, что 1 книгу можно расставить на полке только одним способом:

То есть Р₁ = 1. Теперь выпишем значения чисел Р при разном количестве переставляемых предметов, используя формулуР_n+1 = (n + 1)Р_n

Р₁ = 1

Р₂ = 2•Р₁= 2•1 = 2

Р₃ = 3Р₂ = 3•2•1 = 6

Р₄ = 4Р₃ = 4•3•2•1 = 24

Р₅ = 5Р₄ = 5•4•3•2•1 = 120

Видно, что количество перестановок n объектов равно произведению всех натуральных чисел от 1 до n. В математике есть специальная функция для вычисления значения этого произведения. Она называется факториалом и обозначается восклицательным знаком.

Например, факториал 6 вычисляется так:

6! = 1•2•3•4•5•6 = 720

Мы убедились на примере с книгами, что количество перестановок из n различных объектов, которое обозначается как Р_n, равно n!.

Относительно факториала надо заметить несколько важных моментов. Во-первых, очевидно, что факториал единицы равен 1:

1! = 1

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

0! = 1

Объяснить это можно так. Факториал числа можно представить как произведение этого числа и факториала предыдущего числа, например:

5! = 1•2•3•4•5 = (1•2•3•4)•5 = 4!•5

7! = 1•2•3•4•5•6•7 = (1•2•3•4•5•6)•7 = 6!•7

В общем случае формула выглядит так:

n! = (n– 1)!•n

Из неё несложно получить, что

(n– 1)! = n!/n

Например: 5! = 4!•5

Подставив в эту формулу единицу, получим

(1 – 1)! = 1!/1

0! = 1/1

0! = 1

 

Пример. Сколькими способами тренер может расставить 4 участников эстафеты 4х400 м по этапам эстафеты?

Решение. Количество таких способов равно числу перестановок 4 различных объектов Р₄:

Р₄ = 4! = 1•2•3•4 = 24

Ответ: 24

 

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

Решение. В данном случае расписание занятий – это порядок, в котором Вася в течение недели будет изучать иностранные языки, например:

Такое расписание можно описать последовательностью символов:

Ф, Ан, И, К, Я, Ар, П

Создавая расписание, Вася переставляет 7 языков, поэтому общее количество расписаний равно 7!:

Р₇ = 1•2•3•4•5•6•7 = 5040

Ответ: 5040

 

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

Решение. Общее количество перестановок 5 цифр составляет Р₅. Однако нельзя начинать запись числа с нуля. Так как, перестановка 12340 – это пятизначное число (двенадцать тысяч триста сорок), а перестановка 03241 – не является пятизначным числом.

Расстановок, начинающихся с нуля, ровно Р₄, поэтому общее количество допустимых цифр равно Р₅ – Р₄:

Р₅ – Р₄ = 5! – 4! = 120 – 24 = 96

Ответ: 96

 

Пример. На полке расставляют 7 книг, однако 3 из них образуют трехтомник. Тома трехтомника должны стоять друг за другом и в определенном порядке. Сколько существует способов расстановки книг?

Решение. Будем считать трехтомник одной книгой. Тогда нам надо расставить 5 книг

Р₅ = 5! = 120

Ответ: 120

 

Пример. Необходимо расставить 7 книг на полке, но три из них принадлежат одному автору. Их надо поставить друг с другом, но они могут стоять в любом порядке. Сколько возможно перестановок книг.

Решение. Снова будем считать три книги как один трехтомник. Получается, что существует 5! = 120 вариантов. Однако каждому из них соответствует 3! = 6 расстановок книг внутри трехтомника, например:

В итоге на каждую из 120 расстановок приходится 6 вариантов расстановки трехтомника, а общее число расстановок равно, согласно правилу умножения, произведению этих чисел:

120•6 = 720

Ответ: 720

 

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

До этого мы рассматривали случаи, когда все переставляемые объекты были различными. Однако порою некоторые из них не отличаются друг от друга. Пусть на полке надо расставить 3 книги, но две из них одинаковые. Сколько тогда существует перестановок? Общее число перестановок 3 книг составляет 3! = 6:

Здесь одинаковые книги отмечены как А и А1. Очевидно, что 1-ый и 2-ой варианты (А1АБ) и (АА1Б) на самом деле не отличаются друг от друга. В них отличается лишь порядок одинаковых книг А и А1. В первом случае за А1 следует А, а во втором, наоборот, за А следует А1. Тоже самое можно сказать про варианты 3 и 4, 5 и 6. Получается, что все возможные перестановки можно разбить на группы, в которых находятся «перестановки-дубликаты»:

А1АБ и АА1Б

А1БА и АБА1

БА1А и БАА1

В каждой группе находится ровно по два «дубликата». Почему именно по два? Это число равно количеству перестановок одинаковых книг. Так как одинаковых томов 2, а Р₂ = 2, то в каждой группе по 2 «дубликата». Действительно, если бы мы «убрали» с полки все книги, кроме повторяющихся, то там осталось бы только 2 одинаковых тома, которые можно переставить двумя способами.

Для того чтобы найти количество «оригинальных» перестановок, надо их общее количество поделить на число дубликатов в каждой группе.

6:2 = 3

Пусть теперь надо расставить 4 книги, из которых 3 одинаковы. Обозначим тома как А, А1, А2 и Б. Всего можно записать 4! = 24 перестановки. Однако каждые 6 из них будут дублировать друг друга. То есть их можно разбить на группы, в каждой из которых будет 6 идентичных «дубликатов»:

1-ая группа: БАА1А2, БАА2А1, БА1АА2, БА1А2А, БА2АА1, БА2А1А

2-ая группа: АБА1А2, АБА2А1, А1БАА2, А1БА2А, А2БАА1, А2БА1А

3-ая группа: АА1БА2, АА2БА1, А1АБА2, А1А2БА, А2АБА1, А2А1БА

4-ая группа: АА1А2Б, АА2А1Б, А1АА2Б, А1А2АБ, А2АА1Б, А2А1АБ

И снова для подсчета числа оригинальных перестановок надо из общее число расстановок поделить на количество дубликатов в каждой группе:

Р₄/Р₃ = 4!/3! = 24/6 = 4

Для обозначения перестановок с повторениями используется запись

Р_n(n₁, n₂, n₃,… n_k)

где n – общее количество объектов, а n₁, n₂, n₃,… n_k – количество одинаковых элементов. Например, в задаче с 4 книгами мы искали величину Р₄(3, 1), потому что всего книг было 4, но они были разбиты на две группы, в одной из которых находилось 3 одинаковых тома (буквы А, А1, А2), а ещё одна книга (Б) составляла вторую группу. Мы заметили, что для вычисления числа перестановок с повторениями надо общее число перестановок делить на количество дублирующих перестановок. Формула в общем случае выглядит так:

 

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

Решение. Вася должен расставить 3 урока испанского и 4 урока английского, тогда n₁ = 3, а n₂ = 4. Общее количество уроков равно 3 + 4 = 7. Тогда

Ответ: 35

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

 

Пример. У мамы есть 3 яблока, 2 банана и 1 апельсин. Эти фрукты она распределяет между 6 детьми. Сколькими способами она может это сделать, если каждый должен получить по фрукту?

Решение. Всего есть три группы фруктов. В первой находится 3 яблока, поэтому n₁ = 3. Во второй группе 2 банана, поэтому n₂ = 2. В третьей группе только 1 апельсин, поэтому n_k = 1. Общее число фруктов равно 6. Используем формулу:

Ответ: 60

В знаменателе формулы для перестановок с повторениями мы записываем число объектов в каждой группе одинаковых предметов. Так, если переставляются 3 яблока, 2 банана и 1 апельсин, то в знаменателе мы пишем 3!•2!•1!. Но что будет, если в каждой группе будет находиться ровно один уникальный объект? Тогда мы запишем в знаменателе произведение единиц:

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

 

Размещения

Пусть в футбольном турнире участвуют 6 команд. Нам предлагают угадать те команды, которые займут призовые места (то есть первые три места). Сколько вариантов таких троек существует?

Сначала запишем ту команду, которая выиграет турнир. Здесь есть шесть вариантов, по количеству участвующих команд. Запишем эти варианты:

Далее выберем один из вариантов и для него укажем серебряного призера соревнований. Здесь есть только 5 вариантов, ведь 1 из 6 команд уже записана на 1-ом месте:

Такую пятерку можно записать для каждого из шести вариантов того, кто станет чемпионом. Получается, что всего есть 6•5 = 30 пар «чемпион – серебряный призер». Наконец, для одной такой пары можно записать 4 варианта того, кто окажется третьим (две команды писать нельзя, так как они уже записаны на первых двух строчках):

Для каждой пары можно записать 4 тройки призеров. Так как число пар «чемпион – вице-чемпион» равно 6•5 = 30, то число троек составит 6•5•4 = 120.

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

Если общее число команд обозначить как n (в этом примере n = 6), а количествоупорядочиваемых команд равно k, то количество таких размещений в комбинаторике обозначается как

В примере с командами количество размещений равнялось 120:

Читается эта запись как «число размещений из 6 по 3 равно 120».

Для нахождения этого числа мы перемножили k (3)множителей. Первый из них был равен n(6), так как каждая из n команд могла занять первая место. Второй множитель был равен (n– 1), так как после определения чемпиона мы могли поставить на вторую позицию одну из (n– 1) команд. Третий множитель был равен (n– 2). По этой логике каждый следующий множитель будет меньше предыдущего на единицу. Например, чтобы вычислить число размещенийиз 7 по 4, надо перемножить 4 множителя, первый из которых равен 7, а каждый следующий меньше на 1:

Однако математически удобнее представлять это произведение как отношение двух факториалов. Для этого умножим количество размещений на дробь 3!/3!, равную единице. Естественно, число размещений из-за умножения на единицу не меняется:

Число 3 в данном случае можно получить, если из 7 вычесть 4. В общем случае из числа nнадо вычесть число k. Тогда формула для вычисления количества размещений примет вид:

 

Пример. В программе 8 «А» класса 12 различных предметов. В понедельник проводится 5 занятий подряд. Сколько существует вариантов расписаний для класса, если в течение понедельника нельзя проводить два одинаковых урока?

Решение. Для составления расписания нужно выбрать 5 предметов и расставить их по порядку. Поэтому нам необходимо найти размещение из 12 по 5:

Ответ: 95040

 

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

Решение. Из десяти мест надо выбрать шесть и указать для каждого, какому пассажиру оно соответствует. То есть каждый вариант рассадки пассажиров – это размещение из 10 по 6. Найдем их количество:

Ответ: 151200

Заметим, что перестановка – это частный случай размещения, когда k = n. Действительно, если нам надо указать тройку призеров турнира, в котором участвуют 6 команд, то мы указываем размещение из 6 по 3. Но если мы указываем для каждой из 6 команд, какое место она займет в чемпионате, то это размещение из 6 по 6. С другой стороны, это расстановка одновременно является и перестановкой 6 команд. Убедимся, что в этом частном случае формула для подсчета количества размещений покажет тот же результат, что и формула для перестановок

Для примера с 6 командами это будет выглядеть так:

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

 

Сочетания

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

Однако порою этот порядок не имеет значения. Так, существует известная лотерея, где предлагается угадать 7 чисел из 49, которые выпадут во время розыгрыша из барабана. При этом порядок их выпадения не играет никакой роли. Игрок, выбирая эти 7 чисел, с точки зрения математики формирует сочетание из 49 по 7.

Количество возможных сочетаний из n по k обозначается буквой С:

Для вычисления количеств сочетаний из n по k сначала найдем количество аналогичных размещений. Оно вычисляется по формуле:

Однако ясно, что, как и в случае с перестановками с повторениями, некоторые сочетания мы посчитали несколько раз. Вернемся к примеру с командами. Если мы выбрали команды Л (Локомотив) , З (Зенит) и К (Краснодар), то мы можем составить ровно 3! = 6 размещений из них:

ЛЗК

ЛКЗ

ЗЛК

ЗКЛ

КЛЗ

КЗЛ

Однако все они соответствуют только одному сочетании – ЛКЗ. Таким образом, считая количество размещений, мы посчитали каждоесочетание не один, а 3! раз. Поэтому для нахождения количества сочетаний в комбинаторике надо поделить число размещений на число перестановок k элементов:

Эта формула связывает важнейшие понятия комбинаторики – перестановки, сочетания и размещения. Подставим в неё формулы для размещений и перестановок и получим:

 

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

Решение. Посчитаем число сочетаний из 6 по 3:

Ответ: 20

 

Пример. Сколько комбинаций чисел может составить игрок, играющий в лотереи «5 из 36», «6 из 45», «7 из 49»?

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

Ответ: 376992; 8145060; 85900584

 

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

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

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

Это же условие гарантирует, что, выбрав любые 3 и 8 точек, мы сможем построить треугольник с вершинами в этих точках, а выбрав 4 точки, получим четырехугольник. Поэтому для подсчета количества треугольников и четырехугольников следует искать число сочетаний по 3 и 4:

Ответ: 28 прямых, 56 треугольников и 70 четырехугольников.

 

Пример. В одной урне находится 10 различных шаров с номерами от 0 до 9, а в другой – 8 различных шаров с первыми восемью буквами алфавита. По условиям лотереи ведущий вытаскивает из первой урны два шара с числами, а из второй – три шара с буквами. Для победы в лотерее надо угадать выпавшие шары. Сколько комбинаций шаров может выпасть в игре?

Решение. Посчитаем отдельно, сколькими способами можно выбрать 2 шара с цифрами из 10 и 3 шара с буквами из 8:

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

56•45 = 2520

Ответ: 2520

Заметим, что выбирая, например, сочетание из 49 по 7, мы одновременно выбираем и сочетание из 49 по 49 – 7 = 42. Действительно, игрок, обводящий в кружок в лотерейном билете свои 7 счастливых чисел, одновременно и определяетостальные 42 числа, какие числа он НЕ считает счастливыми. Для наглядности запишем число сочетаний в обоих случаях:

Получили одну и ту же дробь, в которой отличается лишь последовательность множителей в знаменателе. Можно показать, что и в общем случае число сочетаний из nпо k совпадает с количеством сочетаний из nпо (n– k):

 

100urokov.ru

1.3. Элементы комбинаторики

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

Пусть A₁, A₂, …, A_k – элементы конечного множества. Сформулируем два важных правила, часто применяемых при решении комбинаторных задач.

Правило суммы. Если элемент А₁ может быть выбран n₁ способами, элемент А₂ – n₂ способами, …, элемент А_k – n_k способами, то выбор одного из элементов (или А₁, или А₂, …, или A_k) может быть осуществлен n₁ + n₂ + … + n_k способами.

Пример 1.3. В группе 30 студентов. Известно, что 5 из них на экзамене по математике получили оценку «отлично», 10 – оценку «хорошо», остальные – «удовлетворительно». Сколько существует способов выбрать одного студента, получившего на экзамене оценку «отлично» или «хорошо»?

Решение. Студент, получивший оценку «отлично» может быть выбран n₁ = 5 способами, оценку «хорошо» – n₂ = 10 способами. По правилу суммы существует n₁ + n₂ = 5 + 10 = 15 способов выбора одного студента, получившего на экзамене оценку «отлично» или «хорошо». ◄

Правило произведения. Если элемент А₁ может быть выбран n₁ способами, после этого элемент А₂ может быть выбран n₂ способами, …, после каждого такого выбора элемент А_k может быть выбран n_k способами, то выбор всех элементов А₁, А₂, …, A_k в указанном порядке может быть осуществлен n₁·n₂·…·n_k способами.

Пример 1.4. В группе 30 студентов. Необходимо выбрать старосту, его заместителя и профорга. Сколько существует способов это сделать?

Решение. Старостой может быть выбран любой из 30 студентов, его заместителем – любой из оставшихся 29, а профоргом – любой из оставшихся 28 студентов, т.е. n₁ =30, n₂ =29, n₃ = 28. По правилу произведения общее число способов выбора старосты, его заместителя и профорга равно n₁·n₂·n₃ = 30·29·28 = = 24360 способов. ◄

Пусть дано множество из n различных элементов. Из этого множества могут быть образованы подмножества из m элементов (0 ≤ m ≤n). Например, из 5 элементов a, b, c, d, e могут быть отобраны комбинации по 2 элемента – ab, bc, cd, ba и т.д., по 3 элемента – abc, cbd, cba и т.д.

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

Число размещений из n элементов по m находится по формуле

,

(1.5)

где n! равно произведению n первых чисел натурального ряда, т.е. n! = 1·2·…·n.

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

Решение. В данном случае двузначное число является комбинацией из пяти цифр по две цифры. Поскольку числа отличаются как составом входящих в них цифр, так и порядком их расположения, то в данном случае двузначные числа являются размещениями из пяти цифр по две. Число таких размещений

. ◄

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

Число сочетаний из n элементов по m находится по формуле

.

(1.6)

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

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

. ◄

Если в размещениях из n элементов поmнекоторые из элементов (или все) могут оказаться одинаковыми, то такие размещения называютразмещениями с повторениями из nэлементов поm.Число размещений с повторениями равно

,

(1.7)

Пример 1.7.Сколько можно записать трехзначных чисел, которые не содержат цифр 0 и 5?

Решение.В данном случае трехзначное число является комбинацией из восьми цифр (0 и 5 не учитываются) по три цифры. При этом некоторые из цифр (или все) могут повторяться. Поэтому в данном случае трехзначные числа является размещениями с повторениями из восьми цифр по три. Число таких размещений с повторениями

= 512. ◄

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

Число сочетаний с повторениями равно

,

(1.8)

где определяется по формуле (1.6).

Пример 1.8.В почтовом отделении продаются открытки восьми видов. Сколькими способами можно купить в нем три открытки?

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

= 120. ◄

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

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

Решение. Каждый вариант жеребьевки отличается только порядком участников конкурса, т.е. является перестановкой из 5 элементов. Их число равно P₅ = 5! = 1·2·3·4·5 = 120. ◄

Если в перестановках из общего числа nэлементов естьkразличных элементов, при этом 1-й элемент повторяетсяn₁раз, 2-й элемент –n₂раз,k-й элемент –n_kраз, причемn₁+n₂+ … +n_k=n, то такие перестановки называютперестановками с повторениямиизnэлементов. Число перестановок с повторениями равно

.

(1.10)

Пример 1.10.Сколько можно составить шестизначных чисел, состоящих из цифр 3, 5, 7, в которых цифра 3 повторяется 3 раза, цифра 5 – 2 раза, цифра 7 – 1 раз?

Решение.Каждое шестизначное число отличается от другого порядком следования цифр (причемn₁=3,n₂= 2,n₃= 1, а их сумма равна 6), т.е. является перестановкой с повторениями из 6 элементов. Их число равно

= 60. ◄

studfile.net

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

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

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

Число перестановок из n

 

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

 

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

 

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

 

save Сохранить share Поделиться extension Виджет

Итак, есть множество из 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. Сочетания: АВ, АС, СВ

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

Обратите внимание, что внизу

planetcalc.ru

§2. Комбинаторика без повторений.

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

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

Определение 2: Множество с заданным на нем порядком называется упорядоченным множеством.

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

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

и .

Три буквы ,иможно расположить в виде последовательности шестью способами:

, ,,,,.

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

Упорядоченные последовательности элементов некоторого множества можно рассматривать как распределения или расстановки этих элементов в последовательности.

Определение 3: Пусть дано конечное множество изэлементов. Всякий набор изэлементов данного множества (при этом элементы в наборе могут и повторяться) будем называть—расстановками.

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

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

Определение 4: Пусть — конечное множество изэлементов.Перестановками из различных элементов множестваназываются все расположенияэлементов в определенном порядке. Обозначается:(от французского словаpermutation — перестановка).

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

Определение 5: Различные упорядоченные множества, которые отличаются лишь порядком элементов, называются перестановками этого множества.

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

Определение 6: Произведение последовательных натуральных чисел в математике обозначаюти называютфакториалом.

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

Теорема 1: Число перестановок из различных элементов вычисляется по формуле:

(1)

Доказательство. Рассмотрим произвольное множество из элементов. Построим всевозможные расстановки из этихэлементов. На первое место расстановки можно поставить любой из элементов (способов выбора первого элемента). После того, как первый элемент выбран и независимо как он выбран, второй элемент можно выбратьспособом. Для выбора третьего элемента остаетсяспособа и т.д. Последний элемент выбирается соответственно одним способом. Тогда, в силу комбинаторного принципа умножения, количество таких расстановок будет равно:

Теорема доказана.

Пример 1: Сколькими способами трое друзей могут занять в кинотеатре места с номерами 1, 2 и 3.

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

Перестановки букв некоторого слова называют анаграммами. Открытые еще в ІІІ веке до нашей эры греческим грамматиком Ликофроном анаграммы до сих пор привлекают внимание языковедов, поэтов и любителей словесности. Мастера словесных игр помимо эрудиции и большого запаса слов знают много секретов, связанных с комбинаторными навыками, один из которых – анаграммы. Часто требуется среди всех перестановок выбрать те, которые обладают определенным свойством. Например, среди анаграмм слова «крот», которых всего , только одна, не считая самого слова«крот», имеет смысл в русском языке – «корт».

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

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

Пример 2: Сколькими способами 7 детей могут стать в хоровод?

Решение. Число линейных перестановок 7 детей будет равно . Если хоровод уже сформирован, тогда для него существует 7 круговых перестановок, переходящих друг в друга при повороте. Эти перестановки не должны быть засчитаны, поэтому круговых перестановок из 7 элементов будет.

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

Определение 7: Пусть имеется различных предметов. Расстановки изэлементов поэлементов () называютсяразмещениями без повторений. Обозначают: . Здесь имеется в виду, что элементы в расстановках не повторяются.

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

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

Определение 8: Конечные упорядоченные множества называются размещениями.

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

. (2)

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

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

.

По определению, такие расстановки являются размещениями. Что и требовалось доказать.

Пример 3: Собрание из 25 человек выбирает президиум из 3 человек: 1) председатель, 2) заместитель, 3) секретарь. Сколько возможно вариантов выбора президиума?

Решение. Выбирая трех человек из 25, замечаем, что важен порядок выбора, поэтому количество президиумов будет равно:

.

Замечание: Число размещений без повторений можно также находить по формуле:

. (3)

Если в знаменателе дроби из формулы (3) , то принято считать.

Замечание: Формула (3) отличается компактностью, но при решении задач удобнее использовать формулу (2). Дробь, стоящая в правой части формулы (3), может быть сокращена до целого числа. Это число равно числу из правой части формулы (2).

Пример 4: Сколько можно составить двухбуквенных слов (буквы не повторяются) из 33 букв русского алфавита?

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

Тогда количество различных комбинаций из 2 букв, выбранных из 33 букв алфавита, будет равно:

.

В данном случае важен порядок букв. Если поменять 2 буквы в слове, то получим новое слово.

Замечание: Перестановка без повторений – это частный случай размещений без повторений при . Можно сказать, что перестановка изэлементов – это размещение изэлементов поэлементов:

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

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

Определение 9: Сочетания без повторений из элементов некоторого множества поэлементов () – это расстановки, отличающиеся друг от другасоставом, но не порядком элементов. Обозначают: (от французского словаcombinaison – сочетание).

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

С точки зрения теории множеств определение сочетаний можно сформулировать иначе.

Определение 10: Конечные неупорядоченные множества называются сочетаниями.

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

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

Теорема 4: Число сочетаний находится по следующей формуле:

. (4)

Доказательство. Если из произвольного -элементного множества выбраныэлементов, то их можно пронумеровать номерамичислом способов, равным. Оставшиесяэлементов можно занумеровать номерами,, …,всегоспособами. Кроме того, сам отборэлементов изэлементов можно осуществитьспособами. Таким образом, мы получили вариантов нумерации полного множества из элементов, которых всего. Поэтому имеем, откуда получаем:

.

Теорема доказана.

Замечание: Дробь, стоящая в правой части (4), может быть сокращена до целого числа.

Из формулы числа сочетаний следует:

, ,.

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

Пример 5: Сколькими способами можно выбрать 3 различные краски из имеющихся пяти.

Решение. Порядок выбора красок не важен. Важно только какие краски выбраны. Поэтому количество вариантов равно: .

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

Решение. Порядок выбора полос важен, поэтому количество таких флагов равно: .

studfile.net

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

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

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

Число сочетаний с повторениями из n элементов по m будем обозначать символом Формула для вычисления числа сочетаний с повторениями:

(1.6)

Замечание: m может быть и больше n.

Пример 1.4. Сколькими способами можно выбрать 6 пирожных в кондитерской, где есть 4 разных сорта пирожных?

Решение.

,

где m>n.

Ответ. Существует 84 различных способа выбора пирожных.

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

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

Число перестановок их n элементов обозначается символом Р_n, это то же самое, что число размещений из n элементов по n в каждом, поэтому

(1.7)

Пример 1.5. Менеджер ежедневно просматривает 6 изданий экономического содержания. Если порядок просмотра изданий случаен, то сколько существует способов его осуществления?

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

По условию задачи n = 6.

Следовательно:

.

Ответ. Издания можно просмотреть издания 720 способами.

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

Число перестановок с повторениями выражается при помощи формулы:

,

(1.8)

где числа повторений.

Пример 1.6. Каким числом способов можно разделить m + n + s предметов на три группы, чтобы в одной группе было m предметов, в другой — n предметов, в третьей — s предметов?

Решение.

Ответ:

1.8. Правила комбинаторики

Правило суммы (принцип логического сложения)	Если объект а может быть выбран m способами, а объект b может быть выбран другими n способами (не такими как а), то выбор элемента а или b из объединенной совокупности может быть осуществлен m+n способами.
Правило произведения (принцип логического умножения)	Если объект а может быть выбран m способами и после каждого такого выбора объект b может быть выбран n способами, то выбор пары объектов а и b в указанном порядке может быть осуществлен m∙n способами.

Задачи к теме 1

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

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

3. Руководством риэлтерской фирмы принято решение о необходимости рекламы нового вида услуг. По расчетам отдела рекламы, выделенных средств хватит для того, чтобы поместить объявления только в 7 из 12 городских газет. Сколько существует способов случайного отбора газет для размещения рекламы?

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

5. Расписание одного дня занятий на II курсе состоит из трех пар. В течение семестра студенты изучают 12 дисциплин. Сколько существует вариантов составления расписания занятий на один из дней недели, если в течение дня проводятся занятия по разным дисциплинам?

6. Покупая карточку лотереи “Спортлото”, игрок должен зачеркнуть 5 из 36 возможных чисел от 1 до 36. Если при розыгрыше тиража лотереи он угадает все 5 чисел, то имеет шанс выиграть значительную сумму денег. Сколько возможных комбинаций можно составить из 36 по 5, если порядок чисел безразличен?

7. а) Сколько различных «слов», каждое из которых содержит 6 букв, можно составить из слова «экспертиза»? б) Сколько различных «слов», каждое из которых содержит 10 букв, можно составить из слова «экспертиза»?

8. Распределение пар в первом круге Уимблдонского турнира проводится методом жеребьевки. Сколько комбинаций пар возможно составить, если в турнире участвуют 20 теннисисток?

9. Администрация города объявила тендер на строительство медицинского центра. В конкурсную комиссию поступило 8 запечатанных пакетов со сметами от различных строительных фирм. Сколько существует способов очередности вскрытия пакетов, если они вскрываются конкурсной комиссией в случайном порядке после окончания срока подачи заявок?

10. Для обнаружения нефти на участке необходимо пробурить до 11 скважин. Однако, компания имеет средства для бурения только 6 скважин. Сколько способов отбора шести различных скважин у компании?

11. В Российской Федерации номерной знак автомобиля каждого региона состоит из трех букв и трех цифр. Чему равно общее число возможных номерных знаков региона, если, для его составления используется 12 букв русского алфавита и 10 цифр. Рассмотрите два случая, когда: а) цифры и буквы в номере не повторяются; б) если повторяются?

12. В финале конкурса телевизионных программ по трем номинациям представлены 9 региональных телерадиокомпаний. Сколько существует вариантов распределения призов, если каждая телерадиокомпания может получить призы по нескольким номинациям и по каждой номинации установлены: а) одинаковые призы? б) различные призы?

13. PIN – код пластиковой карты состоит из 4 цифр. Сколько всевозможных комбинаций PIN – кода существует, если: а) цифры в коде не повторяются? б) повторяются?

14. Издательство планирует выпустить в текущем году 6 различных учебников по статистике. Каким количеством способов можно выбрать 30 экземляров, если в библиотеке университета должны быть представлены все виды изданных учебников по статистике?

15. Сколько различных «слов» можно составить из букв слова «колокол»?

16. Код банковского сейфа состоит из 8 цифр. Сколько можно составить различных кодовых комбинаций, если: а) цифры не повторяются? б) цифры повторяются?

17. В мореплавании принято давать сигналы, используя разноцветные флаги. Сколько сигналов можно составить, используя одновременно 8 флагов, из которых 1 красный, 2 синих, 3 зелёных и 2 белых?

18. Фирма планирует приобрести путевки для отдыха 25 сотрудников. Сколько существует вариантов приобретения путевок, если: а) контракт будет заключен с четырьмя пансионатами? б) с двумя пансионатами?

19. Компьютерный ключ к антивирусной программе состоит из 9 цифр. Сколько существует различных вариантов компьютерных ключей, если: а) цифры ключа не повторяются? б) цифры ключа повторяются?

20. В парфюмерном магазине имеется 5 различных косметических наборов. Фирме необходимо приобрести 18 подарков к празднику. Сколько в таком случае существует вариантов выбора подарков?

studfile.net