Правила суммы и произведения.

Правило суммы – если элемент а может быть выбран способами, а элемент b – m способами, то один из этих элементов можно выбрать n+m способами.

Правило произведения – если элемент а может быть выбран способами и после каждого такого выбора элемент b можно выбрать m способами, то пару (ab) из этих элементов в указанном порядке можно выбрать nm способами.

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

Теорема. Число всех размещений из n элементов по k вычисляется по формуле:

 

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

 

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

 

В частном случае k=n размещения называются перестановками.

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

Пример: Различными перестановками множества элементов {1,2,3} будут (1,2,3), (1,3,2), (2,3,1), (2,1,3), (3,2,1), (3,1,2)

 

Неупорядоченные наборы из k элементов, взятых из данных n элементов, называются сочетаниямииз n элементов по k.

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

 

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