Элементы комбинаторики. Лекция

Правило сложения используется в том случае, если у нас есть два или более множеств, которые попарно не пересекаются, то есть не имеют общих элементов. И нам нужно найти сколько элементов содержится в объединении этих множеств. В этом случае мы складываем число элементов в каждом множестве. Простейший пример: если у нас есть две корзинки с фруктами: в одной 5 яблок, а в другой 7 груш. Если мы эти фрукты пересыпаем в одну корзинку (объединяем множества), тогда в новой корзинке окажется 5+7=12 фруктов.

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

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

Действительно. Возьмем первое яблоко. Мы можем положить к нему любую из семи груш, то есть получаем 7 пар. Возьмем второе яблоко, и к нему мы также можем положить любую из 7-ми груш, получаем ещё 7 пар. И так далее. Всего получается пар.

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

Пусть двузначное чиcло имеет вид , где - число десятков, - число единиц. При этом цифра может принимать значения от 1 до 9 (цифра 0 не может стоять на первом месте, так как в этом случаем мы получим однозначное число), цифра может принимать значения от 0 до 9.

Пусть , и у нас есть 10 вариантов цифр, которые могут стоять на втором месте. Тогда мы имеем 10 двузначных чисел, содержащих 1 десяток.

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

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

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

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

Если элемент A можно выбрать n способами, и при любом выборе A элемент B можно выбрать m способами, то пару (A, B) можно выбрать n·m способами. Это правило распространяется на любое число независимо выбираемых элементов.

Если мы хотим ответить на вопрос, сколько существует трехзначных чисел, мы заметим, что в трехзначном числе первая цифра может принимать 9 значений, вторая - 10, и третья - 10 значений. И мы получаем трехзначных чисел.

Формула включений-исключений

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

Пусть множество А содержит n элементов, множество В содержит m элементов, и пересечение этих множеств содержит k элементов. То есть k элементов содержатся и в множестве А, и в множестве В. Тогда объединение множеств содержит m+n-k элементов.

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

Число элементов в множестве обозначается общепринятым значком #. Тогда формула для подсчета числа элементов в объединении трех множеств имеет вид:

## # # # # # #

Рассмотрим примеры задач.

1. Сколько трехзначных чисел содержит хотя бы одну цифру 3?

Если вопрос задачи содержит слова "хотя бы", то в большинстве случаев сначала надо ответить на противоположное утверждение.

Найдем, сколько трехзначных чисел НЕ содержит цифру 3. В этом случае на первом, втором и третьем месте в записи числа может стоять любая цифра кроме 3. То есть первая цифра может принимать 8 значений, вторая - 9, и третья - 9 значений. Тогда мы получаем трехзначных чисел, которые НЕ содержит цифру 3. Следовательно, остальные числа содержат хотя бы одну цифру 3.

2. Сколько четырехзначных чисел, кратных 5.

Мы знаем, что число делится на 5, если оно оканчивается на 0 или 5. Следовательно, в четырехзначном числе последняя цифра может принимать только два значения: 0 и 5.
Первая цифра может принимать 9 значений, вторая - 10, и третья - 10 значений, четвертая - 2 значения.

Тогда мы получаем четырехзначных чисел, которые делятся на 5.

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

Воспользуемся правилом умножения чтобы ответить на вопрос, "сколькими способами можно построить 7 человек в шеренгу?" .

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

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

способов расположения этих объектов.

Факториалом натурального числа называется произведение всех натуральных чисел от 1 до :

По определению 0!=1; 1!=1.

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

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

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

1. Каждый диск лежит в своей коробке.

2. Хотя бы один диск лежит не в своей коробке.

3. Два определенных диска перепутаны местами, а остальные в своих коробках.

4. Ровно один лежит не в своей коробке, а остальные - в своих коробках.

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

Расположить 10 чисел в определенной последовательности можно единственным способом, то есть мы имеем 1 благоприятный исход.

Расположить 10 чисел в произвольном порядке можно 10! способами.

Следовательно, вероятность того, что каждый диск окажется в своей коробке равна

2. Событие "хотя бы один диск лежит не в свой коробке " противоположно событию "", и его вероятность равна

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

