Рассмотрим множество А = {а1, а2,..., аn},
содержащее n различных элементов, которое будем называть n-множеством
или генеральной совокупностью объема n. Из n-множества можно образовать его части (подмножества).
Определение. Подмножество, состоящее из m элементов n-множества, называют m-подмножеством n-множества или со-
единением из n элементов по m, или выборкой объема m из генеральной совокупности объема n.
Возможны два способа выбора:
1. Выбор без возвращения,
при котором однажды выбранный элемент удаляется из генеральной совокупности. Выборка
(соединение) в этом случае не содержит повторяющихся элементов.
2. Выбор с возвращением,
при котором выбор производится каждый раз из всей генеральной совокупности, то есть перед
следующим выбором предыдущий выбранный элемент возвращается в генеральную совокупность. В выборке (соединении) в
этом случае встречаются повторения.
Какие выборки одного и того же объема считать различными и какие одинаковыми, зависит от правил выбора соедине-
ния (подмножества, выборки).
Два соединения могут отличаться либо 1) составом, если они содержат хотя бы по одному различному элементу, либо
2) порядком входящих элементов.
В зависимости от правил выбора соединения делят на три типа: размещения, перестановки, сочетания. В зависимости от
способа выбора (без возвращения или с возвращением) каждый тип соединения может быть без повторений или с повторениями.
2. Размещения без и с повторениями.
Классической задачей комбинаторики является задача о числе размещений без повторений,
содержание которой можно
выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?
Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой
можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n предметов,
среди которых есть одинаковые?
Определение. Размещениями из n элементов по m называются соединения из n элементов по m, которые отличаются
друг от друга либо своими элементами (составом), либо порядком их расположения.
На языке теории множеств это звучит следующим образом: размещения из n элементов по m – это упорядоченное
m-подмножество n-множества (упорядоченная m-выборка из генеральной совокупности объема n). Термин «упорядоченная»
означает, что порядок следования элементов в выборке существенен: выборки с одними и теми же элементами, но с разным
порядком их следования различны.
Задача
. Пусть имеется множество, содержащее 4 буквы:
{А, B, C, D}. Записать все возможные размещения из 4 указанных букв по две:
а) без повторений;
б) с повторениями.
Решение.
а) Таких размещений 12: (АВ), (AC), (АD), (ВС),(ВD), (BA), (CA), (CB), (СD), (DА), (DВ), (DС). Заметим, что
размещения отличаются порядком входящих в них элементов и их составом. Размещения АВ и ВА содержат одинаковые буквы,
но порядок их расположения различен.
б) Таких размещений 16. К приведенным для случая (а)
размещениям добавляются размещения из одинаковых элементов (АА), (BB), (CC), (DD).
Задача
. Пусть имеется множество, содержащее 2 буквы:{A, B}. Записать все возможные размещения с повторениями из
4-х букв.
Решение. Таких размещений 16: (AAAA), (BBBB), (AAAB),(AABA), (ABAA), (BAAA), (AABB), (ABAB), (BABA), (BBAA), (ABBA),
(BAAB), (BBBA), (BBAB), (BABB), (ABBB).
Теорема 3. 3.1 Число различных размещений без повторений из n элементов по m равно
для выборки без возвращения.
3.2 Число размещений с повторениями из n элементов по m равноm (2) для выборки с возвращением.
Доказательство. Для доказательства воспользуемся пра- вилом умножения.
Рассмотрим выборки без возвращения. Для выбора первого элемента имеется n возможностей, второго – (n – 1)
(перед вторым выбором в генеральной совокупности ос- талось (n –1) элементов),..., при m-ом выборе (n – m + 1) воз- можностей.
Таким образом, по правилу умножения
Запишем выражение в более удобном виде, умножив и разделив его на (m – n)!
Считается, что 0! = 1, что позволяет использовать эту формулу для случая m = n.
Рассмотрим выборки с возвращением
. Для выбора первого элемента имеется n возможностей, второго – тоже n (перед выбо-
ром очередного элемента предыдущий выбранный элемент зафиксирован и возвращен в генеральную совокупность), при m-м вы-
боре тоже n возможностей. Таким образом .
Задача . В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии.
Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?
Решение
. В данной задаче генеральной совокупностью являются 12 страниц газеты, и выборкой без возвращения 4 выбранные из них страницы для фотографий. В данной задаче важно не только то, какие выбраны страницы, но и в каком порядке (для расположения фотографий). Таким образом, задача сводится к классической задаче об определении числа размещений без повторений из 12 элементов по 4 элемента:
Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.
Задача
. У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих
штампов нанести на все книги пятизначные номера – составить каталог. Сколько различных пятизначных номеров может со-
ставить мальчик?
Решение. Можно считать, что опыт состоит в 5-кратном выборе с возращением одной из 3 цифр {1, 3, 7}. Таким образом, число пятизначных номеров определяется числом размещений с повторениями из 3 элементов по 5:
3. Перестановки без повторений
Классической задачей комбинаторики является задача о числе перестановок без повторения, содержание которой можно
выразить вопросом: сколькими способами можно разместить n различных предметов на n различных местах?
Определение. Размещения, в которых участвуют все n элементов генеральной совокупности, называются перестанов-
ками без повторений из n элементов. Перестановки состоят из одних и тех же элементов, но отличаются между собой порядком.
Задача
. Пусть имеется множество букв {A, B, C}. Записать все возможные перестановки.
Решение. Этому множеству букв соответствует 6 перестановок: (АВС), (ACB), (BAC), (BCA), (CBA), (CAB).
Теорема . Число перестановок n различных элементов равно n!, т. е. Рn = n!
Доказательство. Так как перестановки являются частным случаем размещений, то при n = m получаем
Замечание. При больших n для подсчета факториала исполь- зуют таблицу логарифмов факториалов либо приближенную формулу Стирлинга
Задача . Сколько можно составить четырехбуквенных «слов» из букв слова «брак»?
Решение . Генеральной совокупностью являются 4 буквы слова «брак» {б, р, а, к}.
Число «слов» определяется перестановками этих 4 букв, т. е. Р4 = 4! = 1 x 2 x 3 x 4 = 24.
Задача . Сколькими способами можно расставить девять различных книг на полке, чтобы определенные четыре книги стояли рядом?
Решение . В исходной генеральной совокупности – 9 разных книг.
Тогда для остальных 6 книг существует Р6 = 6! = 720 перестановок.
Однако четыре определенные книги можно переставить между собой Р4 = 4! = 24 способами.
По правилу умножения имеем Р6 x Р4 = 720 x 24 = 17280.
4. Перестановки с повторениями
Для случая, когда среди выбираемых n элементов есть одинаковые (выборка с возвращением), задачу о числе перестановок с повторениями можно выразить вопросом: сколькими способами можно переставить n предметов, расположенных на
n различных местах, если среди n предметов имеются k различных типов (k < n), т. е. есть одинаковые предметы.
Определение. Перестановками с повторениями называются соединения из генеральной совокупности, каждое из которых содержит n элементов, среди которых элемент
а1 повторяется n1 раз,
а2 повторяется n2 раз,
. . . . . . . . . . . . . . . . . . .
аn повторяется nk раз
n1 + n2 + ... + nk = n
и которые отличаются друг от друга только порядком расположения различных элементов.
Теорема. Число перестановок с повторениями
Доказательство. Доказательство очевидно, так как перестановки одинаковых элементов в перестановке с повторениями не дают новой перестановки.
Задача .
Сколько разных буквосочетаний можно сделать из букв слова «Миссисипи»?
Решение. Здесь 1 буква «м», 4 буквы «и», 3 буквы «c» и 1 буква «п», всего 9 букв.
Следовательно, число перестановок с повторениями равно
5. Сочетания без повторений
Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из п различных предметов?
Определение. Сочетаниями из n различных элементов по m называются соединения из n элементов по m (m <=n), которые
отличаются друг от друга только составом элементов.
Задача. Пусть имеется множество, содержащее 4 буквы {A, B, C, D}. Запишем все возможные сочетания из указанных
букв по 3.
Решение. Таких сочетаний 4: ABC, ACD, ABD, BCD.
Здесь в число сочетаний не включены, например, АСВ,ВСА, так как они не отличаются по составу от последовательно-
сти букв АВС, потому что перестановка элементов нового сочетания не дает.
Теорема. Число сочетаний из n элементов по m равно
Доказательство.
Вспомним, что и сочетания, и размещения из n элементов по m – это выборки объема m из генеральной совокупности объема n и разница между ними в том, что в случае размещений важен и состав, и порядок элементов, тогда как в случае сочетаний важен только состав элементов. Пусть имеется какое-то одно сочетание. Для того, чтобы образовать все размещения с такими же элементами, нужно осуществить всевозможные перестановки элементов этого сочетания. Поскольку в сочетании m элементов, то существует m! перестановок. Следовательно, одному сочетанию, состоящему из m элементов, соответствует m! размещений с этими элементами. Поэтому
Числа называются биномиальными коэффициентами: они являются коэффициентами в разложении бинома Ньютона
Задача . Необходимо выбрать в подарок 4 из 10 имеющих- ся различных книг. Сколькими способами можно это сделать?
Решение . Генеральной совокупностью является 10 раз- личных книг. Из них нужно выбрать 4, причем порядок выбора книг не играет роли. Нужно найти число сочетаний из 10 элементов по
Задача . Имеется 10 белых и 5 черных шаров. Сколькими способами можно выбрать 7 шаров, чтобы среди них были 3 черных?
Решение . Имеем 15 шаров: 10 белых и 5 черных. Нужно выбрать 7 шаров: 4 белых и 3 черных.
Разобьем 15 шаров на 2 генеральные совокупности:
1) 10 белых шаров;
2) 5 черных шаров.
4 белых шара будем выбирать из I генеральной совокупности, порядок выбора безразличен, их можно выбрать
Способами. 3 черных шара будем выбирать из II генеральной совокупности, их можно выбрать
Способами.
Тогда по правилу умножения искомое число способов равно .
Решение этой задачи можно схематически представить следующим образом
Задача . Десять команд участвуют в розыгрыше первенства по футболу, лучшие из которых занимают 1-е, 2-е и 3-е место.
Две команды, занявшие последние места, не будут участвовать в следующем таком же первенстве.
Сколько разных вариантов результата первенства может быть, если учитывать только положение первых трех и последних двух команд.
Решение . Имеется генеральная совокупность объема 10 команд. Из нее будем выбирать 5 команд в 2 этапа:
1) сначала на первые 3 места из 10 с учетом состава и порядка команд;
2) затем на последние 2 места из оставшихся 7 с учетом только состава (порядок выбывших команд не важен).
Первые 3 места могут быть распределены способами.
Число способов исключить 2 команды из оставшихся 7 равно .
Согласно правилу умножения получаем, что число разных результатов неравенства равно 0.
Задача .
Сколько существует вариантов опроса 11 учащихся на одном занятии, если ни одни из них не будет подверг нут опросу дважды и на занятии может быть опрошено любое количество учащихся, причем порядок, в котором опрашивают- ся учащиеся, безразличен?
Решение .
I способ. Имеется генеральная совокупность объема 11 учащихся. Преподаватель может не опросить ни одного из 11 учащихся, что является одним из вариантов. Этому случаю соответствует . Преподаватель может опросить только одного из учащихся, таких вариантов .
Если преподаватель опросит двух учащихся, то число вариантов опроса . Для опроса трех учащихся существует вариантов и т. д.
Наконец, могут быть опрошены все учащиеся. Число вариантов в этом случае .
Число всех возможных вариантов опроса можно найти по пра- вилу сложения
Решение этой задачи можно схематически представить следующим образом:
II способ. Имеется генеральная совокупность, состоящая из 2 элементов:
{а, в}, где а – ученик опрошен, в – ученик не опрошен на данном занятии.
Опыт состоит в 11-кратном выборе с возвращением одного из элементов этого множества – каждый из 11 учеников либо опрошен, либо не опрошен.
В данной задаче важно не только то, какие выбраны элементы множества (сколько учеников опрошено и сколько нет),
но и в каком порядке (т. е. какой именно ученик опрошен или нет).
Число способов такого выбора определяется числом размещений с повторениями из 2 элементов по 11; .
6. Сочетания с повторениями
Рассмотрим задачу о числе сочетаний с повторениями:
имеется по r одинаковых предметов каждого из n различных типов;
сколькими способами можно выбрать m (m <= r) из этих (n x r) предметов?
Определение . Сочетаниями с повторениями называются соединения из n элементов по m (выбор с возвращением m элементов), которые отличаются только составом и при этом отдельные соединения могут содержать повторяющиеся элементы.
Задача
. Имеются 2 буквы А, 2 буквы В, 2 буквы С. Сколькими способами можно выбрать две из этих шести букв?
Решение. Существует 6 способов выбора 2 букв из 6 с повторениями: (АА), (AB), (AC), (BC), (BB), (CC). Порядок следо-
вания букв не учитывается.
Теорема . Число сочетаний с повторениями равно
Доказательство. Пусть имеются предметы n различных типов. Сколько соединений по m элементов можно из них сделать, если не принимать во внимание порядок элементов. Расположим в каждом сочетании элементы по типам (сначала все элементы 1-го типа, потом 2-го и т. д.). После этого перенумеруем все элементы в сочетании, но к номерам элементов второ- го типа прибавим 1, третьего типа – 2 и т. д. Тогда из каждого сочетания с повторениями получится сочетание без повторений, состоящее из чисел 1, 2,..., n + m – 1, причем в каждое сочетание входит m элементов.
Отсюда следует, что
Задача . В технической библиотеке имеются книги по ма- тематике, физике, химии и т. д., всего по 16 разделам науки.
Поступили очередные 4 заказа на литературу. Сколько сущест- вует вариантов такого заказа?
Решение. Так как 4 заказанные книги могут быть и из одно- го раздела науки, и из разных разделов, при этом порядок выбора разделов не важен, то число вариантов заказа определяется чис- лом сочетаний с повторениями из 16 элементов по 4, т. е.
Задача . В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?
Решение . Очевидно, что порядок, в котором выбираются пирожные, не существен, причем в комбинации могут входить повторяющиеся элементы (например, можно купить 7 эклеров). Следовательно, число способов покупки 7 пирожных определяется числом сочетаний с повторениями из 4 элементов по 7, т. е
Рассмотрим в этом классе задач две следующие задачи:
1. Даны n различных предметов и k различных групп. Сколькими способами можно распределить n различных предметов по k различным группам, если допускаются пустые группы. Ниже покажем, что число способов равно k^n .
2. Даны n различных предметов и k различных групп. Сколькими способами можно распределить n различных пред- метов по k группам, если в первой группе n1 предметов, во второй – n2 , в k-й – nk , где n1 + n2 +... + nk = n . Ниже покажем, что число способов равно
Рассмотрим решение первой задачи. Пусть генеральной совокупностью будет k различных групп {1, 2,..., k}. Можно считать, что опыт состоит в n-кратном выборе с возвращением номера группы для каждого предмета. Заметим, что поскольку предметы разные, то важно не только, какие группы выбираются для предметов, но и в каком порядке выбираются эти группы. Таким образом, число способов раз- бить n различных предметов на k групп определяется числом размещений с повторениями и k элементов по n:
Рассмотрим решение второй задачи.
Разбиение n предметов по k группам можно выполнить следующим образом. Сначала положим все n предметов в ряд. После этого возьмем первые n1 предметов и поместим их в первую группу, вторые n2 предмета – во вторую группу, ..., последние nk предметов в k-ю группу. Ясно, что меняя положение предметов в ряду, можно получить всевозможные разбиения предметов. Так как число перестановок из n элементов равно n!, то число расположения предметов в ряд равно n! При этом заметим, что любая перестановка первых n1 предметов ничего не меняет, так же как и вторых n2, ..., и последних nk. В силу правила произведения получим n1!n2!...nk! перестановок предметов, не меняющих результата раздела. Таким образом, число способов разбиения на группы равно
Формула совпадает с формулой для числа перестановок с повторениями. К этому же результату можно прийти иначе. Первые n1 предметов выбираем из n предметов. Так как порядок выбранных предметов безразличен, то имеет выборов. После этого следующие n2 предмета выбираем из оставшихся n – n1. Это можно сделать способами, и т. д.
Наконец, последние nk предметов выбираем из оставшихся nk. Это можно сделать , т. е. единственным способом. По правилу произведения получаем, что число способов разбиения на группы равно
Как видим, задачи о разбиениях привели к уже известным формулам комбинаторики.
Задача. 7 одинаковых шариков случайным образом рас- сыпаются по 4 лункам (в одну лунку может поместиться любое число шаров). Сколько существует различных способов распре- деления 7 шариков по 4 лункам?
Решение. Мы имеем 7 шариков, которые распределяем по 4 лункам (лунки могут быть пустые), т. е. это соответствует первой задаче о разбиениях, число способов равно 4^7 = 16348
Задача. При игре в домино 4 игрока делят поровну 28 костей. Сколькими способами они могут это сделать?
Решение. Это задача о разделе 28 костей между 4 игрока- ми по 7 костей. Используя полученную выше формулу для числа способов такого раздела (задача 2), имеем
8. Рекомендации по решению задач
Решение комбинаторных задач представляет известную трудность для начинающих. Причин много, но одна из них очевидна – при изложении комбинаторики используется своя специфическая терминология (генеральная совокупность, выборка, правила выбора). В задаче же этих терминов, как правило, нет –сформулирована она на обычном литературном языке и комби-
наторные понятия присутствуют в ней в неявной форме. Поэтому после усвоения содержания задачи нужно ее «перевести»
на математический язык.
Для этого необходимо выяснить,
1) что является генеральной совокупностью - она всегда будет присутствовать в задаче, т. е. комбинаторные задачи свя-
заны с выбором объектов, а этот выбор из чего-то (генеральной совокупности) производится; каков объем генеральной сово-
купности;
2) одна или несколько генеральных совокупностей;
3) что является выборкой и каков объем выборки;
4) правила выбора: допустимы или нет повторы, важен ли порядок выбираемых элементов, возможно ли изменение состава.
После этого полезно для себя переформулировать задачу на языке генеральных совокупностей и выборок. В зависимости
от ситуации выбрать нужную формулу (см. таблицу). Иногда в более сложных задачах приходится использовать совместно не-
сколько формул.
В заключение приведем основные свойства чисел .
Прежде всего, построим таблицу таких чисел, используя формулу (3.11).
Таблица чисел имеет треугольную форму и называется треугольником Паскаля по имени математика Блеза Паскаля (1623-1662). Анализируя треугольник Паскаля, легко видеть основные свойства чисел .
Свойства 1 – 2 вытекают из определения сочетания как подмножества, содержащего m элементов множества, имеющего n элементов.
Свойства 3 – 5 доказываются методом математической индукции.
В силу свойства 4 треугольник Паскаля легко продолжить вниз на любое число шагов.
рис 3.2 схема определения вида расстановок и выбора формул
Комбинаторикой называется раздел математики, изучающий вопрос о том, сколько комбинаций определенного типа можно составить из данных предметов (элементов).
Правило умножения (основная формула комбинаторики)
Общее число способов, которыми можно выбрать по одному элементу из каждой группы и расставить их в определенном порядке (то есть получить упорядоченную совокупность ), равно:
Пример 1
Монету подбросили 3 раза. Сколько различных результатов бросаний можно ожидать?
Решение
Первая монета имеет альтернативы – либо орел, либо решка. Для второй монеты также есть альтернативы и т.д., т.е. .
Искомое количество способов:
Правило сложения
Если любые две группы и не имеют общих элементов, то выбор одного элемента или из , или из , …или из можно осуществить способами.
Пример 2
На полке 30 книг, из них 20 математических, 6 технических и 4 экономических. Сколько существует способов выбора одной математической или одной экономической книги.
Решение
Математическая книга может быть выбрана способами, экономическая - способами.
По правилу суммы существует способа выбора математической или экономической книги.
Размещения – это упорядоченные совокупности элементов, отличающиеся друг от друга либо составом, либо порядком элементов.
Размещения без повторений , когда отобранный элемент перед отбором следующего не возвращается в генеральную совокупность. Такой выбор называется последовательным выбором без возвращения, а его результат – размещением без повторений из элементов по .
Число различных способов, которыми можно произвести последовательный выбор без возвращения элементов из генеральной совокупности объема , равно:
Пример 3
Расписание дня состоит из 5 различных уроков. Определите число вариантов расписания при выборе из 11 дисциплин.
Решение
Каждый вариант расписания представляет набор 5 дисциплин из 11, отличающихся от других вариантов как составом, так и порядком следования. поэтому:
Перестановки – это упорядоченные совокупности, отличающиеся друг от друга только порядком элементов. Число всех перестановок множества из элементов равно
Пример 4
Сколькими способами можно рассадить 4 человек за одним столом?
Решение
Каждый вариант рассадки отличается только порядком участников, то есть является перестановкой из 4 элементов:
Размещения с повторениями , когда отобранный элемент перед отбором следующего возвращается в генеральную совокупность. Такой выбор называется последовательным выбором с возвращением, а его результат - размещением с повторениями из элементов по .
Общее число различных способов, которыми можно произвести выбор с возвращением элементов из генеральной совокупности объема , равно
Пример 5
Лифт останавливается на 7 этажах. Сколькими способами могут выйти на этих этажах 6 пассажиров, находящихся в кабине лифта?
Чтобы решение задачи по теории вероятностей было максимально точным и верным, многие недорого заказывают контрольную работу на этом сайте. Подробно (как оставить заявку, цены, сроки, способы оплаты) можно почитать на странице Купить контрольную работу по теории вероятностей...
Решение
Каждый из способов распределения пассажиров по этажам представляет собой комбинацию 6 пассажиров по 7 этажам, отличающуюся от других комбинаций как составом, так и их порядком. Так как одном этаже может выйти как один, так и несколько пассажиров, то одни и те же пассажиры могут повторяться. Поэтому число таких комбинаций равно числу размещений с повторениями из 7 элементов по 6:
Сочетаниями из n элементов по k называются неупорядоченные совокупности, отличающиеся друг от друга хотя бы одним элементом.
Пусть из генеральной совокупности берется сразу несколько элементов (либо элементы берут последовательно, но порядок их появления не учитывается). В результате такого одновременного неупорядоченного выбора элементов из генеральной совокупности объема получаются комбинации, которые называются сочетаниями без повторений из элементов по .
Число сочетаний из элементов по равно:
Пример 6
В ящике 9 яблок. Сколькими способами можно выбрать 3 яблока из ящика?
Решение
Каждый вариант выбора состоит из 3 яблок и отличается от других только составом, то есть представляет собой сочетания без повторений из 9 элементов:
Количество способов, которыми можно выбрать 3 яблока из 9:
Пусть из генеральной совокупности объема выбирается элементов, один за другим, причем каждый отобранный элемент перед отбором следующего возвращается в генеральную совокупность. При этом ведется запись, какие элементы появились и сколько раз, однако порядок их появления не учитывается. Получившиеся совокупности называются сочетаниями с повторениями из элементов по .
Число сочетаний с повторениями из элементов по :
Пример 7
На почте продают открытки 3 видов. Сколькими способами можно купить 6 открыток?
Это задача на отыскание числа сочетаний с повторениями из 3 по 6:
Пусть множество из различных элементов разбивается на групп так, то в первую группу попадают элементов, во вторую - элементов, в -ю группу - элементов, причем . Такую ситуацию называют разбиением множества на группы.
Число разбиений на групп, когда в первую попадают элементов, во вторую - элементов, в k-ю группу - элементов, равно:
Пример 8
Группу из 16 человек требуется разбить на три подгруппы, в первой из которых должно быть 5 человек, во второй – 7 человек, в третьей – 4 человека. Сколькими способами это можно сделать?
Решение
Здесь
Число разбиений на 3 подгруппы:
Посвященный решению задач выбора и расположения элементов некоторого, обычно конечного, множества в соответствии с заданными правилами. Например, сколькими способами можно выбрать 6 карт из колоды, состоящей из 36 карт, или сколькими способами можно составить очередь, состоящей из10 человек и т.д. Каждое правило в комбинаторике определяет способ построения некоторой конструкции, составленной из элементов исходного множества и называемой комбинацией . Основная цель комбинаторики состоит в подсчете количества комбинаций, которые можно составить из элементов исходного множества в соответствии с заданным правилом. Простейшими примерами комбинаторных конструкций являются перестановки, размещения и сочетания.
Рождение комбинаторики связано с работами Б. Паскаля и П. Ферма по поводу азартных игр, большой вклад внесли Лейбниц, Бернулли, Эйлер. В настоящее время интерес к комбинаторике связан с развитием компьютеров. Нас в комбинаторике будет интересовать возможность определения количественно различных подмножеств конечных множеств для вычисления вероятности классическим способом.
Для определения мощности множества, которое соответствует тому или иному событию, полезно разобраться с двумя правилами комбинаторики: правило произведения и правило суммы (иногда их называют принципами умножения и сложения соответственно).
Правило nроизведения: пусть из некоторого конечного множества
1-й объект можно выбрать k 1 способами,
2-ой объект - k 2 способами,
n -ый объект - k n способами. (1.1)
Тогда произвольный набор, перечисленных n объектов из данного множества можно выбрать k 1 , k 2 , …, k n способами.
Пример 1. Сколько существует трехзначных чисел с разными цифрами?
Решение . В десятичной системе исчисления десять цифр: 0,1,2,3,4,5,6,7,8,9. На первом месте может стоять любая из девяти цифр (кроме нуля). На втором месте - любая из оставшихся 9 цифр, кроме выбранной. На последнем месте любая из оставшихся 8 цифр.
По правилу произведения 9·9·8 = 648 трёхзначных чисел имеют разные цифры.
Пример 2. Из пункта в пункт ведут 3 дороги, а из пункта в пункт - 4 дороги. Сколькими способами можно совершить поездку из в через ?
Решение . В пункте есть 3 способа выбора дороги в пункт , а в пункте есть 4 способа попасть в пункт . Согласно принципу умножения, существует 3×4 = 12 способов попасть из пункта в пункт .
Правило суммы: при выполнении условий (1.1), любой из объектов можно выбрать k 1 +k 2 +…+k n способами.
Пример 3. Сколько существует способов выбора одного карандаша из коробки, содержащей 5 красных, 7 синих, 3 зеленых карандаша.
Решение . Один карандаш, по правилу суммы, можно выбрать 5+7+3 = 15 способами.
Пример 4. Пусть из города в город можно добраться одним авиамаршрутом, двумя железнодорожными маршрутами и тремя автобусными маршрутами. Сколькими способами можно добраться из города в город ?
Решение . Все условия принципа сложения здесь выполнены, поэтому, в соответствии с этим принципом, получим 1+2+3 = 6 способов.
Рассмотрим пример, иллюстрирующий различие принципов умножения и сложения.
Пример 5. В магазине электроники продаются три марки телевизоров и два вида видеомагнитофонов. У покупателя есть возможности приобрести либо телевизор, либо видеомагнитофон. Сколькими способами он может совершить одну покупку? Сколько различных комплектов, содержащих телевизор и магнитофон, можно приобрести в этом магазине, если покупатель собирается приобрести в паре и телевизор, и видеомагнитофон?
Решение . Один телевизор можно выбрать тремя способами, а магнитофон - другими двумя способами. Тогда телевизор или магнитофон можно купить 3+2=5 способами.
Во втором случае один телевизор можно выбрать тремя способами, после этого видеомагнитофон можно выбрать двумя способами. Следовательно, в силу принципа умножения, купить телевизор и видеомагнитофон можно 3×2 = 6 способами.
Рассмотрим теперь примеры, в которых применяются оба правила комбинаторики: и принцип умножения, и принцип сложения.
Пример 6. В корзине лежат 12 яблок и 10 апельсинов. Ваня выбирает либо яблоко, либо апельсин. После чего Надя выбирает из оставшихся фруктов и яблоко и апельсин. Сколько возможно таких выборов?
Решение . Ваня может выбрать яблоко 12 способами, апельсин - 10 способами. Если Ваня выбирает яблоко, то Надя может выбрать яблоко 11 способами, а апельсин - 10 способами. Если Ваня выбирает апельсин, то Надя может выбрать яблоко 12 способами, а апельсин - 9 способами. Таким образом, Ваня и Надя могут сделать свой выбор способами.
Пример 7. Есть 3 письма, каждое из которых можно послать по 6 адресам. Сколькими способами это можно сделать?
Решение . В данной задаче мы должны рассмотреть три случая:
а) все письма рассылаются по разным адресам;
б) все письма посылаются по одному адресу;
в) только два письма посылаются по одному адресу.
Если все письма рассылаются по разным адресам, то число таких способов легко находится из принципа умножения: n 1 = 6×5×4 = 120 способов. Если все письма посылаются по одному адресу, то таких способов будет n 2 = 6. Таким образом, остается рассмотреть только третий случай, когда только 2 письма посылаются по одному адресу. Выбрать какое-либо письмо мы можем 3 способами, и послать его по какому-либо выбранному адресу можем 6 способами. Оставшиеся два письма мы можем послать по оставшимся адресам 5 способами. Следовательно, послать только два письма по одному адресу мы можем n 3 =3×6×5=90 способами. Таким образом, разослать 3 письма по 6 адресам в соответствие с принципом сложения можно
способами.
Обычно в комбинаторике рассматривается идеализированный эксперимент по выбору наудачу k элементов из n . При этом элементы: а) не возвращаются обратно (схема выбора без возвращений); б) возвращаются обратно (схема выбора с возвращением).
1. Схема выбора без возвращений
Размещением из n элементов по k называют любой упорядоченный набор из k элементов, принадлежащих n - элементному множеству. Различные размещения отличны друг от друга или порядком элементов, или составом.
Число размещений из n элементов по k обозначается и вычисляется по формуле
(1.2)
где n ! = 1×2×3×…×n , 1! = 1, 0! = 1.
Пример 8. В соревнованиях участвует 10 человек, трое из них займут 1, 2, 3 место. Сколько существует различных вариантов?
Решение . В этом случае важен порядок распределения мест. Число различных вариантов равно
Перестановкой из n элементов называют размещение из n элементов по n. Число перестановок из n элементов обозначают P n и вычисляют по формуле
(1.3)
Пример 9. Сколько существует способов расстановки 10 книг на полке?
Решение . Общее число способов расстановки определяется как число перестановок (1.3) из 10 элементов и равно Р 10 = 10! = 3628 800.
2. Схема выбора с возвращениями
Если при выборе k элементов из n , элементы возвращаются обратно и упорядочиваются, то говорят, что это размещения с nовторениями .
Число размещений с повторениями:
Пример 11. В гостинице 10 комнат, каждая из которых может разместить четырех человек. Сколько существует вариантов размещения, прибывших четырех гостей?
Решение . Каждый следующий гость из 4 может быть помещён в любую из 10 комнат, так как рассматривается идеализированный опыт, поэтому общее число размещений, по формуле размещений с повторениями (1.5), равно
.
Если при выборе k элементов из n элементы возвращаются обратно без последующего упорядочивания, то говорят, что это сочетания с nовторениями. Число сочетаний с повторениями из n элементов по k определяется:
Пример 12. В магазине продается 10 видов тортов. Очередной покупатель выбил чек на три торта. Считая, что любой набор товаров равновозможен, определить число возможных заказов.
Решение . Число равновозможных заказов по формуле (1.6) равно
.
План:
1. Элементы комбинаторики.
2. Общие правила комбинаторики.
4. Применение графов (схем) при решении комбинаторных задач.
1. Комбинаторика и ее возникновение.Комбинаторика - это область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из элементов, принадлежащих данному множеству.
Комбинаторика возникла в XVI веке. В жизни привилегированных слоев тогдашнего общества большое место занимали азартные игры (карты, кости). Широко были распространены лотереи. Первоначально комбинаторные задачи касались в основном азартных игр: сколькими способами можно получить данное число очков, бросая 2 или 3 кости или сколькими способами можно получить 2-ух королей в некоторой карточной игре. Эти и другие проблемы азартных игр являлись движущей силой в развитии комбинаторики и далее в развитии теории вероятностей.
Одним из первых занялся подсчетом числа различных комбинаций при игре в кости итальянский математик Тарталья. Он составил таблицы (числа способов выпадения k очков на r костях). Однако, он не учел, одна и та же сумма очков может выпасть различными способами, поэтому его таблицы содержали большое количество ошибок.
Теоретическое исследование вопросов комбинаторики предприняли в XVII веке французские математики Блез Паскаль и Ферма. Исходным пунктом их исследований были так же проблемы азартных игр.
Дальнейшее развитие комбинаторики связано с именами Я. Бернулли, Г. Лейбница, Л. Эйлера. Однако, и в их работах основную роль играли приложения к различным играм.
Сегодня комбинаторные методы используются для решения транспортных задач, в частности задач по составлению расписаний, для составления планов производства и реализации продукции и т.д.
2. Общие правила комбинаторики.Правило суммы: Если некоторый объект А может быть выбран m способами, а объект В- k способами, то объект «либо А, либо В» можно выбрать m +k способами.
Примеры:
1. Допустим, что в ящике находится n разноцветных шаров. Произвольным образом вынимается 1 шарик. Сколькими способами это можно сделать?
Ответ: n способами.
Распределим эти n шариков по двум ящикам: в первый- m шариков, во второй- k шариков. Произвольным образом из произвольно выбранного ящика вынимается 1 шарик. Сколькими способами это можно сделать?
Решение: Из первого ящика шарик можно вынуть m способами, из второго- k способами. Тогда всего способов m+k=n .
2. Морской семафор.В морском семафоре каждой букве алфавита соответствует определенное положение относительно тела сигнальщика двух флажков. Сколько таких сигналов может быть?
Решение: Общее число складывается из положений, когда оба флажка расположены по разные стороны от тела сигнальщика и положений, когда они расположены по одну сторону от тела сигнальщика. При подсчете числа возможных положений применяется правило суммы.
Правило произведения: Если объект А можно выбрать m способами, а после каждого такого выбора другой объект В можно выбрать (независимо от выбора объекта А) k способами, то пары объектов «А и В» можно выбрать m *k способами.
Примеры:
1. Сколько двузначных чисел существует?Решение: Число десятков может быть обозначено любой цифрой от 1 до 9. Число единиц может быть обозначено любой цифрой от 0 до 9. Если число десятков равно 1, то число единиц может быть любым (от 0 до 9). Таким образом, существует 10 двузначных чисел, с числом десятков- 1.Аналогично рассуждаем и для любого другого числа десятков. Тогда можно посчитать, что существует 9 *10 = 90 двузначных чисел.
2. Имеется 2 ящика. В одном лежит m разноцветных кубиков, а в другом- k разноцветных шариков. Сколькими способами можно выбрать пару «Кубик-шарик»?
Решение: Выбор шарика не зависит от выбора кубика, и наоборот. Поэтому, число способов, которыми можно выбрать данную пару равно m *k .
3. Генеральная совокупность без повторений и выборки без повторений.Генеральная совокупность без повторений - это набор некоторого конечного числа различных элементов a 1 , a 2 , a 3 , ..., a n .
Пример: Набор из n разноцветных лоскутков.
Выборкой объема k (k n ) называется группа из m элементов данной генеральной совокупности.
Пример: Пестрая лента, сшитая из m разноцветных лоскутков, выбранных из данных n .
Размещениями из n элементов по k называются такие выборки, которые содержат по k элементов, выбранных из числа данных n элементов генеральной совокупности без повторений, и отличаются друг от друга либо составом элементов, либо порядком их расположения.
- число размещений из n по k .
Число размещений из n по k можно определить следующим способом: первый объект выборки можно выбрать n способами, далее второй объект можно выбрать n -1 способом и т.д.
Преобразовав данную формулу, имеем:
Следует помнить, что 0!=1.
Примеры:
1. В первой группе класса А первенства по футболу участвует 17 команд. Разыгрываются медали: золото, серебро и бронза. Сколькими способами они могут быть разыграны?
Решение:
Комбинации
команд-победителей отличаются друг от друга составом и порядком следования
элементов, т.е. являются размещениями из 17 по 3.
2. Научное общество состоит из 25-ти человек. Необходимо выбрать президента общества, вице-президента, ученого секретаря и казначея. Сколькими способами это можно сделать?
Решение: Комбинации руководящего состава общества отличаются друг от друга составом и порядком следования элементов, т.е. являются размещениями из 25 по 4.
Перестановками без повторений из n элементов называются размещения без повторений из n элементов по n , т.е. размещения отличаются друг от друга только порядком следования элементов.
Число перестановок.
Примеры:
1. Сколько различных пятизначных чисел можно составить из цифр 1, 2, 3, 4, 5 при условии, что они должны состоять из различных цифр?
Решение: Имеем перестановки из 5 элементов. 2. Сколькими способами можно собрать 6 разноцветных лоскутков в пеструю ленту?Сочетаниями без повторений из n элементов по k называются такие выборки, которые содержат по k элементов, выбранных из числа данных n элементов генеральной совокупности без повторений, и отличаются друг от друга только составом элементов.
- число сочетаний из n по k
Элементы каждого из сочетаний можно расставить способами. Тогда Примеры:1. Если в полуфинале первенства по шахматам участвует 20 человек, а в финал выходят лишь трое, то сколькими способам и можно определить эту тройку?
Решение: В данном случае порядок, в котором располагается эта тройка, не существенен. Поэтому тройки, вышедшие в финал, являются сочетаниями из 20 по 3.
2. Сколькими способами можно выбрать трех делегатов из десяти человек на конференцию?Решение: В данном случае порядок, в котором располагается эта тройка, не существенен. Поэтому тройки делегатов являются сочетаниями из 10 по 3.
Конспект:
4.Применение графов (схем) при решении комбинаторных задач.
В случае, когда число возможных выборов на каждом шагу зависит от того, какие элементы были выбраны ранее, можно изобразить процесс составления комбинаций в виде «дерева». Сначала из одной точки проводят столько отрезков, сколько различных выборов можно сделать на первом шагу. Из конца каждого отрезка проводят столько отрезков, сколько можно сделать выборов на втором шагу, если на первом шагу был выбран данный элемент и т.д.
Задача:
При составлении команд космического корабля учитывается вопрос и психологической совместимости участников путешествия. Необходимо составить команду космического корабля из 3 человек: командира, инженера и врача. На место командира есть 4 кандидата: a 1 , a 2 , a 3 , a 4 .На место инженера- 3: b 1 , b 2 , b 3 . На место врача- 3: c 1 , c 2 , c 3 . Проведенная проверка показала, что командир a 1 психологически совместим с инженерами b 1 и b 3 и врачами c 1 и c 3 . Командир a 2 - с инженерами b 1 и b 2 . и всеми врачами. Командир a 3 - с инженерами b 1 и b 2 и врачами c 1 и c 3 . Командир a 4 -со всеми инженерами и врачом c 2 . Кроме того, инженер b 1 не совместим с врачом c 3 , b 2 - с врачом c 1 и b 3 - с врачом c 2 . Сколькими способами при этих условиях может быть составлена команда корабля?
Решение:
Составим соответствующее «дерево».
Ответ: 10 комбинаций.
Такое дерево является графом и применяется для решения комбинаторных задач.
Перестановка – это комбинация элементов из N разных элементов взятых в определенном порядке. В перестановке важен порядок следования элементов, и в перестановке должны быть задействованы все N элементов.
Задача
: Найти все возможные перестановки для последовательности чисел 1, 2, 3.
Существуют следующие перестановки:
1:
1 2 3
2:
1 3 2
3:
2 1 3
4:
2 3 1
5:
3 1 2
6:
3 2 1
Количество перестановок для N различных элементов составляет N! . Действительно:
Рассмотрим задачу получения всех перестановок чисел 1…N (то есть последовательности длины N ), где каждое из чисел входит ровно по 1 разу. Существует множество вариантов порядка получения перестановок. Однако наиболее часто решается задача генерации перестановок в лексикографическом порядке (см. пример выше). При этом все перестановки сортируются сначала по первому числу, затем по второму и т.д. в порядке возрастания. Таким образом, первой будет перестановка 1 2 … N , а последней — N N-1 … 1 .
Рассмотрим алгоритм решения задачи. Дана исходная последовательность чисел. Для получения каждой следующей перестановки необходимо выполнить следующие шаги:
Таким образом мы получим новую последовательность, которая будет рассматриваться в качестве исходной на следующем шаге.
Реализация на С++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include
using
namespace
std;
{
int
s = a[i];
a[i] = a[j];
a[j] = s;
}
bool NextSet(int
*a, int
n)
{
int
j = n - 2;
while
(j != -1 && a[j] >= a) j--;
if
(j == -1)
return
false; // больше перестановок нет
int
k = n - 1;
while
(a[j] >= a[k]) k--;
swap(a, j, k);
int
l = j + 1, r = n - 1;
while
(l
return
true;
}
void
Print(int
*a, int
n) // вывод перестановки
{
static int
num = 1; // номер перестановки
cout.width(3);
cout <<
num++ <<
": "
;
for
(int
i = 0; i < n; i++)
cout <<
a[i] <<
" "
;
cout <<
endl;
}
int
main()
{
int
n, *a;
cout <<
"N = "
;
cin >>
n;
a = new
int
[n];
for
(int
i = 0; i < n; i++)
a[i] = i + 1;
Print(a, n);
while
(NextSet(a, n))
Print(a, n);
cin.get(); cin.get();
return
0;
}
Результат выполнения
Особого внимания заслуживает задача генерации перестановок N элементов в случае если элементы последовательности могут повторяться. Допустим, исходная последовательность состоит из элементов n 1 , n 2 ... n k , где элемент n 1 повторяется r 1 раз, n 2 повторяется r 2 раз и т.д. При этом n 1 +n 2 +...+n k =N . Если мы будем считать все n 1 +n 2 +...+n k элементов перестановки с повторениями различными, то всего различных вариантов перестановок (n 1 +n 2 +...+n k)! . Однако среди этих перестановок не все различны. В самом деле, все r 1 элементов n 1 мы можем переставлять местами друг с другом, и от этого перестановка не изменится. Точно так же, можем переставлять элементы n 2 , n 3 и т. д. В итоге имеем r 1 ! вариантов записи одной и той же перестановки с различным расположением повторяющихся элементов n 1 . Таким образом, всякая перестановка может быть записана r 1 !·r 2 !·...·r k ! способами. Следовательно, число различных перестановок с повторениями равно
Для генерации перестановок с повторениями можно использовать алгоритм генерации перестановок без повторений, приведенный выше. Введем повторяющийся элемент в массив a. Ниже приведен код программы для генерации перестановок с повторениями (изменен только код функции main()
).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include
using
namespace
std;
void
swap(int
*a, int
i, int
j)
{
int
s = a[i];
a[i] = a[j];
a[j] = s;
}
bool NextSet(int
*a, int
n)
{
int
j = n - 2;
while
(j != -1 && a[j] >= a) j--;
if
(j == -1)
return
false; // больше перестановок нет
int
k = n - 1;
while
(a[j] >= a[k]) k--;
swap(a, j, k);
int
l = j + 1, r = n - 1; // сортируем оставшуюся часть последовательности
while
(l
return
true;
}
void
Print(int
*a, int
n) // вывод перестановки
{
static int
num = 1; // номер перестановки
cout.width(3); // ширина поля вывода номера перестановки
cout <<
num++ <<
": "
;
for
(int
i = 0; i < n; i++)
cout <<
a[i] <<
" "
;
cout <<
endl;
}
int
main()
{
int
n, *a;
cout <<
"N = "
;
cin >>
n;
a = new
int
[n];
for
(int
i = 0; i < n; i++)
a[i] = i + 1;
a = 1; // повторяющийся элемент
Print(a, n);
while
(NextSet(a, n))
Print(a, n);
cin.get(); cin.get();
return
0;
}
Результат работы приведенного выше алгоритма:
