Комбинаторика

Комбинаторика — основные понятия и формулы с примерами

Комбинаторика

1001student.ru > Математика > Комбинаторика — основные понятия и формулы с примерами

Комбинаторика — раздел математики. Основные понятия и формулы комбинаторики как науки применяются во всех сферах жизни.

Неудивительно, что она включена в программу 11 класса, а также во вступительные испытания во многих ВУЗах РФ. Ее основы лежат в прикладном искусстве многих сфер деятельности человека.

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

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

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

  • Что такое комбинаторика в математике
  • Основные понятия
  • Правило произведения
  • Правило суммы
  • Сочетания с повторениями и без повторений
  • Размещения с повторениями и без повторений
  • Перестановки с повторениями и без повторений
  • Комбинаторные задачи с решениями
  • Заключение

Что такое комбинаторика в математике

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

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

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

Основные понятия

Их несколько:

  1. Элемент – любой объект или явление, входящий в искомое множество.
  2. Сочетание – подмножества, находящиеся в произвольном порядке в исходном множестве.
  3. Перестановка – элементы во множестве находятся в строго определенном порядке.
  4. Размещение – упорядоченные подмножества в исходном множестве.

Правило произведения

Является одним из основных правил при решении таких задач и звучит так:

При выборе элемента А из n способов и выборе элемента В из m способов верно утверждение, что выбрать пару А и В одновременно можно n*m способами.

Рассмотрим на конкретных примерах.

Задача №1.

В коробке лежит 2 мяча и 6 скакалок. Сколько существует способов достать 1 мяч и 1 скакалку?

Ответ прост: 2 * 6 = 12.

Задача №2.

Есть 1 кубик, 2 шарика, 3 цветка и 4 конфеты. Сколькими способами можно вытянуть кубик, шарик, цветок и конфету?

Решение аналогично: 1 * 2 * 3 * 4 = 24.

Причем левую часть можно записать гораздо проще: 4!

! в данном случае является не знаком препинания, а факториалом. С помощью него можно вычислить более сложные варианты и решать трудные задачи (существуют разные формулы, но об этом позже).

Задача №3.

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

Ответ: 2! = 2.

Задача №4.

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

10! = 3628800.

Правило суммы

Тоже является базовым правилом комбинаторики.

Если А можно выбрать n раз, а В — m раз, то А или В можно выбрать (n + m) раз.

Задача №5.

В коробке лежат 5 красных, 3 желтых, 7 зеленых, 9 черных карандашей. Сколько есть способов вытащить 1 любой карандаш?

Ответ: 5 + 3 + 7 + 9 = 24.

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

Под этим термином понимают комбинации в произвольном порядке из множества n по m элементов.

Число сочетаний равно количеству таких комбинаций.

Задача №6.

В коробке находится 4 разных фрукта. Сколькими способами можно достать одновременно 2 разных фрукта?

Решение простое:

Где 4! – комбинация из 4 элементов.

С повторениями чуть сложней, комбинации считаются по такой формуле:

Задача №7.

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

В этом случае:

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

Под этим определением понимают набор m элементов из множества n элементов.

Задача №8.

Из 3 цифр надо выбрать 2, чтобы получались разные двузначные числа. Сколько вариантов?

Ответ прост:

А как же быть с повторениями? Здесь каждый элемент может размещаться несколько раз! В таком случае общая формула будет выглядеть следующим образом:

Задача №9.

Из 12 букв латинского алфавита и 10 цифр натурального ряда надо найти все варианты составления автомобильного кода региона.

Решение:

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

Под этим термином понимают все возможные комбинации из n элементного множества.

Задача №10.

Сколько возможных пятизначных чисел можно составить из 5цифр? А шестизначных из 6 цифр? Семизначных из 7 цифр?

Решения, согласно вышеприведенной формуле, следующие:

5! = 120;

6! = 720;

7! = 5040.

А как же быть с повторениями? Если в таком множестве есть одинаковые по своей значимости элементы, то перестановок будет меньше!

Задача №11.

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

Ответ прост: 4! / (3! * 1!) = 4.

Комбинаторные задачи с решениями

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

Типы задачЧто требуется найтиМетоды решения
Магический квадратФигура, в которой сумма чисел в рядах и столбцах должна быть одинакова (его разновидность – латинский квадрат).Рекуррентные соотношения. Решается подобная же задача, но с гораздо меньшим множеством элементов по известным правилам и формулам.
Задача размещенияСтандартная производственная задача (например, в лоскутной технике) — найти возможные способы разложения количества продуктов в ячейки в определенном порядке.Включения и исключения. Как правило, применяется при доказательстве различных выражений.
Задачи про торговцевСуть — найти все возможные пути прохождения людей из пункта А в пункт В.Траектории. Для этого вида задач характерно геометрическое построение возможных способов решения.

Заключение

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

Источник: https://1001student.ru/matematika/kombinatorika.html

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

Комбинаторика

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

Размещение элементов комбинаторики

Пусть даны три элемента . Из них можно создать такие соединения:

1) по одному элементу: ;

2) по два элемента: ;

3) по три элемента: .

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

Число размещений обозначается . Из вышеописанного, мы видим, что , , .

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

.

(1)

Действительно, пусть нам дано элементов: .

Рассмотрим размещение по одному элементу. Понятно, что их будет , то есть .

Теперь рассмотрим, какие возможные размещения по 2 элемента. Чтобы их получить, мы допишем к каждому из данных элементов ещё по одному, которые брались из остальных  элементов. Так, к элементу  допишем последовательно остальные элементы: ; к элементу последовательно остальные элементы: и т. д.

Получим все размещения из элементов по 2:

Записано строк, а число всех размещений в каждом из этих строк . Общее количество всех размещений равняется произведению на , то есть:

.

Чтобы получить рзмещение по 3 элемента в каждом, нам нужно к каждой из записанных пар элементов приобщить ещё по одному элементу из элементов, что остались.

Например, к необходимо приобщить один из элементов . Тогда всех размещений по 3 элемента будет:

и т. д.

Иногда встречаются задачи на размещение с повторениями.

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

.

(2)

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

Согласно с определением:

.

Произведение всех натуральных чисел от до обозначается , а читается ( факториал).

Таким образом,

.

Тогда формула для вычисления количества перестановок запишется:

(3)

При этом имеется ввиду, что .

Обратите внимание! Иногда встречается обозначение . Принято считать, что .

Комбинации или сочетание элементов комбинаторики

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

(4)

Формулу (4) объясним на таком примере:

Пусть даны 4 элемента , комбинациями из этих элементов по будут:

.

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

Число таких размещений равняется .

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

,

откуда получается формула (4).

Посмотрите пример:

.

Умножим числитель и знаменатель в формуле (4) на . Тогда получим:

В итоге получаем:

(5)

По определению принимают . Это определение можно получить из формулы (5), если принять во внимание, что .

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

(6)

Действительно, если по формуле (5) записать , тогда получим:

(7)

Последнее выражение совпадает с правой частью в формуле (5).

Отметим ещё, что числа – это коэффициенты в биноме Ньютона:

(8)

причём согласно с равенством (6) коэффициенты, равноотдалённые от окончания в формуле (8), равные между собой, то есть:

, , и т. д.

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

 Иногда бывают перестановки с повторениями: , которые можно образовать из элементов, среди которых одинаковых элементов 1-го типа, одинаковых элементов 2-го типа, и т. д. одинаковых элементов к-го типа, причём находятся по формуле:

(9)

Теперь рассмотрим комбинации с повторениями.

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

(10)

где может быть .

Примеры решения задач с элементами комбинаторики

Пример 1

Задача

Студенты группы изучают 9 дисциплин по 3 пары ежедневно. Сколько существует способов, чтобы распределить пары на один день?

Решение

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

.

Ответ

Существует 504 размещений.

Пример 2

Задача