4. Событие "ровно один лежит не в своей коробке, а остальные - в своих коробках " невозможно, так как если один диск лежит не своей коробке, то обязательно должен найтись ещё один, который так же лежит не в своей коробке. Поэтому вероятность этого события равна нулю.

4. Слово "МАТЕМАТИКА" написали на полоске картона и разрезали полоску на буквы. Найдите вероятность того, что составив все эти буквы случайным образом в ряд, мы снова получим слово "МАТЕМАТИКА".

МАТЕМАТИКА"?

Вероятность того, что на первом месте будет стоять буква М равна 2/10 - у нас две буквы М, и всего 10 букв.

Вероятность того, что на втором месте будет стоять буква А равна 3/9 - у нас осталось 9 букв, из которых 3 буквы А.

Вероятность того, что на втором месте будет стоять буква Т равна 2/8 - у нас осталось 8 букв, из которых 2 буквы Т.

Пронумеруем все буквы в слове "МАТЕМАТИКА". Найдем, сколькими способами мы можем их расположить в определенном порядке. В слове 10 букв, и мы можем их расположить 10!=3628800 различными способами.

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

в слове "МАТЕМАТИКА" 2 буквы "М"; 3 буквы "А"; 2 буквы "Т", следовательно по правилу произведения это дает нам способов перестановки этих букв с сохранением слова "МАТЕМАТИКА".

Таким образом, вероятность снова получить слово "МАТЕМАТИКА" равна:

Сколько буквосочетаний можно составить из букв слова "МАТЕМАТИКА" ?

Из 10 букв слова "МАТЕМАТИКА" можно составить 10! буквосочетаний. Но некоторые из них будут одинаковыми, так как при перестановке одинаковых букв, мы будем получать те же буквосочетания. То есть в итоге мы получим

буквосочетаний.

Размещения

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

5. Сколько существует различных вариантов выбора 4-х кандидатур из 9-ти специалистов для поездки в 4 различных страны?

Воспользуемся правилом умножения.

В первую страну мы выбираем из 9 специалистов, то есть у нас 9 вариантов выбора. После того, как специалист для поездки в первую страну выбран, у нас осталось 8 специалистов, и для поездки во вторую страну у нас 8 вариантов выбора. И так далее... в четвертую страну мы можем выбрать кандидата из 6 специалистов.

Таким образом, мы получаем вариантов выбора 4-х кандидатур из 9-ти специалистов для поездки в 4 различных страны.

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

Рассуждая аналогичным образом, мы получаем

вариантов.

Если умножить и разделить это выражение на , то получим следующую формулу:

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

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

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

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

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

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

При бросании кости первый раз мы получим 6 различных вариантов: 1 очко, 2, 3... или 6. Аналогично при бросании кости во второй и в третий раз мы получим также по 6 различных вариантов. По правилу умножения получим число различных комбинаций трех чисел, принимающих значения от 1 до 6:

В общем случае:

Пусть у нас есть множество , состоящее из элементов.

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

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

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

Сочетания

Рассмотрим задачу, аналогичную задаче 5, но с существенным отличием.

7. Сколько существует различных вариантов выбора 4-х кандидатур из 9-ти специалистов?

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

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

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

способов.

В этой задаче появляется понятие сочетания .

Сочетаниями из n элементов по k элементов называются подмножества, состоящие из k элементов множества (множества, состоящего из n элементов).

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

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

и находится по формуле:

Число сочетаний из n по k показывает, сколькими способами мы можем выбрать k элементов из n элементов, или сколькими способами мы можем расположить k объектов по n местам.

Легко заметить, что

8. В коробке лежат 8 красных карандашей и 4 синих. Из коробки наугад вынимают 4 карандаша. Какова вероятность того, что среди них окажется 2 красных и 2 синих?

Всего в коробке 12 карандашей. Найдем, сколькими способами способами можно извлечь из коробки 4 карандаша. Так как нас не интересует порядок, в котором карандаши извлекаются из коробки, а только состав карандашей, это число равно числу сочетаний из 12 по 4:

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

Из 4 синих карандашей можно извлечь два карандаша способами.

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

Таким образом, искомая вероятность равна:

Метод шаров и перегородок

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

Рассмотрим 10 шаров:

