1.1. Основные понятия и определения

Любое понятие дискретной математики можно определить с помощью понятия множества. Для самого же множества не существует формального определения, считается, что это понятие первичное и не определяется. Говорят, что множество есть объединение различных объектов. Однако, понятие “объединение” и “объекты” остаются неопределяемыми.

Объекты, образующие множество, называются его элементами. Если элемент m принадлежит множеству S, то используют запись mS, в противном случае – запись mS.

Множество, содержащее конечное число элементов, называется конечным. Если же множество не содержит ни одного элемента, то оно называется пустым и обозначается .

Число элементов конечного множества S называется его мощностью и обозначается |S|.¹

Конечное множество S будем задавать списком его элементов²:

S={s₁,s₂,…,s_n}, где s₁,s₂,…,s_n – элементы S (обязательно различные).

Введем понятие мультимножества. Мультимножество есть объединение не обязательно различных объектов. Его можно считать множеством, в котором каждому элементу поставлено в соответствие³ положительное целое число, называемое кратностью.

Конечное мультимножество S будем записывать в следующем виде:

Здесь все s_i различны и k_i – кратность элемента s_i. Тогда мощность S равна .

Теперь рассмотрим некоторые из комбинаторных объектов.

Подмножества. Множество M называется подмножеством множества S (обозначение МS либо SМ; читается М входит в S, S содержит М) тогда и только тогда, когда любой элемент множества М принадлежит множеству S.

Теорема. Число подмножеств n-элементного множества S равно 2ⁿ.

Доказательство. Поставим в соответствие каждому подмножеству M множества S двоичный набор длины n по следующему правилу: s_iМ, если и только если i-й разряд равен единице. Число двоичных наборов длины n, согласно правилу произведения, равно 22…2=2ⁿ. Следовательно, число всех подмножеств n-элементного множества равно 2ⁿ.

Перестановки. Перестановкой называется расположение элементов множества в определенном порядке.

Теорема. Число перестановок n-элементного множества S, т.е. число способов его упорядочивания выражается формулой P_n=n!.

Символом n! (читается n-факториал) обозначается произведение натуральных чисел от 1 до n: n!=12...n. Считается, что 0!=1.

Доказательство. Будем последовательно выбирать элементы множества S и располагать их в определенном порядке на n местах. На первое место можно поставить любой из n элементов. После того, как заполнено первое место, на второе место можно поставить любой из оставшихся n-1 элементов и т.д. Тогда по правилу произведения все n мест можно заполнить n(п-1)(п-2)...21=n! способами. Следо­вательно, n-элементное множество можно упорядочить n! способами.

Размещения. Упорядоченные k-элементные подмножества множества из n элементов называются размещениями из n элементов по k.

Теорема. Число размещений из n по k определяется формулой:

.

Доказательство. Будем последовательно выбирать k-элементов из n-элементного множества, и располагать их в определенном порядке на k местах. На первое место можно поставить любой из n элементов, затем на второе - любой из n-1 оставшихся и т.д. По правилу произ­ведения имеем

.

Сочетания. Сочетанием из n элементов по k называется k-элементное подмножество множества из n элементов.

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

.

Доказательство. Изn-элементного множества можно образоватьразличных упорядоченныхk-элементных подмножеств. Каждоеk-элементное подмножество может быть упорядоченоР_kспособами. Тогда число сочетаний изnпоk -число неупорядоченныхk-элементных подмножествn-элементного множества будет равно

.

Для числа сочетания справедливы равенства

,

,

.

Последнее свойство вытекает из теоремы о числе подмножеств конечного множества (объясните почему).

Перестановки с повторениями. Перестановкой с повторениями называется расположение элементов мультимножества в определенном порядке.

Теорема. Число перестановок с повторениями для мультимножествавыражается формулой

,

где .

Доказательство 1.Рассмотрим одну перестановку мультимножества и заменим в ней все одинаковые элементы разными. Тогда, число различных перестановок, которые можно составить из рассматриваемой перестановки, равно k₁!k₂!…k_m!. Проделав это для каждой перестановки, получимn! перестановок. Следовательно,

C_n(k₁,k₂,…,k_m)k₁!k₂!…k_m!=n!,

Число C_n(k₁,k₂,…,k_m) называется полиномиальным коэффициентом. Приведем еще одно доказательство данной теоремы.

Доказательство 2. Для упорядочивания мультимножества необходимо из n мест выбрать k₁ мест для элемента s₁, что можно сделать способами, затем изn-k₁ оставшиеся мест выбрать k₂ мест для элемента s₂, что можно сделать способами и т.д. Тогда число способов упорядочивания мультимножестваS по правилу произведения равно (напомнив, что 0!=1)

.

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

Например, из трех элементов (m=3) a, b, c можно составить такие сочетания по два с повторениями: aа, ab, ас, bb, bc, cc.

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

.

Доказательство. Каждое сочетание полностью определяется, если указать, сколько элементов каждого из m типов в него входит. Поставим в соответствие каждому сочетанию последовательность нулей и единиц, составленную по следующему правилу: ставим подряд столько единиц, сколько элементов первого типа входит в сочетание, далее ставим нуль, и после него пишем столько единиц, сколько элементов второго типа содержит это сочетание и т.д. Например, написанным выше сочетаниям из трех букв по две будут соответствовать такие последовательности: