Основные правила и формулы комбинаторики. Методические указания по изучению темы. Сочетания с повторениями

План:

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

2. Общие правила комбинаторики.

4. Применение графов (схем) при решении комбинаторных задач.

1. Комбинаторика и ее возникновение.

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

Комбинаторика возникла в XVI веке. В жизни привилегированных слоев тогдашнего общества большое место занимали азартные игры (карты, кости). Широко были распространены лотереи. Первоначально комбинаторные задачи касались в основном азартных игр: сколькими способами можно получить данное число очков, бросая 2 или 3 кости или сколькими способами можно получить 2-ух королей в некоторой карточной игре. Эти и другие проблемы азартных игр являлись движущей силой в развитии комбинаторики и далее в развитии теории вероятностей.

Одним из первых занялся подсчетом числа различных комбинаций при игре в кости итальянский математик Тарталья. Он составил таблицы (числа способов выпадения k очков на r костях). Однако, он не учел, одна и та же сумма очков может выпасть различными способами, поэтому его таблицы содержали большое количество ошибок.

Теоретическое исследование вопросов комбинаторики предприняли в XVII веке французские математики Блез Паскаль и Ферма. Исходным пунктом их исследований были так же проблемы азартных игр.

Дальнейшее развитие комбинаторики связано с именами Я. Бернулли, Г. Лейбница, Л. Эйлера. Однако, и в их работах основную роль играли приложения к различным играм.

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

2. Общие правила комбинаторики.

Правило суммы: Если некоторый объект А может быть выбран m способами, а объект В- k способами, то объект «либо А, либо В» можно выбрать m +k способами.

Примеры:

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

Ответ: n способами.

Распределим эти n шариков по двум ящикам: в первый- m шариков, во второй- k шариков. Произвольным образом из произвольно выбранного ящика вынимается 1 шарик. Сколькими способами это можно сделать?

Решение: Из первого ящика шарик можно вынуть m способами, из второго- k способами. Тогда всего способов m+k=n .

2. Морской семафор.

В морском семафоре каждой букве алфавита соответствует определенное положение относительно тела сигнальщика двух флажков. Сколько таких сигналов может быть?

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

Правило произведения: Если объект А можно выбрать m способами, а после каждого такого выбора другой объект В можно выбрать (независимо от выбора объекта А) k способами, то пары объектов «А и В» можно выбрать m *k способами.

Примеры:

1. Сколько двузначных чисел существует?

Решение: Число десятков может быть обозначено любой цифрой от 1 до 9. Число единиц может быть обозначено любой цифрой от 0 до 9. Если число десятков равно 1, то число единиц может быть любым (от 0 до 9). Таким образом, существует 10 двузначных чисел, с числом десятков- 1.Аналогично рассуждаем и для любого другого числа десятков. Тогда можно посчитать, что существует 9 *10 = 90 двузначных чисел.

2. Имеется 2 ящика. В одном лежит m разноцветных кубиков, а в другом- k разноцветных шариков. Сколькими способами можно выбрать пару «Кубик-шарик»?

Решение: Выбор шарика не зависит от выбора кубика, и наоборот. Поэтому, число способов, которыми можно выбрать данную пару равно m *k .

3. Генеральная совокупность без повторений и выборки без повторений.

Генеральная совокупность без повторений - это набор некоторого конечного числа различных элементов a 1 , a 2 , a 3 , ..., a n .

Пример: Набор из n разноцветных лоскутков.

Выборкой объема k (k n ) называется группа из m элементов данной генеральной совокупности.

Пример: Пестрая лента, сшитая из m разноцветных лоскутков, выбранных из данных n .

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

- число размещений из n по k .

Число размещений из n по k можно определить следующим способом: первый объект выборки можно выбрать n способами, далее второй объект можно выбрать n -1 способом и т.д.

Преобразовав данную формулу, имеем:

Следует помнить, что 0!=1.

Примеры:

1. В первой группе класса А первенства по футболу участвует 17 команд. Разыгрываются медали: золото, серебро и бронза. Сколькими способами они могут быть разыграны?

Решение: Комбинации команд-победителей отличаются друг от друга составом и порядком следования элементов, т.е. являются размещениями из 17 по 3.

2. Научное общество состоит из 25-ти человек. Необходимо выбрать президента общества, вице-президента, ученого секретаря и казначея. Сколькими способами это можно сделать?

Решение: Комбинации руководящего состава общества отличаются друг от друга составом и порядком следования элементов, т.е. являются размещениями из 25 по 4.

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

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

