если объект А может быть выбран из множества M_n h способами и при каждом выборе объекта А другой объект В может быть выбран k способами, то объект , состоящий из двух объектов А и В может быть выбран hk способами.

Конечные подмножества элементов множества M_n называются соединениями.

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

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

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

Определение 7.1. Размещением из n элементов по m элементов без повторений называется упорядоченное подмножество попарно различных m элементов множества M_n ().

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

Определение 7.3. Сочетанием из n элементов по m элементов без повторений называется подмножество из m попарно различных элементов множества M_n без учёта порядка их следования ().

Для размещения или сочетания с повторениями требуется лишь условие, что и, следовательно, m может быть любым натуральным числом, независимым от числа n элементов множества M_n.

В перестановке с повторениями присутствуют все элементы множества M_n, причём указывается, сколько раз повторяются элементы . Число элементов в такой перестановке может быть любым натуральным числом, большим или равным n.

Обозначим символами , , число всех размещений, сочетаний без повторений из n элементов по m элементов и число всех перестановок без повторений из n элементов (). Символы для обозначения числа всех соединений определённого типа берутся из начальных букв соответствующих французских слов: arrangement – размещение, combination – комбинация, сочетание, permutation – перестановка.

Символами , , обозначим число всех размещений, сочетаний, перестановок с повторениями (m, m_i – любые натуральные числа). Число m_i указывает, что элемент a_i повторяется в перестановке m_i раз, причем .

Произведение n первых натуральных чисел обозначается символом n! и называется n-факториалом: .

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

♦ Теорема 7.1.Число размещений без повторений из n элементов по m элементов вычисляется по формуле

, (7.1)

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

. (7.2)

Доказательство.Докажем методом математической индукции формулы (7.1) и (7.2).

1) Для m=1 они справедливы, так как выбор по одному элементу из множества M_n можно осуществить только n способами, а по формулам (7.1) и (7.2) , .

2) Пусть эти формулы справедливы для произвольного фиксированного натурального числа k, то есть , . По правилу умножения , , так как в случае подмножества с попарно различными элементами множества M_n после выбора k элементов из M_n в нём останется n–k элементов, из которых по одному элементу можно выбрать n–k способами. А в случае размещения с повторениями (k+1)‑м элементом может быть любой из n элементов множества M_n. Учитывая, что , убеждаемся в справедливости формул (7.1) и (7.2). ■

Следствие 1. Так как , то . Таким образом, получается формула числа перестановок:

(7.3)

Формула для перестановок с повторениями такова:

. (7.3а)

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

Следствие 2.По правилу умножения . Следовательно,

,

то есть справедлива формула

. (7.4)

♦ Теорема 7.2.Число сочетаний из n элементов по m элементов с повторениями вычисляется по формуле

. (7.5)

Доказательство.Докажем формулу (7.5) методом математической индукции.

1) Для m=1 она справедлива, так как , а выбор по одному элементу из множества M_n можно осуществить только n способами.

2) Пусть формула (7.5) верна для произвольного фиксированного , то есть . Тогда, по правилу умножения, , т.к. вставить один элемент, взятый из M_n, мы можем n+k способами, добавив к уже выбранным k элементам либо один из них, либо любой из M_n. А в знаменателе число k+1 означает, что вставить этот дополнительный элемент, не изменяя сочетания, мы можем либо вначале, либо между первым и вторым и т.д., либо после последнего (то есть k+1 вариантов).

Учитывая, что , убеждаемся, что формула (7.5) справедлива для m=k+1, а значит, она справедлива и для любого натурального числа m. ■

♦ Теорема 7.3.Справедливо правило симметрии

. (7.6)

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

♦ Теорема 7.4.Справедлива формула (правило Паскаля)

. (7.7)

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

. ■

♦ Теорема 7.5. Число всех подмножеств из n элементов равно :

.

Доказательство. Докажем теорему методом математической индукции.

1) При n=1 имеем множество одного элемента , которое содержит два подмножества: пустое множество и само себя.

2) Пусть установлено, что множество из k элементов содержит ровно подмножеств.

Рассмотрим множество из k+1 элементов. Любое его подмножество В получается одним из двух способов:

а) берётся подмножество В множества ,

в) берётся подмножество и присоединяется элемент .

Каждым из этих способов получаем подмножеств, а всего подмножеств множества А. ■

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

J Пример 7.1. Сколько пятизначных чисел можно составить из цифр 1, 3, 7?