Планирование 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сочетания. Размещения. Перестановки

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

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

Решение:

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

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

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

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

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

Число всех возможных размещений рассчитывается

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

Решение:

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

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

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

Пример: сколькими способами можно выбрать 2 детали из ящика, содержащего 10 деталей?

Решение:

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

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

Пример: имеется 6 штаммов бактерий. Для определения скорости их роста необходимо выбрать три штамма. Сколькими способами можно это сделать?

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

То есть имеется 20 способов.

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

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

Правило суммы: если некоторый объект A может быть выбран из совокупности объектов m способами, а другой объект В может быть выбран n способами, то выбрать либо А , либо В можно способами.

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

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

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

Французский философ, писатель, математик и физик Блез Паскаль (1623–1662) рано проявил свои выдающиеся математические способности. Круг математических интересов Паскаля был весьма разнообразен. Паскаль доказал одну
из основных теорем проективной геометрии (теорема Паскаля), сконструировал суммирующую машину (арифмометр Паскаля), дал способ вычисления биномиальных коэффициентов (треугольник Паскаля), впервые точно определил и применил для доказательства метод математической индукции, сделал существенный шаг в развитии анализа бесконечно малых, сыграл важную роль в зарождении теории вероятности. В гидростатике Паскаль установил ее основной закон (закон Паскаля). “Письма к провинциалу” Паскаля явились шедевром французской классической прозы.

Готфрид Вильгельм Лейбниц (1646–1716) — немецкий философ, математик, физик и изобретатель, юрист, историк, языковед. В математике наряду с И. Ньютоном разработал дифференциальное и интегральное исчисление. Важный вклад внес в комбинаторику. С его именем, в частности, связаны теоретико-числовые задачи.

Готфрид Вильгельм Лейбниц имел мало внушительную внешность и поэтому производил впечатление довольно невзрачного человека. Однажды в Париже он зашел в книжную лавку в надежде приобрести книгу своего знакомого философа. На вопрос посетителя об этой книге книготорговец, осмотрев его с головы до ног, насмешливо бросил: “Зачем она вам? Неужели вы способны читать такие книги?” Не успел ученый ответить, как в лавку вошел сам автор книги со словами: “Великому Лейбницу привет и уважение!” Продавец никак не мог взять втолк, что перед ним действительно знаменитый Лейбниц, книги которого пользовались большим спросом среди ученых.

В дальнейшем важную роль будет играть следующая

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Числа

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

Свойства чисел {\sf C}_n^k

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

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

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

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

Теорема.

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

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

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

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

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

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

Задачи.

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

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

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

Большинство формул комбинаторики используют понятие факториала. Термин «факториал» произошел от латинского слова factor («производящий») и обозначает созвучное действие - произведение.

Определение 5.1. Произведение п первых последовательных натуральных чисел называется п-факториал.

Обозначение: п.

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

Например: 4! = 1 2 3 4 = 24.

Особо оговариваются частные случаи значения факториала: 0! = 1 и 1! = 1.

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

Например: (3 - 2)! = 1! = 1. Ошибочно выполнять действия в ином порядке: 3! - 2! = 1 - 2*3-1-2 = 6- 2 = 4. Как видим 4 Ф 1 и, соответственно, (3 - 2)! Ф 3! - 2!.

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

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

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

Уже не ошибки, но трудности возникают иногда, когда приходится оперировать буквенными выражениями с факториалами. В связи с этим стоит осмыслить следующий факт. Каждый сомножитель в записи значения факториалов отличается от предыдущего на единицу. Поэтому число, стоящее в таком произведении перед множителем п, имеет вид (п - 1), а перед ним стоит число вида (п - 2). Значит, при необходимости п можно записать, например, в таком виде: п = 1 2 3 ... (п - 2) (п - 1) п = (п - 2)! (п - 1) п.

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

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

Пример 5.5

В семье четыре ребенка: Аия, Боря, Ваня, Галя. Они постоянно спорят между собой за лучшее место в машине, в кино, за столом. Родители, устав от разборок, постановили, что каждый следующий раз дети садятся по-разному. Через сколько раз придется повторить рассадку?

Решение

Пока детей было двое, то возможны были только две комбинации: А - Б, Б - А.

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

Для комбинации А - Б возможны три варианта: В - А - Б, А - Б - В, А-В - Б, и для комбинации Б - Л есть еще три варианта: В - Б - Л, Б - Л - В, Б - В - Л.

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

Когда детей стало четыре, то по отношению к каждой из предыдущих (2 *3) = = 6 комбинаций четвертого ребенка можно было опять-таки разместить по бокам или на одном из двух мест между старшими тремя детьми, т.е. на одном из четырех мест. Например, для комбинации В - А - Б получится четыре новые комбинации:

Таким образом, вместо каждой из предыдущих (2 3) комбинаций получится четыре новые комбинации. Всего надо взять (2 - 3) раз по 4, что соответствует действию умножения: (2 3) 4, или можно записать 1 *2-3*4 = 4!.

Ответ : 24 раза.

Если же в описанной в примере семье появится пятый ребенок, то его можно уже будет посадить на одно из пяти мест: два но бокам и на три пропуска между старшими детьми, т.е. получится (1 *2*3* 4) *5 = 5! комбинаций и т.д.

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

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

Обозначение: Р п.

Утверждение 5.1. Число перестановок определяется по формуле Р п = п.

Теперь, после обоснования подсчета числа перестановок, естественно принять, что 0! = 1 и 1! = 1, поскольку одноэлементное и пустое множество можно представить (упорядочивай, не упорядочивай) только в одном виде.

Определение 5.3. Упорядоченные m-элементные подмножества данного множества из п элементов называются размещениями из п элементов по т.

Обозначение: А™, где п > т.

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

Пример 5.6

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

Решение

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

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

Ответ : 120 чисел.

Легко заметить, что при такой процедуре в ответе получается произведение чисел, уменьшающихся на единицу. В общем случае при выборе из п элементов это произведение выглядит так: п (п - 1) (п - 2) ... . Таких сомножителей должно быть т , по числу мест в каждой комбинации. Последний сомножитель в общем виде представить сложнее, но достаточно внимательно проанализировать полученное произведение. В каждом сомножителе вычитаемое на единицу больше, чем в предыдущем множителе. Поскольку начинается произведение фактически с вычитания нуля, а всего в произведении т разностей, то последнее уменьшаемое равно (т - 1). Так, обработав информацию при помощи нахождения сходств и различий в полученных выражениях, можно получить общий ответ о числе комбинаций при данной выборке: п (п - 1) ... [п - (т - 1)].

Утверждение 5.2. Число размещений определяется по формулам

Обоснование. В первой формуле расписаны «почти 77!», но без первых сомножителей из (77-777)!. Во второй формуле из факториала убраны первые сомножители из (77-777)! при помощи деления.

Замечание. Л" = Р п, если 77 = 777.

Если не повторять каждый раз все рассуждения, а пользоваться готовой формулой (5.1), то решение примера 5.6 выглядит так: число элементов в исходном множестве п = 6, /7? = 3, упорядоченность записи элементов в подмножестве - важна. Тогда

Рассмотрим другую, но очень похожую задачу: сколько различных произведений из трех различных множителей можно составить, взяв в качестве множителей числа 1, 2, 3, 4, 5, 7?

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

Определение 5.4. Неупорядоченное т/7-элементное подмножество данного множества из п элементов называется сочетанием из п элементов

ПО 777.

Обозначение: С" 7 , где п > т.

Утверждение 5.3. Число сочетаний определяется по формуле

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

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

  • наличие совпадения числа элементов в множестве и числа элементов в подмножестве;
  • отличие подмножеств друг от друга по порядку записи элементов.

Теперь можно организовать выбор математической модели - формулы - для подсчета числа комбинаций в виде таблицы (табл. 5.2).

Таблица 5.2

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

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

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

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

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

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

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

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

Пример 5.7

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

Решение

Этап 1. Краткая словесная (вербальная) обработка: например, «выбрать три студента из десяти студентов».

Этап 2. Полная запись условия на языке математических символов.

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

Дано: п =...; т =...;

порядок: да /нет.

Для примера 5.8 эта заготовка заполнится следующим образом:

Дано: п = 10; т = 3;

порядок: нет.

На основе этой заготовки и табл. 5.2 выбор необходимой для решения задачи математической модели выполняется легко.

Поскольку в данном условии число элементов в множестве и подмножестве нс равны (/? Ф т ), то на два вопроса таблицы ответы: «нет - нет». В соответствующей строке таблицы находится формула для подсчета числа сочетаний из п элементов по т. Таким образом, запись решения задачи в целом будет выглядеть так:

«Выбрать три студента из десяти студентов».

Дано: п - 10; т = 3;

порядок: нет.

Ответ: 120 комбинаций надо рассмотреть, чтобы сделать полный перебор вариантов.

Для более продвинутых пользователей табл. 5.2 можно расширить, добавив еще один параметр - повторное использование элементов в подмножестве (табл. 5.3).

Таблица 53

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

Комбинации

Подмножества могут отличаться но порядку

элементов?

Возможно повторное использование элементов в подмножествах?

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

Р п = п

Размещения

а;:,=

Сочетания

ш (п-т)т!

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

А„ = и""

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

W _ (//2-1-/7-1)! " ~т!-(л- 1)!

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

k Jповторов

  • 1- го элемента, k 2 повторов
  • 2- го элемента,

k n повторов /7-го элемента.

Pn(k t,&2,= п

V- k 2 ! *„!

Принцип выбора математической модели по табл. 5.3 аналогичен показанному в примере 5.7. Некоторые затруднения могут возникнуть с конкретизацией формулы для подсчета числа перестановок с повторениями. Поэтому рассмотрим подробнее пример ее использования.

Пример 5.8

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

Решение

Этап 1: «Выбрать шесть букв из шести букв».

Дано: п = 6; т = 6;

порядок: да;

повтор: да, к а = 3, к г = 2, k ? = 1

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

Ответ : 60.

Вид формулы для подсчета числа перестановок с повторениями легко обосновать. Если бы все шесть букв были разные, то количество перестановок равнялось бы 6!. Но если в подмножествах могут фигурировать, например, три одинаковые буквы, то неважно, какая из этих одинаковых букв на каком месте, отведенном для этих букв, находится. А это значит, что количество перестановок с повторениями будет меньше количества бес- повторных перестановок во столько раз, сколько перестановок одинаковых элементов можно сделать, т.е. в /^-факториал раз. Поэтому в формуле числа перестановок с повторениями появился знаменатель в отличие от формулы бесповторных перестановок.

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

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

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

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

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

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