Примеры:

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

Решение: Имеем перестановки из 5 элементов. 2. Сколькими способами можно собрать 6 разноцветных лоскутков в пеструю ленту?
Решение: Имеем перестановки из 6 элементов.

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

- число сочетаний из n по k

Элементы каждого из сочетаний можно расставить способами. Тогда Примеры:

1. Если в полуфинале первенства по шахматам участвует 20 человек, а в финал выходят лишь трое, то сколькими способам и можно определить эту тройку?

Решение: В данном случае порядок, в котором располагается эта тройка, не существенен. Поэтому тройки, вышедшие в финал, являются сочетаниями из 20 по 3.

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

Решение: В данном случае порядок, в котором располагается эта тройка, не существенен. Поэтому тройки делегатов являются сочетаниями из 10 по 3.

Конспект:

4.Применение графов (схем) при решении комбинаторных задач.

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

Задача:

При составлении команд космического корабля учитывается вопрос и психологической совместимости участников путешествия. Необходимо составить команду космического корабля из 3 человек: командира, инженера и врача. На место командира есть 4 кандидата: a 1 , a 2 , a 3 , a 4 .На место инженера- 3: b 1 , b 2 , b 3 . На место врача- 3: c 1 , c 2 , c 3 . Проведенная проверка показала, что командир a 1 психологически совместим с инженерами b 1 и b 3 и врачами c 1 и c 3 . Командир a 2 - с инженерами b 1 и b 2 . и всеми врачами. Командир a 3 - с инженерами b 1 и b 2 и врачами c 1 и c 3 . Командир a 4 -со всеми инженерами и врачом c 2 . Кроме того, инженер b 1 не совместим с врачом c 3 , b 2 - с врачом c 1 и b 3 - с врачом c 2 . Сколькими способами при этих условиях может быть составлена команда корабля?

Решение:

Составим соответствующее «дерево».

Ответ: 10 комбинаций.

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

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

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

Большинство комбинаторных задач решается с помощью двух основных правил – правила суммы и правила произведения .

Задача 1.

В магазине «Все для чая» есть 6 разных чашек и 4 разных блюдца. Сколько вариантов чашки и блюдца можно купить?

Решение .

Чашку мы можем выбрать 6-ю способами, а блюдце 4-я способами. Так как нам надо купить пару чашку и блюдце, то это можно сделать 6 · 4 = 24 способами (по правилу произведения).

Ответ: 24.

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

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

Задача 2.

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

Решение.

Для выбора формулы выясняем, что для чисел, которые мы будем составлять, порядок учитывается и не все элементы одновременно выбираются. Значит, это соединение – размещение из 7 элементов по 3. Воспользуемся формулой для числа размещений: A 7 3 = 7(7 – 1)(7 – 2) = 7 · 6 · 5 = 210 чисел.

Ответ: 210.

Задача 3.

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

Решение.

На первый взгляд эта задача такая же, как и предыдущая, но сложность в том, что надо не учитывать те соединения, которые начинаются с нуля. Значит необходимо из существующих 10-ти цифр составить все семизначные номера телефонов, а потом от полученного числа отнять количество номеров, начинающихся с нуля. Формула будет иметь вид:

A 10 7 – A 9 6 = 10 · 9 · 8 · 7 · 6 · 5 · 4 – 9 · 8 · 7 · 6 · 5 · 4 = 544 320.

Ответ: 544 320.

Задача 4.

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

Решение.

Сначала примем 5 сборников условно за одну книгу, потому что они должны стоять рядом. Так как в соединении существенным есть порядок, и все элементы используются, значит это перестановки из 8 элементов (7 книг + условная 1 книга). Их количество Р 8 . Далее будем переставлять между собой только сборники стихотворений. Это можно сделать Р 5 способами. Поскольку нам нужно расставить и сборники, и другие книги, то воспользуемся правилом произведения. Следовательно, Р 8 · Р 5 = 8! · 5!. Число способов будет большим, поэтому ответ можно оставить в виде произведения факториалов.

Ответ: 8! · 5!

Задача 5 .

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

Решение.

Сначала отдельно выберем 4 мальчика из 16 и 3 девочки из 12. Так как порядок размещения не учитывается, то соответственные соединения – сочетания без повторений. Учитывая необходимость одновременного выбора и мальчиков, и девочек, используем правило произведения. В результате число способов будет вычисляться таким образом:

С 16 4 · С 12 3 = (16!/(4! · 12!)) · (12!/(3! · 9!)) = ((13 · 14 · 15 · 16) / (2 · 3 · 4)) ·((10 · 11 · 12) / (2 · 3)) = 400 400.

Ответ: 400 400.

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

Остались вопросы? Не знаете, как решать комбинаторные задачи?
Чтобы получить помощь репетитора – зарегистрируйтесь .
Первый урок – бесплатно!

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

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

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

Комбинаторные конфигурации

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

• размещение;
• перестановка;
• сочетание;
• композиция числа;
• разбиение числа.

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

Разделы

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

• перечислительная;
• структурная;
• экстремальная;
• теория Рамсея;
• вероятностная;
• топологическая;
• инфинитарная.

В первом случае речь идет об исчисляющей комбинаторике, задачи рассматривают перечисление или подсчет разных конфигураций, которые образованы элементами множеств. На данные множества, как правило, накладываются какие-либо ограничения (различимость, неразличимость, возможность повтора и так далее). А количество этих конфигураций подсчитывается при помощи правила сложения или умножения, о которых мы поговорим немного позже. К структурной комбинаторике относятся теории графов и матроидов. Пример задачи экстремальной комбинаторики - какова наибольшая размерность графа, который удовлетворяет следующим свойствам… В четвертом пункте мы упомянули теорию Рамсея, которая изучает в случайных конфигурациях наличие регулярных структур. Вероятностная комбинаторика способна нам ответить на вопрос - какова вероятность того, что у заданного множества присутствует определенное свойство. Как нетрудно догадаться, топологическая комбинаторика применяет методы в топологии. И, наконец, седьмой пункт - инфинитарная комбинаторика изучает применение методов комбинаторики к бесконечным множествам.

Правило сложения

Среди формул комбинаторики можно найти и довольно простые, с которыми мы достаточно давно знакомы. Примером является правило суммы. Предположим, что нам даны два действия (С и Е), если они взаимоисключаемы, действие С выполнимо несколькими способами (например а), а действие Е выполнимо b-способами, то выполнить любое из них (С или Е) можно а+b способами.

В теории это понять достаточно трудно, постараемся донести всю суть на простом примере. Возьмем среднюю численность учеников одного класса - допустим, это двадцать пять. Среди них пятнадцать девочек и десять мальчиков. Ежедневно в классе назначается один дежурный. Сколько есть способов назначить дежурного по классу сегодня? Решение задачи достаточно простое, мы прибегнем к правилу сложения. В тексте задачи не сказано, что дежурными могут быть только мальчики или только девочки. Следовательно, им может оказаться любая из пятнадцати девочек или любой из десяти мальчиков. Применяя правило суммы, мы получаем достаточно простой пример, с которым без труда справится школьник начальных классов: 15 + 10. Подсчитав, получаем ответ: двадцать пять. То есть существует всего двадцать пять способов назначить на сегодня дежурного класса.

Правило умножения

К основным формулам комбинаторики относится и правило умножения. Начнем с теории. Допустим, нам необходимо выполнить несколько действий (а): первое действие выполняется с1 способами, второе - с2 способами, третье - с3 способами и так далее до последнего а-действия, выполняемого са способами. Тогда все эти действия (которых всего у нас а) могут быть выполнены N способами. Как высчитать неизвестную N? В этом нам поможет формула: N = с1 * с2 * с3 *…* са.

Опять же, в теории ничего не понятно, переходим к рассмотрению простого примера на применение правила умножения. Возьмем все тот же класс из двадцати пяти человек, в котором учится пятнадцать девочек и десять мальчиков. Только на этот раз нам необходимо выбрать двух дежурных. Ими могут быть как только мальчики или девочки, так и мальчик с девочкой. Переходим к элементарному решению задачи. Выбираем первого дежурного, как мы решили в прошлом пункте, у нас получается двадцать пять возможных вариантов. Вторым дежурным может быть любой из оставшихся человек. У нас было двадцать пять учеников, одного мы выбрали, значит вторым дежурным может быть любой из оставшихся двадцати четырех человек. Наконец, применяем правило умножения и получаем, что двоих дежурных можно избрать шестью сотнями способов. Мы данное число получили умножением двадцати пяти и двадцати четырех.

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

Сейчас мы рассмотрим еще одну формулу комбинаторики. В данном разделе статьи мы поговорим о перестановках. Рассмотреть проблему предлагаем сразу же на примере. Возьмем бильярдные шары у нас их n-ое количество. Нам нужно подсчитать: сколько есть вариантов расставить их в ряд, то есть составить упорядоченный набор.