Будем "раскладывать шары по коробкам", ставя перегородки.

Например, так:

В этом примере в первой коробке 3 шара, во второй - 2, в третьей - 4, и в четвертой - 2. Переставляя шары и перегородки, мы получаем различные комбинации шаров в коробках. Например, переставив последний шар в первой коробке и первую внутреннюю перегородку, мы получим такую комбинацию:

Таким образом, мы получаем различное число шаров в коробках, комбинируя позиции 10-ти шаров и 3-х внутренних перегородок. Чтобы определить, сколько различных комбинаций мы можем получить, нам нужно найти число сочетаний из 13 по 3. (Или, что то же самое, что число сочетаний из 13 по 10.) Столько способов выбрать 3 места для перегородок из 13 возможных позиций. Или, что то же самое, 10 мест для шаров.

10. Сколько решений имеет уравнение в целых неотрицательных числах?

Так как переменные могут принимать только целые неотрицательные значения, следовательно, у нас есть 10 переменных, и они могут принимать значения 0, 1, 2, 3 и 4. Представим, что у нас есть 10 коробок (это переменные), и мы должны разложить по этим коробкам 4 шара. Сколько шаров попадет в коробку, таково значение соответствующей переменной. Если у нас 10 коробок, следовательно, 10-1=9 внутренних перегородки. И 4 шара. Всего 13 мест. Нам надо расположить на этих 13 местах 4 шара. Число таких возможностей:

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

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

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

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

Что такое сочетания из элементов по элементов с повторениями можно понять с помощью такого мысленного эксперимента. Представим ящик с пронумерованными шарами. Мы вынимаем шар, записываем его номер и возвращаем обратно, и так раз. В отличие от размещений с повторениями нас не интересует порядок записанных чисел, а только их состав. Например, группы чисел {1,1,2,1,3,1,2} и {1,1,1,1,2,2,3} считаются одинаковыми. Сколько таких групп из номеров мы можем получить?

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

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

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

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

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

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

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

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

Если вкратце: множеством именуют некую совокупность объектов. Записывают множества в фигурных скобках. Порядок записи элементов роли не играет; повторения элементов не допускаются. Например, множество цифр числа 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)\neq(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}=n^k \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}=3^5=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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

I способ. Постараемся выписать все такие числа. На первом месте может стоять любая цифра кроме 0. Например, 2. На втором месте любая цифра из 0, 4, 6 и 8. Пусть 0. Тогда в качестве третьей цифры можно выбрать любую из 4, 6, 8. Получаем три числа

Вместо 0 на второе место можно было поставить 4, тогда третье цифрой можно записать или 0, или 6, или 8:

Рассуждая аналогично, получаем ещё две тройки трёхзначных чисел с цифрой 2 на первом месте:

Других, кроме выписанных 12-ти, трёхзначных чисел с цифрой 2 на первом месте, и удовлетворяющих условию, нет.

Если на первом месте записать цифру 4, а остальные выбирать из цифр 0, 2, 6, 8, то получим ещё 12 чисел:

По столько же трёхзначных чисел можно составить с цифрой 6 на первом месте и цифрой 8 на первом месте. Значит, искомое количество:

Вот эти числа:

204, 206, 208, 240, 246, 248, 260, 264, 268, 280, 284, 286;

402, 406, 408, 420, 426, 428, 460, 462, 468, 480, 482, 486;

602, 604, 608, 620, 624, 628, 640, 642, 648, 680, 682, 684;

802, 804, 806, 820, 824, 826, 840, 842, 846, 860, 862, 864.

Ответ: 48. ◄

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

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

Комбинаторное правило сложения (правило "или") — одно из основных правил комбинаторики, утверждающее, что, если имеется n элементов и элемент A 1 можно выбрать m 1 способами, элемент A 2 можно выбрать m 2 A n можно выбрать m n способами, то выбрать или A 1 , или A 2 , или, и так далее, A n можно

m 1 + m 2 + ... + m n

способами.

Например, выбрать подарок ребёнку из 9 машинок, 7 плюшевых медведей и 3 железных дорог можно

способами.

Ответ: 19. ◄