Автомобильный номер состоит из 5 цифр (из такого набора: и двух букв. В соединении из букв для номеров автомобилей, какие зарегистрированы в Московской области, на первом месте стоит буква , а на втором месте одна из букв А, Б. В, И. К, Н. Сколько автомобильных номеров можно составить в области?

Решение

Числовая часть номера – один из размещений из по с повторениями. И количество:

Из них необходимо исключить размещение 000-00, так как такой номер не используется, то есть, всех числовых соединений будет:

.

Количество соединения букв 7. Первая буква фиксированная, тогда остаётся шесть. Общее число всех автомобильных номеров при изложенной системе равняется:

.

Ответ

Автомобильных номеров в одной области можно составить по числам – 99 999, а по буквам – 599994.

Пример 3

Задача

Сколько пятизначных телефонных номеров можно составить используя цифры 3, 4, 5, 6, 7 (без повторений)?

Решение

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

.

Ответ

Всего можно составить 120 пятизначных номеров.

Пример 4

Задача

Сколько есть способов, чтобы заполнить карточку спортлото, в которой из 49 чисел необходимо выбрать 6?

Решение

Две заполненные карточки считаются разными, если среди выбранных 6 чисел они отличаются хотя бы одним числом, то есть это будут комбинации, и их количество равняется:

.

Ответ

Количество комбинаций =

Пример 5

Задача

Сколько есть способов, чтобы в данном тайме тренер смог бы выставить на поле 5 баскетболистов, если в команде 10 игроков, причём одного из ведущих игроков тренер планирует задействовать в игре не заменяя на другого игрока весь тайм?

Решение

Так как один из ведущих игроков должен находится на поле в игре весь тайм, тогда менять придётся только 4 игрока из оставшихся 9, то есть у нас получается:

Ответ

Есть 126 способов.

Пример 6

Задача

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

Решение

Всего 8 фигур, причём , , , , , тогда:

.

Ответ

На первой горизонтальной шахматной доске с перестановками фигур можно расставить 5 040 раз.

Пример 7

Задача

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

1. В слове “мама”;

2. в слове параллелограмм.

Записать соединения букв.

Решение

1. В слове “мама” буквы, при этом две буквы “м”, и две буквы “а”. По формуле (9) всех перестановок будет:

.

А сами перестановки будут такими: “мама”, “маам”, амам”, “аамм”, “амма”.

2. В слове “параллелограмм” 12 букв, из них букв “а” – 3, “г” – 1, “е” – 1, “л” – 2, “м” – 1, “о” – 1, “п” – 1, “р” – 2. Всех перестановок будет:

.

Ответ

Всевозможных перестановок будет – .

Пример 8

Задача

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

Решение

.

Ответ

Для того, чтобы выбрать 5 деталей 3 цветов, мы нашли 21 способ.

Источник: https://NauchnieStati.ru/spravka/elementy-kombinatorik/

Комбинаторика

Комбинаторика

План:

Предмет комбинаторики. 2

Краткая историческая справка. 4

Основные комбинаторные задачи. 5

Основные формулы комбинаторики_ 7

Правило суммы. 7

Правило произведения. 9

Предмет комбинаторики

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

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

Например, если в сосуде содержится вода при нормальном атмосферном давлении и температуре 20°, то событие «вода в сосуде находится в жидком состоянии» есть достоверное.

В этом примере заданные атмосферное давление и температура воды составляют совокупность условий S.

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

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

Каждое случайное событие, в частности выпадение «герба», есть следствие действия очень многих случайных причин (в нашем примере: сила, с которой брошена монета, форма монеты и многие другие). Невозможно учесть влияние на результат всех этих причин, поскольку число их очень велико и законы их действия неизвестны.

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

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

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

Установлением этих закономерностей и занимается теория вероятностей.

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

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

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

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

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

Краткая историческая справка

Первые работы, в которых зарождались основные понятия теории вероятностей, представляли собой попытки создания теории азартных игр (Кардано, Гюйгенс, Паскаль, Ферма и другие в XVI—XVII вв.).

Следующий этап развития теории вероятностей связан с именем Якоба Бернулли (1654—1705). Доказанная им теорема, получившая впоследствии название «Закона больших чисел», была первым теоретическим обоснованием накопленных ранее фактов.

Дальнейшими успехами теория вероятностей обязана Муавру, Лапласу, Гауссу, Пуассону и др.

Новый, наиболее плодотворный период связан с именами П. Л. Чебышева (1821—1894) и его учеников А.А.Маркова(1856—1922) и А. М.Ляпунова (1857—1918). В этот период теория вероятностей становится стройной математической наукой.

Ее последующее развитие обязано в первую очередь русским и советским математикам (С. Н. Бернштейн, В. И. Романовский, А. Н. Колмогоров, А. Я. Хинчин, Б. В. Гнеденко, Н. В. Смирнов и др.).

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

Основные комбинаторные задачи

Основными и типичными операциями и связанными с ними задачами комбинаторики являются следующие:

1) образование упорядоченных множеств, состоящее в установлении определенного порядка следования элементов множества друг за другом, – составление перестановок;

2) образование подмножеств, состоящее в выделении из данного множества некоторой части его элементов, – составление сочетаний;

3) образование упорядоченных подмножеств – составление размещений.

ТИПЫ КОМБИНАТОРНЫХ ЗАДАЧ.

1. Магический квадрат – квадратная таблица (n * n) целых чисел от 1 до n¤ такая, что суммы чисел вдоль любого столбца, любой строки и двух диагоналей таблицы равны одному и тому же числу s=n(n¤+1)/2. Число n называют порядом магического квадрата.

Доказано, что магический квадрат можно построить для любого n Є 3. Уже в средние века был известен алгоритм построения магических квадратов нечетного порядка.

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

Однако общей теории магических квадратов не существует. Неизвестно даже общее число магических квадратов порядка n.

2. Латинский квадрат– квадратная матрица порядка n, каждая строка и каждый столбец которой являются перестановками элементов конечного множества S, состоящего из n элементов.

3. Задача размещения – одна из классических комбинаторных задач, в которой требуется определить число способов размещения m различных предметов в n различных ячейках с заданным числом r пустых ячеек. Это число равно

r n-r m

C (r)=C дельта O , r=0,1,2,…,n,

nm n

где

k m k j j m

дельта O =сигма (-1) C (k-j)

j=0 k

4. Задача коммивояжера, задача о бродячем торговце – комбинаторная задача теории графов.

В простейшем случае формулируется следующим образом: даны n городов и известно расстояние между каждыми двумя городами; коммивояжер, выходящий из какого-нибудь города, должен посетить n-1 других городов и вернуться в исходный. В каком порядке должен он посещать города (по одному разу каждый) чтобы общее пройденное расстояние было минимальным?

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

МЕТОДЫ РЕШЕНИЯ КОМБИНАТОРНЫХ ЗАДАЧ

1. Метод рекуррентных соотношений.

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

2. Метод включения и исключения.

Пусть N(A) – число элементов множества A. Тогда методом математической индукции можно доказать, что

N(A1 U A2 U … An) = N(A1) + … + N(An) –

– {N(A1 П A2) + … + N(An-1 П An)} +

+ {N(A1 П A2 П A3) + … + N(An-2 П An-1 П An)} – …

… +(-1)n-1*N(A1 П A2 П … П An-1 П An).

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

3. Метод траекторий.

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

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

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

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

Pn = n!,

где n! = 1 * 2 * 3 … n.

Заметим, что удобно рассматривать 0!, полагая, по определению, 0! = 1.

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

Amn = n (n – 1)(n – 2) … (n – m + 1).

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

С mn = n! / (m! (n – m)!).

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

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

Amn = PmC mn.

З а м е ч а н и е. Выше предполагалось, что все n элементов различны. Если же некоторые элементы повторяются, то в этом случае комбинации с повторениями вычисляют по другим формулам. Например, если среди n элементов есть n1 элементов одного вида, n2 элементов другого вида и т.д., то число перестановок с повторениями

Pn (n1, n2, …) = n! / (n1! n2! … ),

Источник: http://MirZnanii.com/a/312548/kombinatorika

Основное правило комбинаторики

Пусть необходимо несколько раз произвести выбор. Существует m1 вариантов при первом выборе, m2 – при втором, m3 – при третьем и т.д.

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

m1 ∙ m2 ∙ m3 ∙ …

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

Рассуждения будем приводить на основе следующего примера:

Пусть урна содержит m различных шаров с номерами от 1 до m. Из неё извлекаются n шаров при соблюдении некоторых условий на способ извлечения. Для каждой модели вычисляются количества всех возможных исходов.

1.1 Число размещений с возвращением

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

Таким образом, мы имеем дело с упорядоченными наборами (a1,…,an), в которых каждое aj может принимать любое значение от 1 до m.

Основное правило сразу приводит к ответу mn для полного числа исходов.

Шары извлекаются наудачу один за другим, однако в данной модели они не возвращаются обратно в урну. Мы снова имеем дело с упорядоченными наборами (a1,…

,an), но уже с ограничением, что в них все aj различны. Конечно, должно выполняться неравенство n меньше или равно m. Основное правило напрямую не применимо.

Тем не менее, принимая во внимание, что на каждом шаге число шаров в урне становится на один меньше, можем записать:

m ∙ (m-1) ∙ (m-2) ∙ … ∙ (m – (n-1)) = (m)n

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

Рассмотрим модель 1.2 при m = n.

Тогда все m шаров извлекаются один за другим без возвращений. Результатом выбора является набор из m занумерованных шаров, расставленных в некотором порядке. Полное количество возможностей совпадает с числом всех расположений элементов множества {1,2,..,m}. Это число называется факториалом от m и обозначается

m! = (m)m = m ∙ (m-1) ∙ … ∙ 2 ∙ 1

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

2.1 Число сочетаний без возвращения

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

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

Следовательно, мы имеем дело с выбором произвольного подмножества размера n из множества размера m.

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

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

Обозначим за x искомое число исходов (подмножеств размера n). Проведенные выше рассуждения показывают, что

n! ∙ x = (m)n

Отсюда получаем искомый ответ:

Если умножить числитель и знаменатель на (m-n)!, получим:

(*)

Выражение (*) называется биномиальным коэффициентом и играет важную роль в теории вероятностей.

Заметьте, что верно тождество

2.1.a. Перестановка из m шаров, неразличимых внутри групп

Допустим,что у нас есть m1 шаров цвета номер 1, m2 шаров цвета номер 2, … mr шаров цвета номер r. Цвета различаются, а шары одного цвета – нет.

Конечно, m1 + m2 +… + mr = m. Сколько существует отличающихся перестановок таких шаров?

Используя рассуждения из 1.2.a. для каждой первоначальной перестановки без различения шаров одного цвета в силу основного правила существует

m1! ∙ m2! ∙ … ∙ mr!

новых способов размещения с учетом нумерации.

Рассуждения аналогичные проведенным для модели 2.1 показывают, что искомое число ненумерованных перестановок равно частному:

Число называется мультиномиальным (или полиномиальным) коэффициентов. Когда r=2, коэффициент сводится к биномиальному.

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

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

К.Л. Чжун, Ф. АитСахлиа. Элементарный курс теории вероятностей. Стохастические процессы и финансовая математика. Перевод с английского М.Б. Лагутина, М.: БИНОМ. Лаборатория знаний, 2007

В начало

портала

Источник: http://statistica.ru/branches-maths/kombinatorika1/

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

Комбинаторика

Чтобы в материале было легче ориентироваться, добавлю содержание данной темы:

Введение. Множества и выборки

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

Для работы нам понадобятся кое-какие вспомогательные сведения. Начнём с такого фундаментального математического понятия как множество. Подробно понятие множества было раскрыто в теме “Понятие множества. Способы задания множеств”.

Очень краткий рассказ про множества: показать\скрыть

Если вкратце: множеством именуют некую совокупность объектов. Записывают множества в фигурных скобках. Порядок записи элементов роли не играет; повторения элементов не допускаются. Например, множество цифр числа 11115555999 будет таким: $\{1,5,9 \}$.

Множество согласных букв в слове “тигрёнок” таково: $\{т, г, р, н, к\}$. Запись $5\in A$ означает, что элемент 5 принадлежит множеству $A=\{1,5,9 \}$. Количество элементов в конечном множестве называют мощностью этого множества и обозначают $|A|$.

Например, для множества $A=\{1,5,9 \}$, содержащего 3 элемента, имеем: $|A|=3$.

Рассмотрим некое непустое конечное множество $U$, мощность которого равна $n$, $|U|=n$ (т.е. в множестве $U$ имеется $n$ элементов). Введём такое понятие, как выборка (некоторые авторы именуют её кортежем).

Под выборкой объема $k$ из $n$ элементов (сокращённо $(n,k)$-выборкой) будем понимать набор элементов $(a_1, a_2,\ldots, a_k)$, где $a_i\in U$. Выборка называется упорядоченной, если в ней задан порядок следования элементов. Две упорядоченные выборки, различающиеся лишь порядком элементов, являются различными.

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

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

Для примера рассмотрим множество $U=\{a,b,c,d,e\}$. Множество $U$ содержит 5 элементов, т.е. $|U|=5$. Выборка без повторений может быть такой: $(a,b,c)$. Данная выборка содержит 3 элемента, т.е. объём этой выборки равен 3. Иными словами, это $(5,3)$-выборка.

Выборка с повторениями может быть такой: $(a,a,a,a,a,c,c,d)$. Она содержит 8 элементов, т.е. объём её равен 8. Иными словами, это $(5,8)$-выборка.

Рассмотрим ещё две $(5,3)$-выборки: $(a,b,b)$ и $(b,a,b)$. Если мы полагаем наши выборки неупорядоченными, то выборка $(a,b,b)$ равна выборке $(b,a,b)$, т.е. $(a,b,b)=(b,a,b)$. Если мы полагаем наши выборки упорядоченными, то $(a,b,b)eq(b,a,b)$.

Рассмотрим ещё один пример, немного менее абстрактный 🙂 Предположим, в корзине лежат шесть конфет, причём все они различны. Если первой конфете поставить в соответствие цифру 1, второй конфете – цифру 2 и так далее, то с конфетами в корзине можно сопоставить такое множество: $U=\{1,2,3,4,5,6\}$.

Представьте, что мы наугад запускаем руку в корзинку с целью вытащить три конфеты. Вытащенные конфеты – это и есть выборка. Так как мы вытаскиваем 3 конфеты из 6, то получаем (6,3)-выборку. Порядок расположения конфет в ладони совершенно несущественен, поэтому эта выборка является неупорядоченной. Ну, и так как все конфеты различны, то выборка без повторений.

Итак, в данной ситуации говорим о неупорядоченной (6,3)-выборке без повторений.

Теперь подойдём с иной стороны. Представим себе, что мы находимся на фабрике по производству конфет, и на этой фабрике производятся конфеты четырёх сортов. Множество $U$ в этой ситуации таково: $U=\{1,2,3,4 \}$ (каждая цифра отвечает за свой сорт конфет).

Теперь вообразим, что все конфеты ссыпаются в единый жёлоб, около которого мы и стоим. И, подставив ладони, из этого потока отбираем 20 конфет. Конфеты в горсти – это и есть выборка.

Играет ли роль порядок расположения конфет в горсти? Естественно, нет, поэтому выборка неупорядоченная. Всего 4 сорта конфет, а мы отбираем двадцать штук из общего потока – повторения сортов неизбежны.

При этом выборки могут быть самыми различными: у нас даже могут оказаться все конфеты одного сорта. Следовательно, в этой ситуации мы имеем дело с неупорядоченной (4,20)-выборкой с повторениями.

Рассмотрим ещё пару примеров. Пусть на кубиках написаны различные 7 букв: к, о, н, ф, е, т, а. Эти буквы образуют множество $U=\{к,о,н,ф,е,т,а\}$. Допустим, из данных кубиков мы хотим составить “слова” из 5 букв. Буквы этих слов (к примеру, «конфе», «тенко» и так далее) образуют (7,5)-выборки: $(к,о,н,ф,е)$, $(т,е,н,к,о)$ и т.д.

Очевидно, что порядок следования букв в такой выборке важен. Например, слова «нокфт» и «кфтон» различны (хотя состоят из одних и тех же букв), ибо в них не совпадает порядок букв. Повторений букв в таких «словах» нет, ибо в наличии только семь кубиков.

Итак, набор букв каждого слова представляет собой упорядоченную (7,5)-выборку без повторений.

Еще один пример: мы составляем всевозможные восьмизначные числа из четырёх цифр 1, 5, 7, 8. Например, 11111111, 15518877, 88881111 и так далее. Множество $U$ таково: $U=\{1,5,7,8\}$.

Цифры каждого составленного числа образуют (4,8)-выборку. Порядок следования цифр в числе важен, т.е. выборка упорядоченная.

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

Размещения без повторений из $n$ элементов по $k$

Размещение без повторений из $n$ элементов по $k$ – упорядоченная $(n,k)$-выборка без повторений.

Так как элементы в рассматриваемой выборке повторяться не могут, то мы не можем отобрать в выборку больше элементов, чем есть в исходном множестве. Следовательно, для таких выборок верно неравенство: $n≥ k$. Количество размещений без повторений из $n$ элементов по $k$ определяется следующей формулой:

\begin{equation}A_{n}{k}=\frac{n!}{(n-k)!} \end{equation}

Что обозначает знак “!”? : показать\скрыть

Запись “n!” (читается “эн факториал”) обозначает произведение всех чисел от 1 до n, т.е.

$$ n!=1\cdot2\cdot 3\cdot \ldots\cdot n $$

По определению полагается, что $0!=1!=1$. Для примера найдём 5!:

$$ 5!=1\cdot 2\cdot 3\cdot 4\cdot 5=120. $$

Пример №1

Алфавит состоит из множества символов $E=\{+,*,0,1,f\}$. Определим количество таких трёхсимвольных слов в этом алфавите, которые не содержат повторяющихся букв.

Решение

Под трёхсимвольными словами будем понимать выражения вида “+*0” или “0f1”. В множестве $E$ пять элементов, поэтому буквы трехсимвольных слов образуют (5,3)-выборки. Первый вопрос: эти выборки упорядочены или нет? Слова, которые отличаются лишь порядком букв, полагаются различными, поэтому порядок элементов в выборке важен. Значит, выборка является упорядоченной.

Второй вопрос: допускаются повторения или нет? Ответ на этот вопрос даёт условие: слова не должны содержать повторяющихся букв. Подводим итоги: буквы каждого слова, удовлетворяющего условию задачи, образуют упорядоченную (5,3)-выборку без повторений. Иными словами, буквы каждого слова образуют размещение без повторений из 5 элементов по 3.

Вот примеры таких размещений:

$$ (+,*,f), \; (*,+,f), \; (1,+,0) $$

Нас же интересует общее количество этих размещений. Согласно формуле (1) количество размещений без повторений из 5 элементов по 3 будет таким:

$$ A_{5}{3}=\frac{5!}{(5-3)!}=\frac{5!}{2!}=60. $$

Т.е. можно составить 60 трёхсимвольных слов, буквы которых не будут повторяться.

Ответ: 60.

Размещения с повторениями из $n$ элементов по $k$

Размещение с повторениями из $n$ элементов по $k$ – упорядоченная $(n,k)$-выборка с повторениями.

Количество размещений с повторениями из $n$ элементов по $k$ определяется следующей формулой:

\begin{equation}\bar{A}_{n}{k}=nk \end{equation}

Пример №2

Сколько пятизначных чисел можно составить из множества цифр $\{5,7,2\}$?

Решение

Из данного набора цифр можно составить пятизначные числа 55555, 75222 и так далее. Цифры каждого такого числа образуют (3,5)-выборку: $(5,5,5,5,5)$, $(7,5,2,2,2)$.

Зададимся вопросом: что это за выборки? Во-первых, цифры в числах могут повторяться, поэтому мы имеем дело с выборками с повторениями. Во-вторых, порядок расположения цифр в числе важен. Например, 27755 и 77255 – разные числа.

Следовательно, мы имеем дело с упорядоченными (3,5)-выборками с повторениями. Общее количество таких выборок (т.е. общее количество искомых пятизначных чисел) найдём с помощью формулы (2):
$$ \bar{A}_{3}{5}=35=243. $$

Следовательно, из заданных цифр можно составить 243 пятизначных числа.

Ответ: 243.

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

Перестановка без повторений из $n$ элементов – упорядоченная $(n,n)$-выборка без повторений.

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

\begin{equation}P_{n}=n! \end{equation}

Эту формулу, кстати, легко получить, если учесть, что $P_n=A_{n}{n}$. Тогда получим:

$$ P_n=A_{n}{n}=\frac{n!}{(n-n)!}=\frac{n!}{0!}=\frac{n!}{1}=n! $$

Пример №3

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

Решение

Пусть первому мороженому соответствует цифра 1, второму – цифра 2 и так далее. Мы получим множество $U=\{1,2,3,4,5\}$, которое будет представлять содержимое морозилки.

Порядок съедения может быть таким: $(2,1,3,5,4)$ или таким: $(5,4,3,1,2)$. Каждый подобный набор есть (5,5)-выборка. Она будет упорядоченной и без повторений.

Иными словами, каждая такая выборка есть перестановка из 5 элементов исходного множества. Согласно формуле (3) общее количество этих перестановок таково:

$$ P_5=5!=120. $$

Следовательно, существует 120 порядков выбора очередности съедения.

Ответ: 120.

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

Перестановка с повторениями – упорядоченная $(n,k)$-выборка с повторениями, в которой элемент $a_1$ повторяется $k_1$ раз, $a_2$ повторяется $k_2$ раза так далее, до последнего элемента $a_r$, который повторяется $k_r$ раз. При этом $k_1+k_2+\ldots+k_r=k$.

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

\begin{equation}P_{k}(k_1,k_2,\ldots,k_r)=\frac{k!}{k_1!\cdot k_2!\cdot \ldots \cdot k_r!} \end{equation}

Пример №4

Слова составляются на основе алфавита $U=\{a,b,d\}$. Сколько различных слов из семи символов может быть составлено, если в этих словах буква “a” должна повторяться 2 раза; буква “b” – 1 раз, а буква “d” – 4 раза?

Решение

Вот примеры искомых слов: “aabdddd”, “daddabd” и так далее. Буквы каждого слова образуют (3,7)-выборку с повторениями: $(a,a,b,d,d,d,d)$, $(d,a,d,d,a,b,d)$ и т.д.

Каждая такая выборка состоит из двух элементов “a”, одного элемента “b” и четырёх элементов “d”. Иными словами, $k_1=2$, $k_2=1$, $k_3=4$. Общее количество повторений всех символов, естественно, равно объёму выборки, т.е.

$k=k_1+k_2+k_3=7$. Подставляя эти данные в формулу (4), будем иметь:

$$ P_7(2,1,4)=\frac{7!}{2!\cdot 1!\cdot 4!}=105. $$

Следовательно, общее количество искомых слов равно 105.

Ответ: 105.

Сочетания без повторений из $n$ элементов по $k$

Сочетание без повторений из $n$ элементов по $k$ – неупорядоченная $(n,k)$-выборка без повторений.

Общее количество сочетаний без повторений из $n$ элементов по $k$ определяется формулой:

\begin{equation}C_{n}{k}=\frac{n!}{(n-k)!\cdot k!} \end{equation}

Пример №5

В корзине размещены карточки, на которых написаны целые числа от 1 до 10. Из корзины вынимают 4 карточки и суммируют числа, написанные на них. Сколько различных наборов карточек можно вытащить из корзины?

Решение

Итак, в данной задаче исходное множество таково: $U=\{1,2,3,4,5,6,7,8,9,10\}$. Из этого множества мы выбираем четыре элемента (т.е., четыре карточки из корзины). Номера вытащенных элементов образуют (10,4)-выборку. Повторения в этой выборке не допускаются, так как номера всех карточек различны.

Вопрос вот в чём: порядок выбора карточек играет роль или нет? Т.е., к примеру, равны ли выборки $(1,2,7,10)$ и $(10,2,1,7)$ или не равны? Тут нужно обратиться к условию задачи. Карточки вынимаются для того, чтобы потом найти сумму элементов. А это значит, что порядок карточек не важен, так как от перемены мест слагаемых сумма не изменится.

Например, выборке $(1,2,7,10)$ и выборке $(10,2,1,7)$ будет соответствовать одно и то же число $1+2+7+10=10+2+1+7=20$. Вывод: из условия задачи следует, что мы имеем дело с неупорядоченными выборками. Т.е. нам нужно найти общее количество неупорядоченных (10,4)-выборок без повторений.

Иными словами, нам нужно найти количество сочетаний из 10 элементов по 4. Используем для этого формулу (5):

$$ C_{10}{4}=\frac{10!}{(10-4)!\cdot 4!}=\frac{10!}{6!\cdot 4!}=210. $$

Следовательно, общее количество искомых наборов равно 210.

Ответ: 210.

Сочетания с повторениями из $n$ элементов по $k$

Сочетание с повторениями из $n$ элементов по $k$ – неупорядоченная $(n,k)$-выборка с повторениями.

Общее количество сочетаний с повторениями из $n$ элементов по $k$ определяется формулой:

\begin{equation}\bar{C}_{n}{k}=\frac{(n+k-1)!}{(n-1)!\cdot k!} \end{equation}

Пример №6

Представьте себе, что мы находимся на конфетном заводе, – прямо возле конвейера, по которому движутся конфеты четырёх сортов. Мы запускаем руки в этот поток и вытаскиваем двадцать штук. Сколько всего различных “конфетных комбинаций” может оказаться в горсти?

Решение

Если принять, что первому сорту соответствует число 1, второму сорту – число 2 и так далее, то исходное множество в нашей задаче таково: $U=\{1,2,3,4\}$. Из этого множества мы выбираем 20 элементов (т.е., те самые 20 конфет с конвейера). Пригоршня конфет образует (4,20)-выборку. Естественно, повторения сортов будут.

Вопрос в том, играет роль порядок расположения элементов в выборке или нет? Из условия задачи следует, что порядок расположения элементов роли не играет. Нам нет разницы, будут ли в горсти располагаться сначала 15 леденцов, а потом 4 шоколадных конфеты, или сначала 4 шоколадных конфеты, а уж потом 15 леденцов. Итак, мы имеем дело с неупорядоченной (4,20) выборкой с повторениями.

Чтобы найти общее количество этих выборок используем формулу (6):

$$ \bar{C}_{4}{20}=\frac{(4+20-1)!}{(4-1)!\cdot 20!}=\frac{23!}{3!\cdot 20!}=1771. $$

Следовательно, общее количество искомых комбинаций равно 1771.

Ответ: 1771.

Онлайн-занятия по высшей математике

Источник: https://math1.ru/education/raznoe/combinatorics.html

Поделиться:
Нет комментариев

    Добавить комментарий

    Ваш e-mail не будет опубликован. Все поля обязательны для заполнения.

    ×
    Рекомендуем посмотреть