Начнем, если у нас нет шаров, то и вариантов расстановки у нас так же ноль. А если у нас шар один, то и расстановка тоже одна (математически это можно записать следующим образом: Р1 = 1). Два шара можно расставить двумя разными способами: 1,2 и 2,1. Следовательно, Р2 = 2. Три шара можно расставить уже шестью способами (Р3=6): 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,2,1; 3,1,2. А если таких шаров не три, а десять или пятнадцать? Перечислять все возможные варианты очень долго, тогда нам на помощь приходит комбинаторика. Формула перестановки поможет нам найти ответ на интересующий нас вопрос. Pn = n *P (n-1). Если попытаться упростить формулу, то получаем: Pn = n* (n - 1) *…* 2 * 1. А это и есть произведение первых натуральных чисел. Такое число называется факториалом, а обозначается как n!

Рассмотрим задачу. Вожатый каждое утро выстраивает свой отряд в шеренгу (двадцать человек). В отряде есть три лучших друга - Костя, Саша и Леша. Какова вероятность того, что они будут стоять рядом? Чтобы найти ответ на вопрос, нужно вероятность «хорошего» исхода поделить на общее количество исходов. Общее число перестановок составляет 20! = 2,5 квинтиллиона. Как посчитать количество «хороших» исходов? Предположим, что Костя, Саши и Леша - это один сверхчеловек. Тогда мы имеем всего восемнадцать субъектов. Число перестановок в данном случае равняется 18 = 6,5 квадриллионов. При всем этом, Костя, Саша и Леша могут произвольно перемещаться между собой в своей неделимой тройке, а это еще 3! = 6 вариантов. Значит всего «хороших» расстановок у нас 18! * 3! Нам остается только найти искомую вероятность: (18! * 3!) / 20! Что равняется примерно 0,016. Если перевести в проценты, то это получается всего 1,6%.

Размещение

Сейчас мы рассмотрим еще одну очень важную и необходимую формулу комбинаторики. Размещение - это наш следующий вопрос, который предлагаем вам рассмотреть в данном разделе статьи. Мы идем на усложнение. Предположим, что мы хотим рассмотреть возможные перестановки, только не из всего множества (n), а из меньшего (m). То есть мы рассматриваем перестановки из n предметов по m.

Основные формулы комбинаторики стоит не просто заучивать, а понимать их. Даже несмотря на то, что они усложняются, так как у нас не один параметр, а два. Предположим, что m = 1, то и А = 1, m = 2, то А = n * (n - 1). Если далее упрощать формулу и перейти на запись при помощи факториалов, то получится вполне лаконичная формула: А = n! / (n - m)!

Сочетание

Мы рассмотрели практически все основные формулы комбинаторики с примерами. Теперь перейдем к заключительному этапу рассмотрения базового курса комбинаторики - знакомство с сочетанием. Сейчас мы будем выбирать m предметов из имеющихся у нас n, при этом всем мы будем выбирать всеми возможными способами. Чем же тогда это отличается от размещения? Мы не будем учитывать порядок. Этот неупорядоченный набор и будет являться сочетанием.

Сразу введем обозначение: С. Берем размещения m шариков из n. Мы перестаем обращать внимание на порядок и получаем повторяющиеся сочетания. Чтобы получить число сочетаний нам надо поделить число размещений на m! (m факториал). То есть С = А / m! Таким образом, способов выбрать из n шаров немножко, равняется примерно столько, сколько выбрать почти все. Этому есть логическое выражение: выбрать немножко все равно, что выкинуть почти все. Еще в данном пункте важно упомянуть и то, что максимальное число сочетаний можно достигнуть при попытке выбрать половину предметов.

Как выбрать формулу для решения задачи?

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

1. Задайте себе вопрос: порядок размещения элементов учитывается в тексте задачи?
2. Если ответ нет, то воспользуйтесь формулой сочетания (С = n! / (m! * (n - m)!)).
3. Если ответ нет, то необходимо ответить на еще один вопрос: все ли элементы входят в комбинацию?
4. Если ответ да, то воспользуйтесь формулой перестановки (Р = n!).
5. Если ответ нет, то воспользуйтесь формулой размещения (А = n! / (n - m)!).

Пример

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

Вопрос первый: сколькими способами их можно переставить? Для этого воспользуемся формулой перестановок: Р = 3! = 6 способов.

Вопрос второй: сколькими способами можно выбрать один фрукт? Это очевидно, у нас всего три варианта - выбрать киви, апельсин или банан, но применим формулу сочетаний: С = 3! / (2! * 1!) = 3.