Правило умножения (правило "и") — ещё одно из важных правил комбинаторики. Согласно ему, если элемент A 1 можно выбрать m 1 способами, элемент A 2 можно выбрать m 2 способами и так далее, элемент A n можно выбрать m n способами, то набор элементов (A 1 , A 2 , ... , A n ) можно выбрать

m 1 · m 2 · ... · m n

способами.

Например.

1) Выбрать ребёнку в подарок машинку, плюшевого медведя и железную дорогу, выбирая из 9 машинок, 7 плюшевых медведей и 3 железных дорог, можно

9 · 7 · 3 = 189

способами.

Ответ: 189.

2) Воспользуемся правилом умножения для решения задачи, уже рассмотренной выше: Сколько трёхзначных чисел можно составить из цифр 0, 2, 4, 6, 8, используя в записи числа каждую из них не более одного раза?

II способ.

0 не может стоять первым, значит первую цифру нужно выбрать из 2, 4, 6, 8 — 4 способа;

второй цифрой может быть любая из четырёх оставшихся — 4 способа;

третью цифру можно выбрать среди трёх оставшихся — 3 способа.

Итак, искомое количество трёхзначных чисел:

4 · 4 · 3 = 48.

Ответ: 48. ◄

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

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

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

Например, из 4 элементов ♦ ♣ ♠ можно составить следующие 24 перестановки:

♦ ♣ ♠	♦ ♣ ♠	♣ ♦ ♠	♠ ♦ ♣
♦ ♠ ♣	♦ ♠ ♣	♣ ♦ ♠	♠ ♦ ♣
♦ ♣ ♠	♣ ♦ ♠	♣ ♦ ♠	♠ ♦ ♣
♦ ♣ ♠	♣ ♠ ♦	♣ ♠ ♦	♠ ♣ ♦
♦ ♠ ♣	♠ ♦ ♣	♣ ♠ ♦	♠ ♣ ♦
♦ ♠ ♣	♠ ♣ ♦	♣ ♠ ♦	♠ ♣ ♦

◄

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

P 1 = 1; P 2 = 2; P 3 = 6; P 4 = 24.

Вообще, число всевозможных перестановок из n элементов равно произведению всех натуральных чисел от 1 до n , то есть n ! (читается "эн факториал"):

P n = 1 · 2 · 3 · ... · (n - 1 ) · n = n !.

Для P n справедлива рекуррентная формула:

P n = n · P n - 1 .

Значение факториала определено не только для натуральных чисел, но и для 0:

0! = 1 .

Таблица факториалов целых чисел от 0 до 10
n		1	2	3	4	5	6	7	8	9	10
n !	1	1	2	6	24	120	720	5 040	40 320	362 880	3 628 800

Например, сколькими способами 5 мальчиков и 5 девочек могут занять в театре места в одном ряду с 1-го по 10-е место, если никакие два мальчика и никакие две девочки не сидят рядом?

Возможны два случая с одинаковым количеством способов: 1) мальчики — на нечётных местах, девочки на чётных и 2) наоборот.

Рассмотрим первый случай. Мальчики по нечётным местам могут сесть

P 5 = 120

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

120 · 120 = 14 400

способами. Значит, всего способов

14 400 + 14 400 = 28 800.

Ответ: 28 800. ◄

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

Перестановкой с повторениями из n элементов, среди которых k разных, при этом насчитывается n 1 неразличимых элементов первого типа, n 2 неразличимых элементов второго типа и так далее, n k неразличимых элементов k -го типа (где n 1 + n 2 + … + n k = n ), называется любое расположение этих элементов по n различным местам.

Число перестановок с повторениями длины n из k разных элементов, взятых соответственно по n 1 , n 2 , …, n k раз каждый обозначается и вычисляется следующим образом:$$P_{n_1,n_2, ... , n_k}=\frac{n!}{n_1!n_2! ... n_k!}~.$$

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

В данном случае: n = 10, n 1 = 1, n 2 = 2, n 3 = 3, n 4 = 4,$$P_{1, 2, 3, 4}=\frac{10!}{1!2! 3! 4!}=\frac{10!}{1!2! 3! 4!}=12~600.$$

Ответ: 12 600. ◄

Размещения

