§ 4. Элементы комбинаторики. Соединения без повторений и с повторениями. Правила суммы и произведения.

Комбинаторика – теория соединений – изучает некоторые операции над конечными множествами, как упорядочение множества и разбиение множества, интересуется расположением элементов в множестве, выясняет, сколькими способами можно расположить элементы множества в том или ином порядке. Это приводит к понятиям перестановок, размещений и сочетаний. Основными задачами комбинаторики являются: 1) определение вида соединения; 2) подсчет числа соединений.

П.1 Соединения без повторений

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

Опр. 4.1.1Перестановки– всевозможные упорядоченные множества, составленные из всех элементов данного множества. Число всевозможных перестановок изnэлементов обозначают Р_nи находят по формуле

Р_n= n! (1),

где n!= 123n, 0!=1 по определению.

Пример 4.1.1.Сколько перестановок можно составить из трех букв а, в, с?

Решение:Р₃=123=6. Действительно: авс, вас, асв, сав, вса, сва.

Пример 4.1.2. Сколькими способами можно переставить буквы в слове «треугольник»?

Решение:Т.к. все буквы в данном слове разные, т.е. нет повторений, то можно воспользоваться формулой (1): Р₁₁=11!=39916800.

Опр. 4.1.2Размещениями из n по m называются всевозможные упорядоченные подмножества, содержащиеmэлементов из данныхn. Обозначаются и вычисляются по формуле:

(2).

Пример 4.1.3.Сколько можно составить четырехзначных чисел, содержащих различные цифры из 5 цифр.

Решение:Четырехзначное число – это упорядоченная последовательность цифр, т.е. имеем дело с размещениями без повторений: А₅⁴=5432=120.

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

Решение:

Опр. 4.1.3Сочетаниями из n по m называются всевозможные подмножества данныхn элементов, состоящие изm элементов. Для подсчета их числа используются следующие обозначение и формула:

(3).

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

Решение:Совокупность трех открыток является неупорядоченным подмножеством семи открыток, поэтому имеем дело с сочетаниями:

П.2 Соединения с повторениями

Опр: 4.2.1Перестановками с повторениями называются перестановки изnэлементов, в каждую из которых входитn₁элементова,n₂элементовb, …,n_kэлементовl, гдеn=n₁+n₂+…+n_k. Число перестановок с повторениями вычисляется по формуле:

Пример 4.2.1 Сколькими способами можно переставить буквы в слове “математика”.

Решение:В слове “математика” есть повторяющиеся буквы: “м” – 2 раза, “а” – 3 раза, “т” – 2 раза, “е” – 1 раз, “и” – 1 раз, “к” – 1 раз. Порядок расположения элементов имеет значение (это очевидно, так как если переставить местами 2 буквы, то получатся разные слова) и все элементы используются, следовательно, это перестановка с повторениями.

Таким образом, в слове “математика” можно переставить буквы 151200 способами.

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

Пример 4.2.2на почте продаются открытки 10 сортов. Сколько вариантов существует для покупки 12 открыток.

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

.

Таким образом, из 10 открыток можно выбрать набор из12 штук 293930 способами.

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

Пример 4.2.3В стену здания вмонтированы 8 гнезд для флажков. В каждое гнездо вставляется либо голубой, либо красный флажок. Сколько различных случаев распределения флажков на здание.

Решение:Так как порядок расположения элементов важен и не все элементы используются в данном соединении, то это размещение. А так как всего 8 гнезд, а флажков 2 вида (голубой и красный), то они будут повторяться, т.е. это размещение с повторением.

Таким образом, существует 256 способов украсить здание с 8 гнездами флажками двух цветов.