Основные концепции

Опираясь на основы логики и множеств, мы теперь изучим отношения, функции и комбинаторику — три столпа, связывающие абстрактные дискретные структуры с практическими вычислениями.

Отношения

Бинарное отношение $R$ из множества $A$ в множество $B$ — это подмножество $A \times B$ .

Свойства отношений

Свойство	Определение	Пример
Рефлексивность	$\forall a \in A: aRa$	$\leq$ на целых числах
Симметричность	$aRb \implies bRa$	«является братом/сестрой»
Антисимметричность	$aRb \land bRa \implies a = b$	$\leq$ на целых числах
Транзитивность	$aRb \land bRc \implies aRc$	$<$ на целых числах

Функции

Функция $f: A \to B$ — это отношение, в котором каждый элемент $A$ отображается ровно в один элемент $B$ .

Инъекция: разные входы дают разные выходы
Сюръекция: каждый элемент кообласти достигается
Биекция: и инъекция, и сюръекция одновременно

Комбинаторика

Перестановки

Число способов упорядочить $r$ элементов из $n$ различных:

P(n, r) = \frac{n!}{(n-r)!}

Сочетания

Число способов выбрать $r$ элементов из $n$ (порядок не важен):

\binom{n}{r} = \frac{n!}{r!(n-r)!}

from math import comb, perm

n, r = 10, 3
print(f"P({n},{r}) = {perm(n, r)}")   # 720
print(f"C({n},{r}) = {comb(n, r)}")    # 120

Биномиальная теорема

(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k

Принцип Дирихле

Если $n + 1$ объектов разместить в $n$ ящиков, то хотя бы один ящик содержит два или более объектов.