Размещением из n элементов по m (m ≤ n) m элементов, взятых в определённом порядке из данных n элементов.

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

Например, составим все размещения из четырёх элементов A, B, C, D по два элемента:

A B; A C;A D;

B A; B C; B D;

C A; C В; C D;

D A; D В; D C.

◄

Число всех размещений из n элементов по m обозначают \(A_n^m\) (читается: "А из n по m ") и вычисляется по любой из формул:$$A_n^m=n\cdot (n-1)\cdot (n-2)\cdot ...\cdot (n-m+1)\\A_n^m=\frac{n!}{(n-m)!}$$

Примеры задач.

1) Воспользуемся понятием размещений из n элементов по m для решения задачи, уже дважды рассмотренной ранее: Сколько трёхзначных чисел можно составить из цифр 0, 2, 4, 6, 8, используя в записи числа каждую из них не более одного раза?

II I способ.

Первую цифру можно выбрать четырьмя способами из набора 2, 4, 6, 8. В каждом из этих случаев количество пар второй и третей цифры равно числу размещений из 4 оставшихся цифр по 2. Значит искомое количество трёхзначных чисел равно:$$4\cdot A_4^2=4\cdot \frac{4!}{(4-2)!}=4\cdot \frac{4!}{2!}=4\cdot (3\cdot 4)=48.$$Ответ: 48.

2) Для полёта в космос необходимо укомплектовать экипаж из шести человек. В него должны входить: командир корабля, первый и второй его помощники, два бортинженера, один из которых старший, и один врач. Командный состав выбирается из 20 лётчиков, бортинженеры — из 15 специалистов, а врач — из 5 медиков. Сколькими способами можно укомплектовать экипаж?

Поскольку в выборе командного состава важен порядок, то командира и двух его помощников можно выбрать \(A_{20}^3\) способами. Порядок бортинженеров тоже важен, значит, для их выбора существует \(A_{15}^2\) способов. Врач всего один, для его выбора существует 5 способов. Воспользуемся комбинаторным правилом умножения и найдём количество возможных экипажей корабля:$$A_{20}^3\cdot A_{15}^2\cdot 5=\frac{20!}{17!}\cdot \frac{15!}{13!}\cdot 5=(18\cdot 19\cdot 20)\cdot (14\cdot 15)\cdot 5=7~182~000.$$Ответ: 7 182 000. ◄

Понятно, что, если m = n , то$$A_n^m=A_n^n=P_n=n!.$$

Справедливо также, что, если m = n - 1 , то$$A_n^{n-1}=A_n^n=P_n=n!.$$

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

Помимо обычных размещений бывают и размещения с повторениями или выборки с возвращением .

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

Размещения с повторениями обозначаются \(\overline{A}_n^m\) и, согласно правилу умножения, вычисляются по формуле$$\overline{A}_n^m=n^m.$$Заметим, что здесь допустим случай, когда m > n , то есть выбранных объектов больше, чем их всего имеется. Это неудивительно: каждый объект после "использования" возвращается обратно и может быть использован повторно.

Например, количество вариантов шестизначного пароля, в котором каждый знак является цифрой от 0 до 9 или буквой латинского алфавита (одна и та же строчная и прописная буква — один символ) и может повторяться, равно:$$\overline{A}_{10+26}^6=\overline{A}_{36}^6=36^6=2~176~782~336.$$Если же строчные и прописные буквы считаются различными символами (как это обычно и бывает), то количество возможных паролей становится ещё более колоссальным:$$\overline{A}_{10+26+26}^6=\overline{A}_{62}^6=62^6=56~800~235~584.$$

◄

Сочетания

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

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

Например, составим все сочетания из четырёх элементов A, B, C, D по два элемента:

A B; A C;A D;

B C; B D;

C D .

◄

Число всех сочетаний из n элементов по m обозначают \(C_n^m\) (читается: "C из n по m ") и вычисляется по любой из формул:$$C_n^m=\frac{A_n^m}{P_m}$$$$C_n^m=\frac{n\cdot (n-1)\cdot (n-2)~\cdot~ ...~\cdot~ (n-m+1)}{1\cdot2\cdot3~\cdot~...~\cdot ~m}$$$$C_n^m=\frac{n!}{m!\cdot (n-m)!}.$$