Вопрос третий: сколькими способами можно выбрать два фрукта? Какие есть у нас вообще варианты? Киви и апельсин; киви и банан; апельсин и банан. То есть три варианта, но это легко проверить при помощи формулы сочетания: С = 3! / (1! * 2!) = 3

Вопрос четвертый: сколькими способами можно выбрать три фрукта? Как видно, выбрать три фрукта можно одним-единственным способом: взять киви, апельсин и банан. С = 3! / (0! * 3!) = 1.

Вопрос пятый: сколькими способами можно выбрать хотя бы один фрукт? Это условие подразумевает, что мы можем взять один, два или все три фрукта. Следовательно, мы складываем С1 + С2 + С3 =3 + 3 + 1 = 7. То есть у нас есть семь способов взять со стола хотя бы один фрукт.

Формулы комбинаторики.

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

Размещения .

Определœение 1. Размещением без повторений из n элементов по k принято называть всякое упорядоченное подмножество данного множества M={a 1 ,a 2 ,¼,a n }, содержащее k элементов.

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

Теорема 1. Число различных размещений без повторений из n элементов по k (k£ n) равно

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

Пусть M ={a 1 ,a 2 ,¼,a n }. Требуется определить число различных строк вида (x 1 ,x 2 ,¼,x k ), где всœе элементы x 1 ,x 2 ,¼,x k ÎM и различны. Первый элемент x 1 можно выбрать n способами. В случае если x 1 уже выбран, то для выбора x 2 осталось n-1 элементов. Аналогично, x 3 можно выбрать n -2 способами и т.д. Последний элемент x k можно выбрать n-k+1 способами. Перемножая эти числа, получим формулу (4).Теорема доказана.

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

Число всœевозможных вариантов расписания есть, очевидно, число различных размещений из 12 элементов по 5, то есть

Важным частным случаем, является случай, когда n=k , то есть когда в строке (x 1 ,x 2 ,¼,x n) участвуют всœе элементы множества M . Строки без повторений, составленные из n элементов множества M называют перестановками из n элементов. Напомним, что в математике через n! обозначают произведение всœех натуральных чисел от 1 до n, то есть ¼и по определœению считают, что 0!=1.

Следствие 1 . Пользуясь формулой (4), находим, что число различных перестановок P n из n элементов равно P n = n !.

Определœение 2. Размещением с повторениями из n элементов по k принято называть любая упорядоченная строка из k элементов множества M={a 1 ,a 2 ,¼,a n }, некоторые из которых могут повторяться.

К примеру, слово “мама” есть размещение с повторениями из 2-х элементов M ={м, а} по 4.

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

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

Первый элемент в строку из k элементов должна быть выбран n способами, поскольку |M|=n. Точно также 2-й, 3-й, …,k-й элементы бывают выбраны n способами. Перемножая эти числа, получим

k раз

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

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

В этой задаче M ={1, 2, 3, 4, 5}, n=5, k=2.По этой причине ответом является число

Пример 3. Сколькими способами k пассажиров могут распределиться по n вагонам, в случае если для каждого пассажира существенным является только номер вагона, а не занимаемое им в вагоне место?

Перенумеруем всœех пассажиров. Пусть x 1 - номер вагона, выбранного первым пассажиром, x 2 - номер вагона второго пассажира, …, x k - номер вагона k -го пассажира. Строка (x 1 ,x 2 ,¼,x k ) полностью характеризует распределœение пассажиров по вагонам. Каждое из чисел x 1 ,x 2 ,¼,x k может принимать любое целое значение от 1 до n. По этой причине в данном примере

M ={1, 2,…,n} и различных распределœений по вагонам будет столько же, сколько строк длиной k можно составить из элементов множества M , то есть

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

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

Определœение 3. Пусть M={a 1 ,a 2 ,¼,a n }. Любое подмножество X мно-жества M , содержащее k элементов, принято называть сочетанием k элементов из n.

Отметим сразу, что в данном определœении порядок следования элементов множества X несущественен и, что k£n , поскольку k=½X½, n=½M½ и XÍM .

Теорема 3. Число различных сочетаний k элементов из n равно

. (6)

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

Каждое сочетание k элементов из n порождает k! различных размещений без повторений из n по k с помощью различных перестановок (см. следствие 1). Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, всœе сочетаний из k элементов из n после различных k! перестановок порождают всœе размещений без повторений из n по k . По этой причине . Следовательно,