dm_tema_2

Дискретная математика Тема 2. Комбинаторика

Е.А.Перепелкин

АлтГТУ

2012

2.1 Правила комбинаторики

Утверждение (Правило суммы) Пусть объект A может быть выбран n способами, объект B m способами. Тогда выбор или A èëè B может быть осуществл¼н n + m способами.

Утверждение (Правило произведения) Пусть последовательно выбираются два объекта A è B. Если объект A может быть выбран n способами и после каждого такого выбора

объект B может быть выбран m способами, то последовательный выбор A è B может быть осуществл¼н nm способами.

Пример

На книжной полке стоят 5 книг по математике и 7 книг по информатике. Сколько существует способов выбрать одну книгу с полки?

Таких способов 12. Здесь мы применили правило суммы.

Пример

Сколько слов, содержащих 5 букв, можно составить из 26 букв латинского алфавита при условии, что любые две стоящие рядом буквы различны?

При составлении слов первую букву можно выбрать любой из 26 букв алфавита. Вторая буква не должна совпадать с первой. Поэтому вторую букву можно выбрать 25-ю способами. Аналогично третья,

четвертая и пятая буквы могут быть выбраны 25-ю способами. Согласно правилу умножения получаем 26 254 = 10156250 различных

ñëîâ.

В теории множеств правилу суммы соответствует формула

jA [ Bj = jAj + jBj; A \ B = ;;

правилу произведения формула

jA Bj = jAjjBj:

Правило суммы и произведения можно обобщить на выбор нескольких объектов.

2.2 Перестановки, размещения, сочетания, разбиения

Пусть A = fa1; : : : ; ang конечное упорядоченное множество.

Определение Перестановкой называется любая упорядоченная последовательность

fai1 ; : : : ; ain g

элементов множества A.

Определение

Выборкой из n элементов по m называется набор

fai1 ; : : : ; aim g;

ãäå âñå aij 2 A.

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

Определение

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

Определение

Сочетанием из n элементов по m называется неупорядоченная выборка.

Обозначим:

Теорема

Справедливы формулы:

Pn = n!;

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

Для перестановок. По правилу произведения

Pn = n(n 1) 1 = n!:

Для сочетаний без повторений

Для размещений с повторениями

Для сочетаний с повторениями. Каждая неупорядоченная выборка с повторениями может быть записана в следующем виде

fa1; : : : ; a1; a2; : : : ; a2; : : : ; an; : : : ; an :g

| {z } | {z } | {z }

k1 k2 kn

ãäå ki число вхождений элемента ai в выборку, k1 + + kn = m. Выборку можно закодировать булевым вектором

f1; : : : ; 1; 0; 1; : : : ; 1; 0; : : : ; 1; : : : ; 1g:

роль разделителя.

Таким образом, число выборок равно числу булевых векторов длины n + m 1, содержащих ровно m единиц, и равно