Примеры задач.

1) Бригада, занимающаяся ремонтом школы, состоит из 12 маляров и 5 плотников. Из них для ремонта физкультурного зала надо выделить 4 маляров и 2 плотников. Сколькими способами можно это сделать?

Так как порядок маляров в каждой выбранной четвёрке и порядок плотников в каждой выбранной паре не имеет значения, то, согласно комбинаторному правилу умножения, искомое количество способов равно:$$C_{12}^4 \cdot C_5^2 =\frac{12!}{4!\cdot 8!}\cdot \frac{5!}{2!\cdot 3!}=\frac{9\cdot10\cdot11\cdot12}{1\cdot2\cdot3\cdot4}\cdot \frac{4\cdot5}{1\cdot 2}=4~950.$$Ответ: 4 950. ◄

2) В классе обучаются 30 учащихся, среди которых 13 мальчиков и 17 девочек. Сколькими способами можно сформировать команду из 7 учащихся этого класса, если в неё должна входить хотя бы одна девочка?

Количество всех возможных команд по 7 человек из класса равно \(C_{30}^7\). Количество команд в которых только мальчики — \(C_{13}^7\). Значит, количество команд, в которых есть хотя бы одна девочка, равно:$$C_{30}^7 - C_{13}^7 =\frac{30!}{7!\cdot 23!} - \frac{13!}{7!\cdot 6!}=2~035~800-1~716=2~034~084.$$Ответ: 2 034 084. ◄

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

Помимо обычных сочетаний рассматривают сочетания с повторениями .

Пусть в множестве имеется n объектов. Выберем из них m штук, действуя по следующему принципу. Возьмём любой, но не будем его устанавливать в какой-то ряд, а просто запишем, сам же объект после этого вернём к остальным. Затем опять из всех n объектов выберем один (в том числе, возможно, и тот, который был взят и записан ранее), запишем его название и снова вернём объект обратно. И так далее, пока не получим m названий.

Принципиальное отличие от размещений с повторениями заключается в том, что в данном случае элементы списка не нумеруются. Например, список "A, С, A, В" и список "А, А, В, С" считаются одинаковыми.

Сочетания с повторениями обозначаются \(\overline{C}_n^m\) и вычисляются по формуле$$\overline{C}_n^m=P_{m,~n-1}=\frac{(m+n-1)!}{m!\cdot (n-1)!}.$$И ещё один способ записи той же формулы:$$\overline{C}_n^m=C_{m+n-1}^m=\frac{(m+n-1)!}{m!\cdot (n-1)!}.$$Заметим, что подобно размещениям с повторениями, допустим случай, когда m > n , то есть выбранных объектов больше, чем их всего имеется. Действительно, каждый объект после "использования" возвращается обратно и может быть использован снова и снова.

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

Естественно полагать, что количество пирожных каждого вида не меньше 7, и при желании можно купить только пирожные одного из них. Так как порядок в котором кладут купленные пирожные в коробку не важен, то имеем дело с сочетаниями с повторениями. Так как нужно выбрать 7 пирожных из 4 его видов, то искомое количество способов равно:$$\overline{C}_4^7=\frac{(7+4-1)!}{7!\cdot (4-1)!}=\frac{10!}{7!\cdot 3!}=\frac{8\cdot 9\cdot 10}{1\cdot 2\cdot 3}=120.$$

Ответ: 120. ◄

Бином Ньютона и биномиальные коэффициенты

Равенство$$(x+a)^n=C_n^0x^na^0+C_n^1x^{n-1}a^1+...+C_n^mx^{n-m}a^m+...+C_n^nx^0a^n$$называют биномом Ньютона или формулой Ньютона . Правая часть равенства называется биномиальным разложением в сумму , а коэффициенты \(C_n^0,~C_n^1,~...~,~C_n^n\) — биномиальными коэффициентами .

Свойства биномиальных коэффициентов:

\(~~~~~~~~1.~~C_n^0=C_n^n=1\\ ~~~~~~~~2.~~C_n^m=C_n^{n-m}\\ ~~~~~~~~3.~~C_n^m=C_{n-1}^{m-1}+C_{n-1}^{m}\\ ~~~~~~~~4.~~C_n^0+C_n^1+C_n^2+~...~+C_n^n=2^n\\ ~~~~~~~~5.~~C_n^0+C_n^2+C_n^4+~... =C_n^1+C_n^3+C_n^5+~...=2^{n-1}\\ ~~~~~~~~6.~~C_n^n+C_{n+1}^n+C_{n+2}^n+~...~+C_{n+m-1}^n=C_{n+m}^{n+1}\\ \)

Свойства биномиального разложения:

1. Число всех членов разложения на единицу больше показателя степени бинома,

то есть равно n + 1 .

2. Сумма показателей степеней x и a каждого члена разложения равна показателю степени бинома,

то есть (n - m) + m = n .

3. Общий член разложения (обозначается T n +1 ) имеет вид$$T_{n+1}=C_n^m x^{n-m}a^m,~~~~m=0,~1,~2,~...~,~n.$$

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

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

					\(C_0^0\)
				\(C_1^0\)		\(C_1^1\)
			\(C_2^0\)		\(C_2^1\)		\(C_2^2\)
		\(C_3^0\)		\(C_3^1\)		\(C_3^2\)		\(C_3^3\)
	\(C_4^0\)		\(C_4^1\)		\(C_4^2\)		\(C_4^3\)		\(C_4^4\)
\(C_5^0\)		\(C_5^1\)		\(C_5^2\)		\(C_5^3\)		\(C_5^4\)		\(C_5^5\)
	. . .				. . .				. . .

В этом треугольнике крайние числа в каждой строке равны 1. Действительно, \(C_n^0=C_n^n=1\). А каждое не крайнее число равно сумме двух чисел предыдущей строки, стоящих над ним: \(C_n^m=C_{n-1}^{m-1}+C_{n-1}^{m}\).

Таким образом, этот треугольник предлагает ещё один (рекуррентный) способ вычисления чисел \(C_n^m\):

n = 0									1
n = 1								1		1
n = 2							1		2		1
n = 3						1		3		3		1
n = 4					1		4		6		4		1
n = 5				1		5		10		10		5		1
n = 6			1		6		15		20		15		6		1
n = 7		1		7		21		35		35		21		7		1
n = 8	1		8		28		56		70		56		28		8		1
...				...				...		...				...

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

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

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

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

Такие размещения называются размещениями без повторений .

ПРИМЕР . В группе 25 студентов. Выбирают старосту, физорга и профорга. Каково число всех возможных вариантов выбора «треугольника» группы?

Решение . Получаемые комбинации (т.е. соединения) из 25 - и элементов по 3 в каждом являются размещениями, так как в них важен не только состав элементов «треугольника», но и расположение внутри него. Следовательно

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

ПРИМЕР 1 . Известно, что 4 студента сдали экзамен. Сколько возможно различных исходов экзамена (распределений оценок)?

Решение . Число элементов =3 («3», «4», «5»); . Последовательность, т. е. порядок элементов, существенна, повторения неизбежны. Следовательно .

ПРИМЕР 2 . Сколькими способами 10 пассажиров могут распределиться по 13 вагонам, если для каждого существенным является только № вагона, а не занимаемое место в нем?

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

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

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

ПРИМЕР . Для проведения испытаний выбрано 5 различных моделей автомобилей. Сколькими способами они могут быть распределены между пятью испытателями?

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

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

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

ПРИМЕР . Каким числом способов можно распределить 9 цитрусовых между 9 студентами, если имеются 4 мандарина, 3 апельсина и 2 лимона?

Решение . Пусть - мандарины, - апельсины и - лимоны. Тогда

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

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

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

Число сочетаний обладает следующими свойствами :

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

3. (см. первое свойство).

ПРИМЕР . На строительство общежития из 25 студентов требуется выбрать 3 человек. Каково число всех возможных вариантов выбора этой тройки?

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

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

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

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

ПРИМЕР . Каким числом способов можно составить расписание занятий из 3-х пар на один день, если изучается 10 предметов, которые могут повторяться в расписании. Расписания считаются различными, если отличаются друг от друга, хотя бы одним предметом (т.е. порядок предметов в расписании роли не играет)?

Решение . .

Замечания.

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