DiscreteMath.md

Оглавление

• Введение
• Теория множеств
• Теория мультимножеств
• Теория графов
• Математическая логика
• Комбинаторика

Введение

• Дискретность и непрерывность
• О дискретной математике
• Наборы элементов, их типы и свойства

Дискретность и непрерывность

Дискретностью (лат. discretus — разделённый, прерывистый) называют свойство некоторого объекта, означающее его конечность (прерывность), что противоположно свойству непрерывности, означающему бесконечность объекта.

Например, дискретное множество - это множество с конечным числом элементов, то есть элементы данного множества можно пересчитать, перечислить.

К примеру, дискретным является множество планет Солнечной системы: { Меркурий, Венера, Земля, Марс, Юпитер, Сатурн, Уран, Нептун }.

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

О дискретной математике

Дискретной математикой (англ. Discrete math) называют раздел математики, в котором изучаются только дискретные математические объекты: конечные множества, дискретные функции, конечные графы, высказывания и другие.

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

Наборы элементов, их типы и свойства

• О наборе элементов
• Характеристики набора элементов
• Типы наборов элементов

О наборе элементов

В математике нет чёткого определения для набора элементов.

Под набором элементов (англ. collection) подразумевают некоторую совокупность (группу) объектов, рассматриваемых вместе в данный момент времени (например, для решения некоторой задачи).

Объекты, из которых состоит некоторый набор, называют элементами (англ. elements) этого набора. Элементами набора могут выступать любые объекты: звёзды на небе, люди в списке, экспонаты в музее, фигуры на рисунке и так далее.

Для программиста самыми распространёнными наборами элементов являются массив (англ. array) и список (англ. list), для математика - множество (англ. set) и кортеж (англ. tuple).

Характеристики набора элементов

Существует две характеристики, которые полностью определяют свойства любого набора элементов:

1. Наличие повторяюшися элементов в наборе.
2. Упорядоченность набора.

Наличие повторяющихся элементов в наборе

Уникальность элементов набора означает, что данный набор не может содержать двух (и более) одинаковых элементов.

Если требование уникальности отсутствует, то набор элементов может содержать повторяющиеся элементы и называется набором элементов с повторениями (англ. collection with repetitions).

Упорядоченность набора

Упорядоченность набора означает, что в данном наборе порядок следования элементов имеет значение.

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

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

Типы наборов элементов

На основании перечисленных ранее характеристик набора можно выделить 4 типа наборов элементов:

• Неупорядоченный набор уникальных элементов. Примеры: множество, сочетание.
• Неупорядоченный набор элементов с повторениями. Примеры: мультимножество, сочетание с повторениями.
• Упорядоченный набор уникальных элементов. Примеры: перестановка, размещение.
• Упорядоченный набор элементов с повторениями. Примеры: кортеж, перестановка мультимножества, размещение с повторениями, число, слово.

Теория множеств

• Почему теория множеств достойна вашего внимания
• Множества и их элементы
• Принадлежность к множеству
• Основные виды множеств
• Мощность (кардинальность) множества
• Отношения между множествами
• Способы задания множества
• Графическое представление множеств
• Число подмножеств
• Пара и кортеж
• Операции над множествами
• Углубленно об отношнении
• Функция (отображение)
• Углубленно об операции

Как вы уже могли догадаться, теория множеств изучает множества, а точнее их виды, способы представления, отношения множеств и операции над ними.

Почему теория множеств достойна вашего внимания

Теория множеств вводит такие понятия, как множество, отношение, функция (отображение), упорядоченный набор элементов и операция, которые имеют невероятно широкое применение в математике, программировании, физике и других областях.

Реализационные базы данных (SQL) полностью базируются на математическом понятии отношения, где понятие множества заменяется понятием типа данных.

Некоторые структуры данных берут своё начало у теории множеств: упорядоченная пара, кортеж (вектор), граф, само множество и другие.

Вообще говоря, любые окружающие нас объекты можно классифицировать и представить в виде множеств, построить их иерархии, выявить их отношения и так далее. Множества и окружающие их понятия помогают нам представлять данные.

Множества и их элементы

Рекомендуется прочитать: «Наборы элементов, их типы и свойства».

Множество (англ. set) — это неупорядоченный набор (совокупность) каких-либо уникальных объектов, наделённых некоторыми общими признаками (характеристиками, чертами, свойствами).

Объекты, из которых состоит множество, называются элементами (англ. elements) этого множества. Они могут представлять собой что угодно: реальные объекты (людей, животных, предметы), абстрактные объекты (числа, фигуры), действия, события и так далее.

Множество обозначают большой латинской буквой (A-Z), а элементы множества - малыми латинскими буквами (a-z), перечисляя их внутри фигурных скобок через запятую:
A = { x, y, z }.

Главными отличительными чертами множества от других наборов являются уникальность и неупорядоченность его элементов.

Уникальность означает, что множество не может содержать двух (и более) одинаковых элементов. При попытке добавить уже существующий элемент множество должно остаться неизменным: { x, x } = { x }.

Неупорядоченность означает, что порядок следования элементов в множестве не имеет значения, поэтому множества { x, y } и { y, x } считаются одинаковыми.

Примеров множеств можно придумать бесконечно много: множество букв латинского алфавита { A, B, C }, множество женских имён { Ася, Дина, Сара }, множество цветов { белый, чёрный }, множество домашних питомцев { кот, собака, хомяк, кролик }, множество языков программирования { JavaScript, Kotlin, Python } и так далее.

Принадлежность к множеству

Объект x принадлежит множеству (содержится в множестве) A, если он является элементом множества A. Обозначение: x ∈ A. Пример такого множества A: { x, y }.

Объект x не принадлежит множеству A, если он не является элементом множества A. Обозначение: x ∉ A. Пример такого множества A: { y, z }.

Ещё примеры: символ i принадлежит множествам символов белорусского и латинского алфавитов, но не принадлежит множеству символов русского алфавита; число 0 принадлежит множеству целых чисел, но не принадлежит множеству натуральных чисел.

Основные виды множеств

• Одноэлементное множество
• Пустое и универсальное множества
• Конечное и бесконечное множества

Одноэлементное множество

Одноэлементное множество (англ. unit set, singleton) — множество, содержащее всего один элемент.

Пример одноэлементного множества: E = { 1 }.

Пустое и универсальное множества

Множество, которое не содержит ни одного элемента, называется пустым множеством (англ. empty set).

Пустое множество обозначается символом ∅ или {}.

Универсальное множество — множество, которое содержит в себе все остальные множества рассматриваемой задачи. Любое множество в конкретной задаче содержится в универсальном множестве.

Универсальное множество обозначается символом U.

Конечное и бесконечное множества

Конечным или счётным множеством (англ. finite set) называют множество, содержащее конечное число элементов.

Примеры конечных множеств: множество булевых значений { 0, 1 }, множество основных арифметических операций { +, -, •, ÷ }, множество букв алфавита некоторого языка.

Бесконечным множеством (англ. infinite set) называют множество, содержащее бесконечное число элементов.

Пример бесконечного множества: множество натуральных чисел N = { 1, 2, 3, ... }.

Мощность (кардинальность) множества

Мощьностью множества A или кардинальностью (англ. cardinality) множества A называют число элементов этого множества.

Обозначение мощности множества A, содержащего n элементов: |A| = n.

Например, |∅| = 0, |{ a }| = 1, |{ 3, 5 }| = 2 и так далее.

Отношения между множествами

• Пересекающиеся и непересекающиеся множества
• Подмножество (включение множества)
• Равенство множеств
• Строгое включение множества

Пересекающиеся и непересекающиеся множества

Множества A и B пересекаются, если они содержат некоторые одинаковые (общие) элементы*. То есть множества A и B пересекаются, если существует хотя бы один элемент x, принадлежащий и множеству A, и множеству B одновременно.

Множества A и B не пересекаются, если у них нет общих элементов. То есть не существует такого элемента x, принадлежащего и множеству A, и множеству B одновременно.

Например, множества символов латинского и белорусского алфавитов пересекаются (имеется общий элемент i), а множества символов китайского и русского алфавитов не пересекаются (поскольку не имеют общих элементов).

Подмножество (включение множества)

Множество A называют подмножеством множества B, если все элементы множества A содержатся в множестве B. В этом случае говорят, что множество A содержится в множестве (включено в множество) B, а множество B содержит (включает в себя) множество A.

Включение множества A в B обозначается: A ⊆ B.

Например, множество деревьев является подмножеством множества растений, а множество растений - подмножеством живых организмов; множество планет Солнечной системы является подмножеством множества планет нашей галактики и так далее.

Задача #1 (подмножества)

«Найти все подмножества множества D = { 3, 6, 9 }.

Ответ

∅, { 3 }, { 6 }, { 9 }, { 3, 6 }, { 3, 9 }, { 6, 9 }, { 3, 6, 9 }

Замечание

Каждое из перечисленных в ответе множеств, а также множество D, содержится в универсальном множестве (⊆ U).

Равенство множеств

Множества A и B равны*, если все их элементы совпадают. Иначе говоря, множество A содержит все элементы множества B (B ⊆ A), а множество B содержит все элементы множества A (A ⊆ B).

Обозначение равенства множеств A и B: A = B.

Если совпадают не все элементы множеств A и B, то множества A и B не равны между собой.

Обозначение неравенства множеств A и B: A ≠ B.

Строгое включение множества

Множество A строго включено в множество B, если все элементы множества A содержатся в множестве B (A ⊆ B), но множества A и B не равны (A ≠ B).

Обозначение строгого включения множества A в множество B: A ⊂ B.

Задача #2 (отношения множеств)

«Имеется 4 множества A = { 1, 3, 5 }, B = { 1, 3, 5 }, C = { 1, 3 }, D = { 5, 7 }. Как эти множества относятся между собой?»

Ответ

A = B, C ⊂ A, C ⊂ B, A ≠ D, B ≠ D, C не пересекается с D.

Способы задания множества

Множество считается заданным, если заданы (известны) все элементы этого множества или указан явный способ их получения.

Задать множество можно несколькими способами:

1. При объявлении множества перечислить все его элементы (это возможно только для конечных множеств). Пример: B = { 0, 1 }.
2. При объявлении множества указать характеристическое свойство P(x) - такое свойство, которым обладает каждый элемент x данного множества и не обладает ни один элемент, не входящий в данное множество. Обозначение: A = { x | P(x) }. Знак | читается “таких, что”, поэтому объявление полностью читается “множество элементов x таких, что они удовлетворяют свойству P(x)”. Свойство P(x) может задаваться выражением, неравенством, уравнением, а также при помощи слов.
3. Задать множество графически.

Примеры характеристических свойств

Пример задания множества неравенством: K = { x | 3 < x < 7 } - множество элементовx таких, что они больше трёх и меньше семи. В множество K попадают как целые числа 4, 5 и 6, так и бесконечное множество дробных чисел заданного промежутка по типу 3.14, 5.7, 6.333.

Пример задания множества выражением, содержащим уже существующий элемент множества: N = { 1 ∈ N | "если x ∈ N, то (x + 1) ∈ N" } - множество натуральных чисел (1 - первый элемент, каждый последующий элемент на единицу больше предыдущего).

Ещё один пример задания множества выражением: J = { x | "если x ∈ J, то -x ∈ J" } - множество симметричных относительно нуля элементов. Например, если добавить в множество J число 3, то в него добавляется также и -3.

Пример задания множества уравнением. Задание графика G функции f: X → Y:
G = { (x,y) ∈ X × Y | f(x) = y }.

Графическое представление множеств

• Диаграмма Эйлера
• Диаграмма Венна

Диаграмма Эйлера

Диаграмма Эйлера - геометрическая схема, с помощью которой можно наглядно изображать отношения множеств (подмножество и пересечение множеств).

На диаграммах Эйлера множества обычно представлены кругами (но могут быть использованы и другие простые фигуры), отчего диаграммы Эйлера также называют кругами Эйлера.

Один круг представляет одно множество.

Если круги двух множеств пересекаются, то эти множества имеют общие (одинаковые) элементы.

Если круги двух множеств не пересекаются, то эти множества не имеют общих (одинаковых) элементов.

Если круг одного множества полностью размещён внутри круга другого множества, то соответствующее первому кругу множество является подмножеством множества, соответствующего второму кругу.

Диаграмма Венна

Диаграмма Венна (также диаграмма Эйлера — Венна) — схематичное изображение основных операций (объединение, пересечение, разность, симметрическая разность) над несколькими множествами.

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

Все остальные множества задачи изображаются простыми фигурами (обычно кругами) внутри прямоугольника. Внутри этих фигур изображены элементы множества. Если множества имеют одинаковые элементы (пересекаются), то эти элементы размещают в пересечении фигур.

Число подмножеств

Множество всех подмножеств множества A называется булеаном (англ. power set, powerset).

Число всех подмножеств (мощность булеана), некоторого множества A мощности n равно: 2^n.

Формула выше доказывается комбинаторно. На каждый элемент множества A приходится по 2 возможных исхода (случая): “элемент содержится в некотором подмножестве” (обозначим 1), “элемент не содержится в некотором подмножестве” (обозначим 0). Для n элементов по правилу произведения имеем 2^n исходов, а значит и 2^n подмножеств.

Пусть A = { x, y, z }, тогда n = |A| = 3 и существует 2^3 = 8 подмножеств множества A:

x	y	z	множество
0	0	0	∅
0	0	1	{ z }
0	1	0	{ y }
0	1	1	{ y, z }
1	0	0	{ x }
1	0	1	{ x, z }
1	1	1	{ x, y, z }

Число всех подмножеств мощности m некоторого множества A мощности n равно биноминальному коэффициенту: С(n,k) = n! ÷ (k!(n-k)!).

В комбинаторике это эквивалентно выборке k элементов из n уникальных элементов.

Пусть A = { h, o, p, e } и m = 2, тогда n = |A| = 4 и существует 4! ÷ (2!2!) = (3 • 4) ÷ 2 = 6 подмножеств мощности 2 множества A: { h, o }, { h, p }, { h, e }, { o, p }, { o, e }, { p, e }.

Пара и кортеж

• Неупорядоченная пара
• Упорядоченная пара
• Кортеж (упорядоченный набор элементов)

Неупорядоченная пара

Неупорядоченной парой (англ. unordered pair), иногда просто парой (англ. pair set), называют множество, состоящее из двух элементов.

Неупорядоченная пара объектов x и y обозначается: { x, y }.

Поскольку порядок следования элементов в множестве не важен, пары { x, y } и { y, x } считаются одинаковыми.

Несмотря на то, что по определению пара - это множество, наборы вроде { x, x } так же иногда называют парами, хоть они и являются мультимножествами.

Упорядоченная пара

Упорядоченной парой (англ. ordered pair) называют такой набор из двух объектов, в котором порядок следования этих объектов имеет значение.

Упорядоченная пара объектов x и y обозначается (x, y).

По определению для упорядоченной пары объектов x и y справедливо: (x, y) ≠ (y, x).

Элемент x называют первым элементом (англ. first entry), первой координатой (англ. first coordinate) или первой компонентой (англ. first component) упорядоченной пары (x, y), элемент y – вторым элементом (англ. second entry), второй координатой (англ. second coordinate) или второй компонентой (англ. second component) упорядоченной пары (x, y).

Порядок следования элементов x и y в круглых скобках так же важен для упорядоченной пары, как порядок букв в словах («да» и «ад»), порядок цифр в числах (18и 81) и так далее.

Определение упорядоченной пары в теории множеств

Пусть задана неупорядоченная пара { x, y } элементов x и y. Множество { { x }, { x, y } } называют упорядоченной парой элементов x и y с первым элементом x, а множество { { y }, { x, y } } называют упорядоченной парой элементов x и y с первым элементом y.

Кортеж (упорядоченный набор элементов)

Понятие кортежа является обобщением понятия упорядоченной пары.

Пусть заданы n множеств A1, A2, …, An (не обязательно различных: некоторые из них могут повторяться). Кортежем длины n называют упорядоченный набор из n элементов x1 ∈ A1, x2 ∈ A2, …, xn ∈ An.

Элемент x1 называют первым элементом (первой координатой, компонентой) кортежа, элемент x2 - вторым элементом (второй координатой, компонентой) и так далее.

Обозначение кортежа из n элементов:
(x1, x2, …, xn).

По определению, нельзя менять элементы x1, x2, …, xn местами внутри круглых скобок, иначе получится другой кортеж:
(x1, x2, …, xn) ≠ (x2, x1, …, xn).

Кортеж длины 2 также называют упорядоченной парой, кортеж длины 3 - упорядоченной тройкой и так далее.

Два кортежа (x1, x2, …, xn) и (y1, y2, …, ym) равны лишь тогда, когда равны их длины (n = m) и попарно равны все их элементы (x1 = y1, x2 = y2, …, xn = yn).

Кортеж длины 3 (x1, x2, x3) представляет собой упорядоченную пару, состоящую кортежа длины 2 (x1, x2) и элемента x3: (x1, x2, x3) = ((x1, x2), x3). Зная это и обозначение упорядоченной пары на языке множеств: (x, y) = { { x }, { x, y } }, можно последовательно получить обозначение кортежа любой длины на языке множеств.

Операции над множествами

• Об операциях над множествами
• Пересечение множеств
• Объединение множеств
• Разность множеств
• Симметрическая разность множеств
• Декартово произведение множеств
• Дополнение множества
• Свойства операций над множествами
• Приоритет операций над множествами

Об операциях над множествами

Большинство операций над множествами либо бинарные, либо унарные.

Бинарная операция (двуместная операция) — математическая операция, принимающая два аргумента и возвращающая один результат.

Соответственно, бинарная операция над множествами принимает два множества и возвращает одно.

Бинарные операции над множествами:

• Пересечение множеств
• Объединение множеств
• Разность множеств
• Симметрическая разность множеств
• Декартово произведение множеств

Аналогично, унарная операция над множеством принимает одно множество и возвращает одно множество.

Унарные операции над множествами:

• Дополнение множества

Пересечение множеств

Пересечением множеств A и B называют множество элементов, принадлежащих и множеству A, и множеству B одновременно.

Обозначение пересечения множеств A и B:
A ∩ B = { x | "x ∈ A и x ∈ B" }.

Если у множеств A и B нет общих элементов, то их пересечение равно пустому множеству: A ∩ B = ∅.

Объединение множеств

Объединением множеств A и B называют множество, содержащее все элементы множества A и все элементы множества B.

Обозначение объединения множеств A и B:
A ∪ B = { x | "x ∈ A или x ∈ B" }.

Если известно, что множества A и B не пересекаются (A ∩ B = ∅), то объединение можно обозначить знаком сложения: A + B = A ∪ B.

Мощность объединения множеств A и B можно рассчитать, используя принцип включений-исключений: |A ∪ B| = |A| + |B| - |A ∩ B|.

Задача #3 (пересечение и объединение)

«Заданы множества A = { 1, 3, 5, 7 }, B = { 3, 5, 9 }, С = { 8, 9 }. Найти все комбинации объединения и пересечения данных множеств.»

Ответ: A ∩ B = { 3, 5 }, A ∪ B = { 1, 3, 5, 7, 9 }, A ∩ C = ∅, A ∪ C = { 1, 3, 5, 7, 8, 9 }, B ∩ C = { 9 }, B ∪ C = { 3, 5, 8, 9 }, A ∩ B ∩ C = ∅, A ∪ B ∪ C = { 1, 3, 5, 7, 8, 9 }.

Разность множеств

Разностью множеств A и B называется множество, которое содержит только те элементы из множества A, которые не содержатся в множестве B.

Обозначение разности множеств A и B:
A / B = { x | "x ∈ A и x ∉ B" }.

Eсли множества A и B не пересекаются (A ∩ B = ∅), то для их разности справедливо:

1. A / B = A,
2. B / A = B.

Eсли A ⊆ B, то A / B = ∅.

Симметрическая разность множеств

Симметрической разностью множеств A и B называется множество, которое содержит только те элементы из множества A, которые не содержатся в множестве B, и только те элементы из множества B, которые не содержатся в множестве A.

Обозначение cимметрической разности множеств A и B:
A Δ B = { x | "(x ∈ A и x ∉ B) или (x ∈ B и x ∉ A)" }.

Фактически, симметрическая разность множеств A и B эквивалентна следующим выражениям:
A Δ B = (A / B) ∪ (B / A) = (A ∪ B) / (A ∩ B).

Eсли A = B, то A Δ B = ∅.

Задача #4 (разность и симметрическая разность)

«Заданы множества A = { 1, 2, 3 }, B = { 0, 1 }. Найти их разность и симметрическую разность.»

Ответ: A / B = { 2, 3 }, A Δ B = { 0, 2, 3 }.

Декартово произведение множеств

Декартово (прямое) произведение множеств A и B — множество всех упорядоченных пар элементов множеств A и B. Каждый элемент из множества A ставится в соответствие (пару) с каждым элементом их множества B.

Обозначение декартова произведения множеств A и B:
A × B = { (x, y) ∣ "x ∈ A и y ∈ B" }.

Основные свойства декартова произведения A × B:

1. (A × B) ≠ (B × A), поскольку для упорядоченых пар справедливо (x, y) ≠ (y, x).
2. |A × B| = |A|•|B|, то есть количество пар в декартовом произведении A × B равняется произведению количества элементов множества A на количество элементов множества B.
3. Если все множители декартова произведения - конечные множества, то результатом произведения станет так же конечное множество. Если хотя бы один множитель - бесконечное множество, то результат произведения - так же бесконечное множество.

Декартово произведение трёх (и более) множеств A, B, C составляется аналогично, при этом элементами произведения A × B × C будут всевозможные упорядоченные тройки (кортежи длины 3) :
A × B × C = { (x, y, z) ∣ "x ∈ A, y ∈ B и z ∈ C" }.

Декартово произведение не коммутативно: (A × B) × C ≠ A × (B × C).

Задача #5 (декартово произведение)

«Заданы множества A = { x, y, z }, B = { 0, 1 }. Найти декартовы произведения A × A, A × B, B × A, B × B.»

Ответ:
A × A = { (x, x), (x, y), (x, z), (y, x), (y, y), (y, z), (z, x), (z, y), (z, z) },
A × B = { (x, 0), (x, 1), (y, 0), (y, 1), (z, 0), (z, 1) },
B × A = { (0, x), (0, y), (0, z), (1, x), (1, y), (1, x) },
B × B = { (0, 0), (0, 1), (1, 0), (1, 1) }.

Дополнение множества

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

Дополнение множества A - такое множество, которое дополняет множество A до универсального множества U, то есть содержит все те элементы универсального множества U, которые не содержатся в A.

Обозначение дополнения множества A: ¬A = U / A = { x ∣ “x ∉ A и x ∈ U” }.

Операция дополнения множества близка по смыслу к операции логического отрицания.

Свойства операции дополнения множества A:

1. У множества и его дополнения нет пересечений: A ∩ ¬A = ∅.
2. Объединение множества и его дополнения составляет универсальное множество: A ∪ ¬A = U.
3. Двойное дополнение множества составляет само множество: ¬¬A = A.

Свойства операций над множествами

Рекомендуется сперва прочесть: «Свойства бинарных операций».

Обозначим символом ◇ произвольную операцию над множествами, тогда при изучении свойств обозначение ◇ ∈ { ∩, ∪ } будет означать, что свойство выполняется для операций ∩ и ∪.

1. Идемпотентность: A ◇ A = A , ◇ ∈ { ∩, ∪ }.
2. Коммутативность: A ◇ B = B ◇ A , ◇ ∈ { ∩, ∪, Δ }.
3. Ассоциативность: (A ◇ B) ◇ C = A ◇ (B ◇ C) , ◇ ∈ { ∩, ∪, Δ }.
4. Дистрибутивность

• пересечения относительно объединения: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C),
• пересечения относительно симметрической разности: A ∩ (B Δ C) = (A ∩ B) Δ (A ∩ C),
• объединения относительно пересечения: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C),

5. Свойства пустого множества ∅:

• A ∪ ∅ = A,
• A ∩ ∅ = ∅,
• ∅ / A = ∅,
• A / ∅ = A,
• A Δ ∅ = A,
• A × ∅ = ∅,
• ∅ × A = ∅,
• A / A = ∅,
• A Δ A = ∅.

6. Свойства унарного дополнения ¬:

• ¬∅ = U,
• ¬U = ∅,
• ¬¬A = A,
• A ∪ ¬A = U,
• A ∩ ¬A = ∅,
• A / ¬A = A,
• A Δ ¬A = U.

7. Принцип включений-исключений: |A ∪ B| = |A| + |B| - |A ∩ B|.

Приоритет операций над множествами

Рекомендуется сперва прочесть: «Приоритет и очерёдность операций».

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

Если в выражении с несколькими различными операциями скобки отсутствуют, то порядок (приоритет) выполнения операций над множествами следующий:

1. Унарные операции: дополнение (¬A).
2. Пересечение (A ∩ B).
3. Остальные бинарные операции: объединение (A ∪ B), разность (A / B) и симметрическая разность (A Δ B).

Операции над множествами одного приоритета выполняются слева направо.

Декартово произведение × используется несколько для других целей, поэтому обычно не появляется в одних и тех же выражениях с остальными операциями над множествами и в «гонке приоритетов» не участвует.

Углубленно об отношении

• Об отношении и примеры отношений
• Бинарное отношение
• Свойства бинарных отношений
• Задача (свойства отношений между множествами)
• Область определения и область значений отношения
• Композиция бинарных отношений

Об отношении и примеры отношений

Говоря простыми словами, отношение — такая математическая структура, которая выражает то, как два или более каких-либо объектов относятся друг к другу, как (чем) они друг с другом связаны.

Например, равенство x = y является одним из видов отношений между объектами x и y, параллельность a || b является одним из видов отношений между прямыми a и b и так далее.

Пусть заданы n множеств A1, A2, …, An (не обязательно различных: некоторые из них могут повторяться). Тогда n-арным (n-местным) отношением R, заданном на множествах A1, A2, …, An, называется подмножество декартового произведения этих множеств (R ⊆ A1 × A2 × … An).

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

Отношения, как и другие множества, обозначают большими латинскими буквами (часто R, S, T).

Связь элементов x1 ∈ A1, x2 ∈ A2, …, xn ∈ An n-арным отношением R обозначается двумя способами:

1. R(x1, x2, …, xn),
2. (x1, x2, …, xn) ∈ R.

При n = 1 отношение называется унарным. Оно отождествляется со свойством одного объекта и обычно не рассматривается.

При n = 2 отношение называется бинарным. Этот вид отношений встречается чаще всего, поэтому далее мы уделим ему особое внимание.

При n = 3 отношение называется тернарным и так далее.

Бинарное отношение

Бинарное (двухместное) отношение R — отношение между двумя множествами A и B, то есть всякое подмножество декартова произведения множеств A и B: R ⊆ A × B.

Связь элементов x ∈ A и y ∈ B бинарным отношением R обычно обозначают так: xRy, но записи R(x, y) и (x,y) ∈ R из определения n-арного отношения так же применимы.

Бинарное отношение R на множестве A — отношение множества A самого с собой, то есть любое подмножество декартова произведения множества A самого с собой R ⊆ A^2 = A × A.

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

Для полного понимания ещё раз взглянем на определение. Вспомним, что декартово произведение A × B - это множество всех упорядоченных пар (x, y) элементов x ∈ A и y ∈ B. Значит некоторое подмножество R декартового произведения - множество, содержащее определённое количество этих упорядоченных пар. Запись (x, y) ∈ R наглядно показывает принадлежность упорядоченной пары к множеству R. Эта принадлежность и означает, что элементы x и y связаны отношением R.

Свойства бинарных отношений

Бинарное отношение R, заданное на множестве A, может обладать некоторыми из следующих свойств:

• Рефлексивность: ∀x ∈ A : (xRx), то есть для любого элемента x из множества A справедливо, что x связан отношением R сам с собой (xRx). Пример: x = x.
• Антирефлексивность: ∀x ∈ A : ¬(xRx), то есть для любого элемента x из множества A справедливо, что x не связан отношением R сам с собой (¬(xRx)). Пример: неверно, что x < x.
• Симметричность: ∀x, y ∈ A : (xRy ⇒ yRx), то есть для любых элементов x и y из множества A справедливо, что из выполнения xRy следует выполнение yRx. Пример: если x = y, то y = x.
• Асимметричность: ∀x, y ∈ A : (xRy ⇒ ¬(yRx)), то есть для любых элементов x и y из множества A справедливо, что из выполнения xRy следует невыполнение yRx (¬(yRx)). Пример: если x < y, то неверно, что y < x.
• Антисимметричность: ∀x, y ∈ A : (xRy ∧ yRx ⇒ x = y), то есть для любых элементов x и y из множества A справедливо, что из выполнения xRy и yRx следует, что x = y. Пример: если x ≤ y и y ≤ x, то x = y.
• Транзитивность: ∀x, y, z ∈ A : (xRy ∧ yRz ⇒ xRz), то есть для любых элементов x, y и z из множества A справедливо, что из выполнения xRy и yRz следует справедливость xRz. Пример: если x = y и y = z, то x = z.

Не все свойства отношений совместимы друг с другом: отношение не может быть одновременно симметричным и асимметричным, рефлексивным и антирефлексивным.

Отношение эквивалентности — бинарное отношение R между объектами x и y, которое рефлексивно, симметрично и транзитивно.

Например, отношение = является отношением эквивалентности, поскольку для любых объектов x, y и z выполняется:

1. x = x,
2. (x = y) ⇒ (y = x),
3. (x = y) ∧ (y = z) ⇒ (x = z).

Отношение порядка — бинарное отношение R между объектами x и y, которое обладает лишь некоторыми из свойств отношения эквивалентности.

Например, на множестве вещественных чисел отношения ≤ (рефлексивно и транзитивно, но не симметрично), ≠ (симметрично и транзитивно, но не рефлексивно), < (транзитивно, но не рефлексивно и не симметрично) являются отношениями порядка.

Отношения не обязательно обозначаются символами, связь объектов можно передать словами. Например, a - потомок b, m левее n, x севернее y - все перечисленные отношения антирефлексивны, асимметричны, но транзитивны, а вот отношение отец к тому же не транзитивно (если x - отец y, то y не отец x).

Множества можно рассматривать как элементы другого множества, поэтому сказанное выше также применимо и к отношениям между множествами.

Задача (свойства отношений между множествами)

«Какими свойствами обладают отношения, отвечающие за равенство, наличие пересечений и включение множеств?»

Ответ:

Выше уже было показано, что отношение = для элементов x и y является отношением эквивалентности, а отношение ≠ - отношением порядка. Это так же справедливо и для множеств A и B.

Отношение пересекается с является отношением эквивалентности:

1. Рефлексивно: верно, что A пересекается с A (есть общие элементы).
2. Симметрично: если A пересекается с B, то верно, что B пересекается с A.
3. Транзитивно: если A пересекается с B, B пересекается с C, то верно, что A пересекается с C.

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

1. Антирефлексивно: неверно, что A не пересекается с A (есть общие элементы).
2. Симметрично: если A не пересекается с B, то верно, что B не пересекается с A.
3. Транзитивно: если A не пересекается с B, B не пересекается с C, то верно, что A не пересекается с C.

Отношение ⊆ (включено в , является подмножеством) является отношением порядка:

1. Рефлексивно: верно, что A ⊆ A.
2. Асимметрично: если A ⊆ B, то неверно, что B ⊆ A.
3. Транзитивно: если A ⊆ B, B ⊆ C, то верно, что A ⊆ C.

Отношение ⊂ (строго включено в ) является отношением порядка:

1. Антирефлексивно: неверно, что A ⊂ A.
2. Асимметрично: если A ⊂ B, то неверно, что B ⊂ A.
3. Транзитивно: если A ⊂ B, B ⊂ C, то верно, что A ⊂ C. Пример: { 1 } ⊂ { 1, 2 } ⊂ { 1, 2, 3 }.

Область определения и область значений отношения

Множество всех первых компонент x упорядоченных пар (x, y) из множества R называют областью определения отношения R.

Обозначение области определения: Dom R = { x ∣ ∃y ((x, y) ∈ R) }, то есть множество таких элементов x, для которых найдутся такие элементы y, что упорядоченная пара (x, y) будет принадлежать множеству R.

Множество всех вторых компонент y упорядоченных пар (x, y) из множества R называют областью значений отношения R.

Обозначение области значений: Im R = { y ∣ ∃x ((x, y) ∈ R) }, то есть множество таких элементов y, для которых найдутся такие элементы x, что упорядоченная пара (x, y) будет принадлежать множеству R.

Таким образом, запись xRy означает связь отношением R между элементом x из области определения Dom R и элементом y из области значений Im R.

Композиция бинарных отношений

Композицией (произведением, суперпозицией) бинарных отношений R ⊆ A × B и S ⊆ B × C (composition of binary relations) называется такое отношение (R ○ S) ⊆ A × C, что для любых элементов a ∈ A, c ∈ C существует связь a(R ○ S)c тогда и только тогда, когда существует элемент b ∈ B такой, что одновременно существуют связи aRb и bSc.

Запись композиции отношений R и S на языке символов: ∀a∈A,∀c∈C: a(R ○ S)c ⇔ ∃b∈B: (aRb)∧(bSc).

Функция (отображение)

• Функция одной переменной
• Область определения и область значений функции
• Непрерывная, разрывная и дискретная функции
• Сюръективность, инъективность и биективность
• Функция нескольких переменных
• Композиция функций
• Индикаторная функция

Функция одной переменной

Функция одной переменной (англ. function) — это такое бинарное отношение R ⊆ X × Y, что каждому элементу x ∈ X соответствует единственный элемент y ∈ Y.

Функцию именуют малыми латинскими буквами (обычно f, h, g).

Элемент x ∈ X называют аргументом функции f (англ. the argument of the function f), а элемент y ∈ Y - значением функции f (англ. the value of the function f).

Говорят, что функция f принимает аргумент x и возвращает значение y.

Обозначение функции f, принимающей аргумент x и возвращающей значение y: f(x) = y. Так же допустимы обозначение y = f(x) и сокращённые обозначения: f(x), f.

Функциональное бинарное отношение R

«Пусть x ∈ X, y, z ∈ Y, тогда бинарное отношение R называют функциональным, если выполняется (xRy ∧ xRz) → (y = z), то есть, если одновременно существуют связи xRy и xRz, не может существовать двух разных значений y и z для одного аргумента x и тогда y = z.»

Отображение

Функцию f(x) = y, x ∈ X, y ∈ Y также называют отображением множества X в множество Y и обозначают f: X → Y.

Говорят, что функция f отображает множество X в множество Y.

Область определения и область значений функции

Множество X называют областью определения или областью задания функции f (англ. the domain of the function f) и обозначают D(f).

Множество Y называют областью значений функции f (англ. the codomain of the function f).

Множество таких элементов y ∈ Y, для которых существует упорядоченная пара (x, y) ∈ f, x ∈ X, называют множеством значений функции f и обозначают E(f).

Говорят, что функция задана (определена) на множестве X и принимает значения из множества Y.

Способы задания функции

Непрерывная, разрывная и дискретная функции

В математике чаще всего рассматриваются числовые функции.

Числовая функция - это функция, которая ставит одни числа в соответствие другим числам, то есть принимает числовой аргумент x и возвращает числовое значение y.

Говоря простыми словами, непрерывная функция - это такая функция, у которой между двумя любыми двумя значениями y1 и y3 всегда найдётся ещё одно значение y2 при некотором аргументе x2. Например, между значениями y1 = 1 и y3 = 2 существует значение 1.5, между 1 и 1.5 - 1.25, между 1 и 1.25 - 1.125 и так далее.

Графически непрерывная функция представляется непрерывной линией.

Понятно, что для непрерывности функции необходимо, чтобы область значений была бесконечным множеством, иначе средняя точка на каком-то этапе не найдётся.

Например, линейная функция f(x) = 3x - 7, x ∈ R, графиком которой является прямая*, непрерывна.

Например, функция, возвращающая модуль числа, непрерывна:

f(x) = |x| = {
  x, x >= 0;
 -x, x < 0;
}

Если между некоторыми двумя значениями y1 и y3 не существует среднего значения y2, то функция называется разрывной функцией, то есть функцией, имеющей точки разрыва.

Функция может быть разрывна в одной точке и непрерывна во всех остальных. Например, функция sgn(x): R → { -1, 0, 1 }, возвращающая знак числа, разрывна лишь в одной точке 0:

sgn(x) = {
  1, x > 0;
  0, x = 0;
 -1, x < 0;
}

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

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

Пример дискретной функции g, заданной на множестве { 0, 1 } и принимающей значения из множества { ложь, истина }:

g(x) = {
  ложь, x = 0;
  истина, x = 1;
}

Сюръективность, инъективность и биективность

Функция f называется сюръективной (сюръекцией), если каждому элементу y ∈ Y может быть поставлен в соответствие хотя бы один элемент x ∈ X. Иначе говоря, не существует таких y ∈ Y, которым не соответствует хотя бы один x ∈ X.

Сюръективное отображение допускает существование двух разных аргументов x1, x2 ∈ X, которым соответствует один и тот же y ∈ Y (y = f(x1) = f(x2)). Таким образом, если множество X содержит больше элементов, чем множествоY, то отображение всё ещё может быть сюръективным. Но если множество Y содержит больше элементов, чем множество X, то оно не может быть сюръективным по определению функции.

Функция f называется инъективной (инъекцией), если любым двум разным элементам x1, x2 ∈ X соответствуют различные элементы y1, y2 ∈ Y (если x1 ≠ x2, то f(x1) ≠ f(x2)). Другими словами, для любых элементов x1, x2 ∈ X верно: если выполняется f(x1) = f(x2), то также выполняется и x1 = x2.

Функция f называется биективной (биекцией), если она сюръективна и инъективна одновременно.

Иначе говоря, биекция (взаимно-однозначное отношение) — такое бинарное отношение R ⊆ X × Y, что каждому значению x ∈ X соответствует единственное значение y ∈ Y, а каждому значению y ∈ Y соответствует единственное значение x ∈ X.

Задача (сюръективность, инъективность, биективность)

«Даны функции f, g: R → R; f(x) = x + 1; g(x) = |x|. Сюръективны, инъективны, биективны ли они?»

Ответ: f биективна, g не инъективна и не сюръективна.

Значение f(x) всегда на единицу больше значения x, а множество действительных чисел R бесконечно, тогда:

1. На R для любого значения f(x) найдётся соответствующий x - функция f сюръективна.
2. При x1 ≠ x2 всегда будет выполняться f(x1) ≠ f(x2), поскольку x1 + 1 ≠ x2 + 1, - функция f инъективна.

Тогда функция f(x) биективна.

“Модуль” всегда возвращает только положительные значения при любых аргументах, поэтому:

1. Не существует такого x ∈ R, чтобы y ∈ R принял какое-либо отрицательное значение из множества R - g не сюръективна.
2. Доказательство от противного. Подберём такой пример, чтобы инъективность не соблюдалась: g(1) = |1| = 1 = |-1| = g(-1). Так как 1 ≠ -1, а g(1) = g(-1), - g не инъективна.

Итак, функция g(x) не сюръективна, не инъективна, а значит и не биективна.

Функция нескольких переменных

Если множество X представляет собой декартово произведение n множеств X = X1 × X2 × … × Xn, то отображение f: X → Y называется n-местным отображением (функцией n переменных).

Элементы x1 ∈ X1, x2 ∈ X2, …, xn ∈ Xn упорядоченного набора x = (x1, x2, … , xn) называются аргументами функции n переменных.

В таком случае запись y = f(x) эквивалентна y = f(x1, x2, … , xn).

Пример функции двух переменных: f: R × R → R, f(x,y) = x + y - числовая функция суммы двух значений.

Композиция функций

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

Композицией (суперпозицией) функций f: X → Y и g: Y → Z называется такая функция (g ○ f): X → Z, что для любых элементов x ∈ X, z ∈ Z существует связь (g ○ f)(x) = z тогда и только тогда, когда существует элемент y ∈ Y такой, что одновременно существуют связи f(x) = y и g(y) = z.

Запись композиции функций f и g на языке символов: ∀x∈X,∀z∈Z: [(g ○ f)(x) = z] ⇔ ∃y∈Y: [f(x) = y]∧[g(y) = z].

Можно заметить, что при композиции функций f и g результат выполнения функции f передаётся аргументом в функцию g, то есть g(f(x)) = z.

Тогда определение упрощается: композицией называется функция (g ○ f): X → Z, определённая равенством: (g ○ f)(x) = g(f(x)), x ∈ X.

Запись g ○ f читается как «g после f».

Таким образом, с помощью композиции сложные действия можно представлять как последовательность (цепочку) простых действий.

Композиция большего числа функций составляется аналогично. Если добавить в неё ещё одну функцию h: Z → P, то (h ○ g ○ f)(x) = h(g(f(x))), x ∈ X.

Например, составную функцию h(z) = 3z + 2 можно представить как композицию двух простых функций f(x) = 3x и g(y) = y + 2.

Композиция функций некоммутативна: (g ○ f) ≠ (f ○ g). Порядок следования функций имеет значение: f(g(x) ≠ g(f(x)).

На примере выше несложно показать некоммутативность композиции: f(g(1)) = 3 • (1 + 2) = 9, g(f(1)) = (3 • 1) + 2 = 5.

Композиция функций ассоциативна: h ○ g ○ f = (h ○ g) ○ f = h ○ (g ○ f).

Композицию интуитивно можно использовать и в других областях, если рассматривать функцию как некоторое действие. Например, регистрация пользователя может состоять из композиции следующих действий (функций): проверки правильности ввода данных, проверки существования пользователя в базе данных, создания нового пользователя в базе данных.

Индикаторная функция

Пусть имеется некоторое множество A и некоторое его подмножество B ⊆ A.

Индикаторной функцией (англ. indicator function), индикатором или характеристической функцией (англ. characteristic function) подмножества B множества A называют дискретную функцию, определенную на множестве A, которая указывает принадлежность элемента x ∈ A к подмножеству B следующим образом:

1. Функция возвращает значение 1 для аргумента x, если значение аргумента принадлежит B.
2. Функция возвращает значение 0 для аргумента x, если значение аргумента не принадлежит B.

Индикаторную функцию обозначают символами I, χ или 1.

Формальное определение индикаторной функции: I: A → { 0, 1 }, B ⊆ A,

I(x) = {
  1, x ∈ B;
  0, x ∉ B;
}

Если B = A, то I(x) ≡ 1 (индикаторная функция тождественно равна единице, то есть её значение равно 1 для любого аргумента x). Если B = ∅, то I(x) ≡ 0 (индикаторная функция тождественно равна нулю).

Например, если A = { 3, 1, 7 }, B = { 1, 7 } то I(3) = 0, I(1) = I(7) = 1.

Углубленно об операции

• Определение операции и обозначения
• Бинарная операция и формы её записи
• Свойства бинарных операций
• Унарная операция, её формы и свойства
• Cвойства операций над множествами
• Приоритет и очерёдность операций

Определение операции и обозначения

Операция (operation) - это функция, которая принимает любое количество входных значений (input values) и имеет чётко определённое выходное значение (output value).

Фактически, определение операции совпадает с определением функции нескольких переменных. Главным различием между ними выступает обозначение: операции обозначаются специальными символами, имеют свои формы записи и способы передачи аргументов.

Пусть имеется n непустых множеств X1, X2, …, Xn. Тогда если множество X представляет собой декартово произведение этих множеств X = X1 × X2 × … × Xn, то отображение f: X → Y называется n-арной операцией.

Входные значения x1 ∈ X1, x2 ∈ X2, …, xn ∈ Xn называют аргументами (arguments) операции или операндами (operands), выходное значение y ∈ Y называют результатом операции (operation result).

Говорят, что операция f совершается над своими операндами.

В отличие от функций и отношений, каждая операция имеет своё уникальное символьное представление (иногда используется несколько символов). Например, операция сложения обозначается знаком +; операция умножения - знаками •, *, ×; логическое отрицание - знаком ¬ и так далее.

Например, выражение 1 + 3 = 4 целиком является операцией, 1 и 3 - операндами, 4 - результатом выполнения операции.

Символ, использующийся в операции (например, +), называют оператором (operator). В отличии от операции, оператор может менять своё предназначение в зависимости от типа операндов. Например, в математике произведение чисел и произведение множеств - это совершенно разные операции, использующие один бинарный оператор ×. В программировании аналогичным примером могут послужить сложение чисел и сложение (конкатенация) строк - разные операции, один бинарный оператор +.

Количество операндов n называют арностью (arity) операции.

При n = 0 операция является константой: f() = 3 или y = 3.

При n = 1 операция называется унарной (unary), при n = 2 - бинарной (binary, лат. bi - “два"), при n = 3 - тернарной (ternary) и так далее.

Абсолютное большинство операций - унарные и бинарные, поэтому мы уделим им особое внимание.

Напоследок хочется сказать, что в каждой области знаний изучаются и используются свои операции. В программировании - арифметические, логические и строковые операции, в математическом анализе - операции дифференцирования и интегрирования и так далее.

Бинарная операция и формы её записи

Говоря простыми словами, бинарная операция (двумеестная операция) — операция, которая принимает два аргумента и возвращающая один результат.

Пусть имеется три непустых множества A, B , C. Бинарной операцией на паре A, B со значениями в C называется отображение f: A × B → C.

Пусть имеется непустое множество A. Тогда бинарной операцией на множестве A называют отображение f: A × A → A.

Самой распространённой формой записи бинарных операций является инфиксная форма - такая, при которой символ операции (например, ◇), ставится между её операндами: x ◇ y.

Тем не менее существуют также префиксная запись (польская нотация), где символ операции ставится перед её операндами: ◇ x y, и постфиксная запись (обратная польская нотация), где символ операции ставится после её операндов: x y ◇.

Свойства бинарных операций

Как разновидность отношения, операция может обладать или не обладать некоторыми свойствами, которые определяют её поведение.

Тем не менее, свойства операций несколько отличаются от свойств отношений. Это связано с тем, что обычно у отношений нет результата x R y (например, x - потомок y), а у операций есть результат x ◇ y = z (например, 4 • 5 = 20). Таким образом, свойства операций будут строятся вокруг знака равенства.

Для рассмотрения свойств условно обозначим произвольную операцию символом ◇, ещё одну операцию (при её необходимости) обозначим символом ◆.

1. Идемпотентность — такое свойство операции, при которотом повторное применение операции не имеет никакого эффекта. Например, операции ∩, ∪ идемпотентны: повторное пересечение или объединение с тем же множеством не даст эффекта (A ∩ B = A ∩ B ∩ B).
2. Коммутативность (переместительное свойство) — такое свойство операции, при котором порядок следования операндов неважен: x ◇ y = y ◇ x. Например, операция сложения коммутативна: 1 + 7 = 7 + 1 = 8.
3. Антикоммутативность — такое свойство операции, при котором (x ◇ y) = -(y ◇ x). Например, операция вычитания антикоммутативна: 8 − 1 = −(1 − 8) = 7.
4. Ассоциативность (сочетательное свойство) — такое свойство операции, при котором результат последовательного применения операции (x1 ◇ x2 ◇ … ◇ xn) не зависит от очерёдности вычисления, то есть расстановка скобок не имеет эффекта и скобки можно опустить: (x ◇ y) ◇ z = x ◇ (y ◇ z) = x ◇ y ◇ z. Например, операция сложения ассоциативна: (3 + 2) + 2 = 3 + (2 + 2) = 3 + 2 + 2 = 7.
5. Дистрибутивность (распределительное свойство). Операция ◆ - дистрибутивна относительно операции ◇, если выполняется (x ◇ y) ◆ z = x ◆ z ◇ y ◆ z. Например, операция умножения дистрибутивна относительно операции сложения: (1 + 7) • 3 = 1 • 3 + 7 • 3 = 24.

Унарная операция, её формы и свойства

Пусть имеется непустое множество A. Унарной операцией на множестве A называется отображение f: A → A.

Унарная операция может быть префиксной ◇ x и постфиксной x ◇.

От формы унарной операции зависят смысл и результат операции, поэтому сменять её нельзя - форма унарной операции фиксирована. Например, x! - факториал в математике, !x - логическое отрицание в программировании; в программировании ++x - инфиксный инкремент, x++ - постфиксный инкремент, --x - инфиксный декремент, x-- - постфиксный декремент.

Унарная операция из перечисленных ранее свойств бинарных операций может обладать лишь свойством идемпотентности: ◇ x = ◇ (◇ x). Например, модуль числа идемпотентен: |-1| = ||-1|| = |||-1||| = 1.

Очевидно, что логическое отрицание не идемпотентено: ¬x ≠ ¬¬x, впрочем как и унарный минус: -1 ≠ -(-1).

Приоритет и очерёдность операций

Приоритет операции - формальное свойство операции, которое влияет на очередность выполнения данной операции в выражении с несколькими различными операциями при отсутствии явного указания (с помощью круглых скобок) на порядок их выполнения. Пример такого выражения: x ◆ y ◇ z. Приоритет влияет на то, что выполнится в первую очередь: x ◆ y или y ◇ z.

Очерёдность операций (the order of operations) - набор правил, определяющий последовательность (очерёдность) выполнения операций. Другими словами, эти правила определяют (задают) приоритет операций.

Очерёдность арифметических операций в науках и большинстве языков программирования:

1. Возведение в степень (x^z) и извлечение корня (√x).
2. Умножение (x • y) и деление (x / y).
3. Сложение (x + y) и вычитание (x - y).

Чем выше по списку находится операция, тем выше её приоритет и тем раньше она выполнится в выражении.

Например, в выражении 7 • 3^2 + 1 сначала выполнится 3^2 = 9, затем 7 • 9 = 63 и только затем 63 + 1 = 64.

Чтобы явно указать порядок выполнения операций (повысить приоритет какой-то операции), можно использовать групприровку операций при помощи круглых скобок (). Тогда первым выполнится та операция, которая находится в скобках. Например, в выражении (3 + 2) • 2 первым выполнится сложение 3 + 2 = 5, а затем умножение 5 • 2 = 10 несмотря на то, что изначально у умножения приоритет был выше.

Если несколько операций имеют одинаковый приоритет, то они выполняются слева направо. Например, умножение и деление имеют одинаковый приоритет, поэтому в выражении 6 / 3 • 7 сперва выполнится операция слева 6 / 3 = 2, а затем операция справа 2 • 7 = 14.

С операциями, которых нет в списке выше, всё аналогично: в тех областях, где эти операции применяются, создаются похожие списки - в противном случае операции выполняются последовательно, слева направо.

В программировании определение ассоциативности операции немного отличается. Ассоциативность (в программировании) — свойство операций, позволяющее восстановить последовательность (очерёдность) их выполнения в выражении с несколькими различными операциями при одинаковом приоритете операций и отсутствии явных указаний (при помощи круглых скобок) на очерёдность их выполнения. Различают левую и правую ассоциативность. При левой ассоциативности вычисление выражения происходит слева направо, а при правой ассоциативности — справа налево.

Теория мультимножеств

• Мультимножество
• Основные понятия теории мультимножеств
• Число мультимножеств
• Отношения между мультимножествами
• Операции над мультимножествами

Мультимножество

Понятие мультимножества получено исключением из понятия множества требования уникальности элементов.

Мультимножеством (англ. multiset, bag) называют неупорядоченный набор объектов (не обязательно уникальных), обладающих схожими признаками.

Обозначение мультимножества совпадает с обозначением множества. Примеры мультимножеств: { 3, 2, 2 }, { белый, красный, белый }.

Основные понятия теории мультимножеств

• Множественность элемента
• Представление мультимножества как множества
• Функция множественности
• Принадлежность элемента мультимножеству
• Мощность (кардинальность) мультимножества
• Саппорт мультимножества

Множественность элемента

Множественностью (англ. multiplicity) элемента x в мультимножестве A называется число вхождений элемента x в мультимножество A.

Например, в мультимножестве { x, x, y, z, z, z }: элемент x имеет множественность 2, элемент y - множественность 1, элемент z - множественность 3.

Представление мультимножества как множества

Мультимножество можно определить как множество особой структуры.

Мультимножеством A называют множество упорядоченных пар (x, m(x)) вида { (x1, m(x1)), (x2, m(x2)), ..., (xn, m(xn)) }, где x - элемент мультимножества, а m(x) - множественность элемента x.

При таком определении мультимножества, мультимножество { x, x, y, z, z, z } можно представить в виде { (x, 2), (y, 1), (z, 3) }, что достаточно удобно.

Существует другое, интуитивное обозначение: { x1^m(x1), x2^m(x2), ..., xn^m(xn) }. Пример: { x, x, y, z, z, z } = { x^2, y, z^3 }.

Функция множественности

Функция m(x), отображающая элементы мультимножества в целые неотрицательные числа (m: A → Z+), называется функцией множественности (англ. multiplicity function).

Добавим дополнительный аргумент в функию множественности: m(x, A), где A - название мультимножества, которому принадлежит элемент x. Это позволит нам различать множественность одних и тех же элементов в разных множествах и при этом не задавать каждый раз новую функцию (m: A → Z+, m: B → Z+ и так далее)

Например, если A = { y, y, y } и B = { x, y }, тогда m(y, A) = 3, m(y, B) = 1, m(x, A) = 0, m(x, B) = 1.

Принадлежность элемента мультимножеству

Элемент x принадлежит мультимножеству (содержится в мультимножестве) A, если m(x, A) > 0. Обозначение: x ∈ A.

Элемент x не приналежит мультимножеству (не содержится в мультимножестве) A, если m(x, A) = 0. Обозначение: x ∉ A.

Мощность (кардинальность) мультимножества

Мощностью или кардинальностью (англ. cardinality) мультимножества A называют число всех элементов мультимножества A, включающее так же все повторения этих элементов. Иначе говоря, кардинальностью называют сумму множественностей всех элементов мультимножества A: |A| = Σ m(x,A), x ∈ A.

Кардинальность мультимножества A обозначается: |A| = z, где z - неотрицательное целое число.

Например, мультимножество A = { y, z, x, y, z } имеет кардинальность |A| = m(x) + m(y) + m(z) = 1 + 2 + 2 = 5.

Саппорт мультимножества

Саппортом (англ. support) мультимножества A называют множество уникальных элементов мультимножества A.

Обозначение саппорта мультимножества A:
Supp(A) = { x ∈ U ∣ m(x, A) > 0 }.

Пусть A = { x, x, x, y, y, z }, тогда его саппорт: Supp(A) = { x, y, z }.

Число мультимножеств

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

Например, для множества { x } существует бесконечное число мультимножеств: { x, x }, { x, x, x }, { x, x, x, ..., x }.

Число мультимножеств (англ. multiset number) мощности k, состоящих из элементов некоторого множества A мощности n обозначается (( n k )) и равняется числу подмножеств мощности k в некотором множестве мощности n + k - 1, то есть:
(( n k )) = C(n + k - 1, k) = (n + k - 1)! ÷ (k!(n - 1)!).

Обозначение (( n k )) читается как “множественный выбор k из n” (англ. n multichoose k).

Например, если A = { ежевика, голубика, черника }, тогда (( 3 2 )) = C(4, 2) = 4! ÷ (2!2!) = (3 • 4) ÷ 2 = 6 мультимножеств: { ежевика, ежевика }, { ежевика, голубика }, { ежевика, черника }, { голубика, голубика }, { голубика, черника }, { черника, черника }.

Отношения между мультимножествами

Пересечение мультимножеств

Мультимножества A и B пересекаются, если они имеют одинаковые элементы и не обязательно одинаковые множественности этих элементов.

Равенство мультимножеств

Мультимножеств A и B равны , если совпадают все элементы этих мультимножеств, а также множественности каждого отдельно взятого элемента, в противном случае мультимножества A и B не равны.

Включение мультимножества

Говорят, что мультимножество A включено в мультимножество B (англ. A included in B), если Supp(A) ⊆ Supp(B) и для любого элемента x ∈ A выполняется m(x, A) <= m(x, B), то есть если каждый элемент x мультимножества A содержится в мультимножестве B и его множественность в A меньше, чем в B.

Существует так же краткая версия определения с использованием универсального множества U.

Говорят, что мультимножество A включено в мультимножество B, если для любого элемента x ∈ U выполняется m(x, A) <= m(x, B), то есть множественность любого элемента универсального множества в A меньше, чем в B.

Обозначение включения A в B: A ⊆ B.

Например, если A = { x, y }, B = { x, z }, C = { x, y, x }, то A ⊆ C.

Для любого мультимножества A выполняется Supp(A) ⊆ A.

Операции над мультимножествами

• Пересечение мультимножеств
• Объединение мультимножеств
• Сложение мультимножеств

Пересечение мультимножеств

Пересечением (англ. intersection) мультимножеств A и B называют такое мультимножество C, что для любого элемента x ∈ U выполняется m(x, C) = min{ m(x, A), m(x, B) }.

Например, A = { x, y, y } в пересечении с B = { x, x, y, z } даёт C = { x, y }.

A: { (x, 1), (y, 2), (z, 0) }
B: { (x, 2), (y, 1), (z, 1) }
C: { (x, 1), (y, 1), (z, 0) }

Объединение мультимножеств

Объединением (англ. union) мультимножеств A и B называют такое мультимножество C, что для любого элемента x ∈ U выполняется m(x, C) = max{ m(x, A), m(x, B) }.

Например, A = { x, y, y } в объединении с B = { x, x, y, z } даёт C = { x, x, y, y, z }.

A: { (x, 1), (y, 2), (z, 0) }
B: { (x, 2), (y, 1), (z, 1) }
C: { (x, 2), (y, 2), (z, 1) }

Сложение мультимножеств

Сложением (англ. sum) мультимножеств A и B называют такое мультимножество C, что для любого элемента x ∈ U выполняется m(x, C) = m(x, A) + m(x, B).

Например, A = { x, y, y } при сложении с B = { x, x, y, z } даёт C = { x, x, x, y, y, y, z }.

A: { (x, 1), (y, 2), (z, 0) }
B: { (x, 2), (y, 1), (z, 1) }
C: { (x, 3), (y, 3), (z, 1) }

Теория графов

Понятие графа

Графом G (англ. graph) называют такую упорядоченную пару (V, E), в которой компонента V - это некоторое конечное (счётное) непустое множество, состоящее из объектов произвольной природы, а комнонента E - множество неупорядоченных пар { x, y }, состоящих из элементов x, y, принадлежащих множеству V (причём не обязательно различных).

Формально определение графа G можно записать вот так:

1. G = (V, E).
2. V ≠ ∅.
3. |V| ≠ ∞.
4. E = { { x, y } } : x, y ∈ V.

Множество V называют множеством вершин (множеством узлов) графа G, а его элементы - вершинами (англ. vertices), узлами (англ. nodes).

Обозначение множества вершин V графа G: V(G).

Множество E называют множеством рёбер графа G, а его элементы - рёбрами (англ. edges).

Обозначение множества рёбер E графа G: E(G).

Обозначение графа G c множеством вершин V и множеством рёбер E: G(V, E).

Объекты, являющиеся элементами множества V (вершинами), могут преставлять собой что угодно - это не имеет значения. Важно лишь, чтобы эти объекты обладали парными связями. Например, вершинами могут выступать точки на карте, тогда наличие дуги (связи) между двумя вершинами может означать наличие маршрута между двумя заданными точками на карте.

В примерах и задачах для простоты в качестве вершин графа используют натуральные числа (1, 2, 3, ...), подразумевая при этом, что вместо чисел может быть что угодно.

Пример графа G(V, E):

V = { 1, 2, 3 }

V × V = {
  (1, 1), (1, 2), (1, 3),
  (2, 1), (2, 2), (2, 3),
  (3, 1), (3, 2), (3, 3)
}

E = { (1, 3), (2, 1), (3, 2) }

Математическая логика

• Высказывание и истинностные значения
• Квантор всеобщности и квантор существования
• Логические операции

Высказывание и истинностные значения

Высказывание (логическое высказывание) - предложение, о котором можно сказать, что оно истино или ложно.

Например, высказывание «Луна вращается вокруг Земли.» является истиным, а высказывание «Я никогда не перестану любить тебя.» - ложным ;)

Высказываниями могут быть только повествовательные предложения, но никак не побудительные («Выходи гулять.») и не вопросительные («Для кого я это пишу?»), поскольку их истинность невозможно оценить.

Также не могут быть высказываниями те повествовательные предложения, об истинности которых мы ничего не можем сказать. Например, предложение «Зима будет холодной» не является высказыванием, поскольку не хватает информации, чтобы подтвердить или опровергнуть его. Предложение x < 3 так же не является высказыванием, поскольку недостаточно информации об x.

Высказывания обозначаются малыми латинскими буквами (a-z). Например, p - «Рыбы не умеют ходить.».

Истинность высказывания передаётся логической единицей 1 (истина), ложность - логическим нулём 0 (ложь). Данные значения называют истинностными (логическими) значениями высказывания.

Истинностное значение является основной характеристикой высказывания.

Условимся, что высказывание не может быть истино и ложно одновремено, то есть мы будем рассматривать только двоичную (бинарную) логику.

Истинность высказывания p обозначается: |p| = 1, ложность: |p| = 0.

Квантор всеобщности и квантор существования

Квантор всеобщности ∀ (перевёрнутое английское “A” - "all") — это условие, которое выполняется для всех указанных элементов.

Символ ∀ читается как “для всех…”, “для любого…”, “для каждого…”, а также “все…”, “любой…” и “каждый…”.

Выражение (∀x ∈ X)P(x) читается как “каждый (всякий, любой) x из множества X обладает свойством P(x)” или “для любого x из множества X справедливо (выполняется) P(x)”.

Символ : читается как “такого (таких), что".

Пример: ∀x ∈ X: x > 0 - “Всякий x из множества X такой, что x > 0”.

Квантор существования ∃ (перевёрнутое английское “E” - “exist") - это условие, которые выполняется хотя бы для одного из указанных элементов.

Символ ∃ читается как “существует”, “некоторый” или “для некоторого”.

Выражение (∃y ∈ Y)Q(y) читается как “некоторый y из множества Y обладает свойством Q(y)” или “существует y из множества Y справедливо (выполняется) Q(y)”.

Квантор существования гарантирует существование, но не единственность элемента (что часто требуется в доказательствах теормем), поэтому существует его модификация: запись ∃! читается как “существует единственный”.

Логические операции

Рекомендуется почитать: «Углубленно об операциях».

• О логических операциях
• Логическое повторение
• Логическое отрицание
• Конъюнкция
• Дизъюнкция
• Штрих Шеффера
• Стрелка Пирса
• Эквивалентность
• Сложение по модулю два
• Прямая импликация
• Обратная импликация
• Декремент
• Инкремент
• Свойства логических операций

О логических операциях

Булево множество - двухэлементное множество { 0, 1 } или { ложь, истина }.

Логическая операция - это операция над элементами булева множества B.

Все логические операции - унарные или бинарные.

Унарная логическая операция имеет один операнд (аргумент) и один результат.

Унарные логические операции:

• Логическое повторение
• Логическое отрицание

Бинарная логическая операция имеет два операнда (аргумента) и один результат.

Бинарные логические операции:

• Конъюнкция
• Дизъюнкция
• Штрих Шеффера
• Стрелка Пирса
• Эквивалентность
• Сложение по модулю два
• Прямая импликация
• Обратная импликация
• Декремент
• Инкремент

Логическое повторение

Логическое повторение (логическое “да”) - унарная операция, которая возвращает в качестве результата входное значение x.

x	x (буферизованное)
0	0
1	1

Это самая простая логическая операция, которую параметрически можно задать так:

x (буферизованное) = {
   1, если x = 1;
   0, если x = 0;
}

В программировании с помощью логического повторения реализуется повторитель.

Логическое отрицание

Логическое отрицание (логическое “не”, инверсия) ¬x (NOT x) — унарная операция, которая меняет значение x ∈ { 0, 1 } на противоположное, то есть преобразует 0 в 1, а 1 в 0.

x	¬x
0	1
1	0

Запись ¬x читается как “не x”.

Параметрически логическое отрицание можно записать так:

¬x = {
   1, если x = 0;
   0, если x = 1;
}

Закон двойного отрицания: ¬¬x = x.

В программировании логическое отрицание обозначают символом !: !true = false.

В программировании с помощью логического отрицания реализуется инвертор.

Конъюнкция

Конъюнкция (логическое “и”, логическое умножение) x ∧ y (x & y, x AND y) - бинарная операция, которая возвращает истинное значение тогда и только тогда, когда её оба операнда (x и y) истинны.

x	y	x ∧ y
0	0	0
0	1	0
1	0	0
1	1	1

Запись x ∧ y читается как “x и y.

Параметрически конъюнкцию можно представить так:

x ∧ y = {
   1, если x = 1 и y = 1;
   0, иначе;
}

В программировании логическое “и” обозначается: x && y.

Дизъюнкция

Дизъюнкция (логическое “или”, логическое сложение) x ∨ y (x OR y) - бинарная операция, которая возвращает истинное значение тогда и только тогда, когда хотя бы один из её операндов x или y содержит истинное значение.

x	y	x ∨ y
0	0	0
0	1	1
1	0	1
1	1	1

Запись x ∨ y читается как “x или y.

Параметрически дизъюнкцию можно представить так:

x ∨ y = {
   1, если x = 1 или y = 1;
   0, иначе;
}

В программировании логическое “или” обозначается: x || y.

Штрих Шеффера

Штрих Шеффера (операция “и-не”, инверсия конъюнкции) x ∣ y (x NAND y) - бинарная операция, которая возвращает истинное значение тогда и только тогда, когда один из её операндов x или y ложен.

x	y	x ∣ y
0	0	1
0	1	1
1	0	1
1	1	0

Параметрически штрих Шеффера можно представить так:

x ∣ y = {
   1, если x = 0 или y = 0;
   0, иначе;
}

Стрелка Пирса

Стрелка Пирса (операция “или-не”, инверсия дизъюнкции) x ↓ y (x NOR y) - бинарная операция, которая возвращает истинное значение тогда и только тогда, когда оба её операнда (x и y) ложны.

x	y	x ↓ y
0	0	1
0	1	0
1	0	0
1	1	0

Параметрически стрелку Пирса можно представить так:

x ↓ y = {
   1, если x = 0 и y = 0;
   0, иначе;
}

Эквивалентность

Эквивалентность (исключающее “или-не”, логическая равнозначность, эквиваленция, тождество) x ↔ y (x ~ y, x ≡ y, x XNOR y) - бинарная операция, которая возвращает истинное значение тогда и только тогда, когда значения операндов x и y совпадают.

x	y	x ↔ y
0	0	1
0	1	0
1	0	0
1	1	1

Параметрически эквивалентность можно представить так:

x ↔ y = {
   1, если x = y;
   0, иначе;
}

Сложение по модулю два

Сложение по модулю два (исключающее “или”, неравнозначность, инверсия равнозначности) x ⊕ y (x XOR y) - бинарная операция, которая возвращает истинное значение тогда и только тогда, когда значения операндов x и y не совпадают.

x	y	x ⊕ y
0	0	0
0	1	1
1	0	1
1	1	0

Параметрически сложение по модулю два можно представить так:

x ⊕ y = {
   1, если x ≠ y;
   0, иначе;
}

Прямая импликация

Прямая импликация (импликация от x к y, инверсия декремента) x → y - бинарная операция, которая возвращает истинное значение тогда и только тогда, когда значение операндов x и y удовлетворяют условию: x ≤ y.

x	y	x → y
0	0	1
0	1	1
1	0	0
1	1	1

Логический смысл импликации от x к y: если из x следует y и x истинно, то y не может быть ложно, поэтому выражение x → y при таких значениях операндов ложно.

Параметрически импликацию от x к y можно представить так:

x → y = {
   1, если x ≤ y;
   0, иначе;
}

Обратная импликация

Обратная импликация (импликация от y к x, инверсия инкремента) x ← y - бинарная операция, которая возвращает истинное значение тогда и только тогда, когда значение операндов x и y удовлетворяют условию: x ≥ y.

x	y	x ← y
0	0	1
0	1	0
1	0	1
1	1	1

Логический смысл импликации от y к x: если из y следует x и y истинно, то x не может быть ложно, поэтому выражение x ← y при таких значениях операндов ложно.

Параметрически импликацию от y к x можно представить так:

x ← y = {
   1, если x ≥ y;
   0, иначе;
}

Декремент

Декремент (запрет импликации по y, инверсия прямой импликации) x ↛ y - бинарная операция, которая возвращает истинное значение тогда и только тогда, когда значение операндов x и y удовлетворяют условию: x > y.

x	y	x ↛ y
0	0	0
0	1	0
1	0	1
1	1	0

Параметрически декремент можно представить так:

x ↛ y = {
   1, если x > y;
   0, иначе;
}

Не путать с декрементом в программировании - унарной операцией, которая уменьшает текущее значение переменной x на единицу: x-- или --x.

Инкремент

Инкремент (запрет импликации по x, инверсия обратной импликации) x ↛ y - бинарная операция, которая возвращает истинное значение тогда и только тогда, когда значение операндов x и y удовлетворяют условию: x < y.

x	y	x ↚ y
0	0	0
0	1	1
1	0	0
1	1	0

Параметрически инкремент можно представить так:

x ↚ y = {
   1, если x < y;
   0, иначе;
}

Не путать с инкрементом в программировании - унарной операцией, которая увеличивает текущее значение переменной x на единицу: x++ или ++x.

Свойства логических операций

Рекомендую прочитать: «Свойства бинарных операций”.

Соберём все свойства и законы в одном месте:

1. Идемпотентность: x ◇ x = x , ◇ ∈ { ∧, ∨ }.
2. Коммутативность: x ◇ y = y ◇ x , ◇ ∈ { ∧, ∨, ⊕, ∼, ∣ , ↓ }.
3. Ассоциативность: (x ◇ y) ◇ z = x ◇ (y ◇ z) , ◇ ∈ { ∧, ∨, ⊕, ∼ }.
4. Дистрибутивность

• конъюнкции относительно дизъюнкции: x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z).
• конъюнкции относительно сложения по модулю два: x ∧ (y ⊕ z) = (x ∧ y) ⊕ (x ∧ z).
• дизъюнкции относительно конъюнкции: x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z).

5. Инволютивность отрицания (закон снятия двойного отрицания): ¬¬x = x.
6. Дополнительность:

• a ∧ ¬a = 0,
• a ∨ ¬a = 1.

7. Законы де Моргана:

• ¬(x ∧ y) = ¬x ∨ ¬y,
• ¬(x ∨ y) = ¬x ∧ ¬y.

8. Законы поглощения:

• x ∧ (x ∨ y) = x,
• x ∨ (x ∧ y) = x.

9. Свойства констант 0 и 1:

• ¬0 = 1,
• ¬1 = 0,
• a ∧ 0 = 0,
• a ∧ 1 = a,
• a ∨ 0 = a,
• a ∨ 1 = 1.

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

• О комбинаторике и её объектах
• Чем может быть интересна комбинаторика
• Простейшие комбинаторные задачи
• Основные комбинаторные правила и принципы
• Сочетания
• Перестановки
• Размещения
• Партиция и композиция натуральных чисел
• Метод “звёзды и столбцы” (stars and bars)

О комбинаторике и её объектах

Комбинаторика (англ. Combinatorics) занимается подсчётами количества (числа) элементов во всевозможных наборах элементов (упорядоченных и неупорядоченных, с уникальными и с повторяющимися элементами).

Элементы рассматриваемого набора чаще всего выбираются из некоторого множества или мультимножества, то есть набор представлен выборкой элементов (англ. selection) из некоторого множества (мультимножества).

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

Чем может быть интересна комбинаторика

Комбинаторика зародилась и получила своё развитие в те времена, когда были популярны азартные игры (карты, кости), ставки и лотереи, поэтому эти виды развлечений будут часто встречаться в условиях комбинаторных задач.

Если вы любитель подобных развлечений, то подсчёт различных комбинаций (вариантов) может быть вам не только интересен, но и полезен.

Тем не менее, развлечения - не единственная область применения комбинаторики.

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

Одно из применений комбинаторики: подсчёт количества информации (размера файла).

Простейшие комбинаторные задачи

• Задача #1 (достань карандаш)
• Задача #2 (достань шарик)
• О формулировках комбинаторных задач

Рассмотрим пару простых задач.

Задача #1 (достань карандаш)

«В коробке лежит 4 разноцветных карандаша. Сколько способов достать один любой карандаш?»

Ответ

4

Объяснение

Пусть в коробке лежали красный, синий, зелёный и жёлтый карандаши, тогда мы можем достать либо красный, либо синий, либо зелёный, либо жёлтый карандаш.

Задача #2 (достань шарик)

«В мешке лежит 3 белых, 2 зелёных и 2 красных шарика. Сколько способов достать один белый шарик?»

Ответ

3

Объяснение

В мешке лежит 3 белых шарика, значит можно достать каждый из них.

О формулировках комбинаторных задач

Хочется ещё раз отметить на примерах выше, что сам класс объектов не важен в комбинаторных задачах. В задачах #1, #2 (как и во многих последующих) могли быть использованы любые другие объекты.

Например, следующая задача эквивалентна задаче #1:
«В мешочке лежит 3 различных бочонка для лото. Сколько способов достать один бочонок?»

А задача ниже эквивалентна задаче #2:
«В колоде лежит 3 туза, 2 короля и 2 дамы. Сколько способов достать один туз?»

Основные комбинаторные правила и принципы

• Правило суммы (rule of sum)
• Правило произведения (rule of product)
• Принцип включений-исключений

Правило суммы (rule of sum)

«Если существует n способов совершить действие A и m способов совершить действие B, причём невозможно совершить оба действия вместе (одновременно), то существует n + m способов совершить действие А или В (либо A, либо B). »

Что значит «нельзя совершить оба действия одновременно»? Например, нельзя одновременно включить и выключить свет; нельзя одновременно встать, сесть и лечь - результаты этих действий несовместимы, не зависят друг от друга.

Для большего числа действий правило суммы работает аналогично. Например, если имеется действие C и k способов его совершить, то существует n + m + k способов совершить действие A или B или C при условии, что действия A, B, C нельзя совершить вместе.

Правило суммы на языке теории множеств

«Пусть имеется n взаимно непересекающиеся множеств A1, A2, ..., An (A1 ∩ A2 ∩ ... ∩ An = {}), тогда мощность их объединения равна сумме мощностей этих множеств:
|A1| + |A2| + ... + |An| = |A1 ∪ A2 ∪ ... ∪ An|.»

Задача #3 (достань карандаш ещё раз)

«В мешке лежит 3 белых, 2 зелёных и 2 красных шарика. Сколько способов достать один любой карандаш?»

Ответ

7

Объяснение

Число способов достать один белый карандаш: 3, один зелёный: 2, один красный: 2.

По правилу суммы: 3 + 2 + 2 = 7.

Правило произведения (rule of product)

«Если существует n способов совершить действие A и m способов совершить действие B, то существует n • m способов совершить действие А и В (оба действия одновременно). »

Для большего числа действий правило произведения работает аналогично. Например, если имеется действие C и k способов его совершить, то существует n • m • k способов совершить действие A и B и C.

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

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

«Пусть имеется n множеств A1, A2, ..., An, тогда мощность их декартова произведения равна произведению мощностей этих множеств:
|A1| • |A2| • ... • |An| = |A1 × A2 × ... × An|.»

Задача #4 (подбрось монетку)

«Монетку подбрасывают 5 раз подряд. Сколько возможных комбинаций может выпасть?»

Ответ

32

Объяснение

У монетки две стороны { орёл, решка } - 2 возможных исхода при одном (каждом) подбрасывании.

Совершаем одно и то же действие n = 2 способами m = 5 раз. По правилу произведения, имеем n^m = 2^5 = 32 способа сделать это.

Почему используется правило произведения, а не правило суммы? Пусть после первого броска выпал орёл и после второго выпала решка, и после третьего - орёл, и после четвёртого - решка. Именно и, а не или.

Задача #5 (сыграем в кости?)

«Подбрасываем кубик два раза подряд. Сколько возможных комбинаций может выпасть?»

Ответ

36

Объяснение

У кубика 6 граней с разных количеством точек на них { 1, 2, 3, 4, 5, 6 } - 6 возможных исходов при одном (каждом) броске.

Совершаем одно и то же действие n = 6 способами m = 2 раза. По правилу произведения, имеем n^m = 6^2 = 36.

Задача #6 (комбинации пароля)

«Сколько существует возможных комбинаций для составления 8-символьного пароля из букв латинского алфавита и цифр?»

Ответ

62^8

Объяснение

В латинском алфавите 26 заглавных (A-Z) и 26 прописных (a-z) букв, цифр всего 10 (0-9). И того существует 26 + 26 + 10 = 62 способа задать один символ пароля.

Тогда для того, чтобы задать 8 символов пароля, используем правило произведения: 62 • 62 • ... • 62 (8 раз) = 62^8.

Принцип включений-исключений

Принципом включений-исключений (англ. inclusion-exclusion principle) называется техника подсчёта мощности объединения n множеств | A1 ∪ A2 ∪ ... ∪ An | сложением мощностей всех множеств |A1| + |A2| + ... + |An| и исключением из этой суммы всего лишнего: элементы из пересечений некоторых множеств вошли в сумму несколько раз.

В простейшем случае, когда объединяются два множеств A и B, применение принципа включений-исключений имеет вид:
|A ∪ B| = |A| + |B| - |A ∩ B|.

Если множества A и B пересекаются, то каждое из множеств содержит в себе пересечение A ∩ B, которое при сложении |A| + |B| учитывается дважды и поэтому одно из пересечений необходимо исключить из рассчёта.

В случае трёх множеств A, B, C применение принципа включений-исключений имёт вид:
|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|.

Сперва включается всё, затем исключается всё лишнее (лишние пересечения), затем включается ошибочно исключённое.

Для большего числа множеств, например, A1, A2, ..., An алгоритм применения принципа включения-исключения следующий:

1. Включаем мощность кадого множества:
   |A1| + |A2| + ... + |An|.
2. Исключаем мощность каждого объединения двух множеств:
   - |A1 ∩ A2| - |A1 ∩ A3| - ....
3. Включаем мощность каждого объединения трёх множеств:
   + |A1 ∩ A2 ∩ A3| + |A1 ∩ A2 ∩ A4| + ....
4. Исключаем мощность каждого объединения четырёх множеств:
   - |A1 ∩ A2 ∩ A3 ∩ A4| - |A1 ∩ A2 ∩ A3 ∩ A5| - ...
5. И так далее включаем-исключаем-включаем-исключаем n раз.

Сочетания

• Сочетание
• Сочетание с повторениями

Сочетание

Сочетанием из n по k (англ. k-combination of a set A) называют неупорядоченный набор из k уникальных элементов, выбранных из некоторого множества A, содержащего n элементов. Каждый элемент множества A может попасть в одно сочетание только один раз. Другими словами, сочетанием из n по k называют всякое подмножество мощности k множества мощности n.

Поскольку понятие сочетания не отличается от понятия подмножества, будем обозначать сочетания как множества.

Число k не может превышать число n, так как элементы не могут повторяться: k <= n.

Например, если A = { 1, 3, 7 }, то сочетаниями из трёх по два являются неупорядоченные пары: { 1, 3 }, { 1, 7 }, { 3, 7 }.

Число сочетаний

Числом сочетаний из n по k (англ. number of k-combinations) называют количество всевозможных сочетаний для заданных параметров k (количество элементов в сочетании) и n (мощность множества A, из которого делается выборка).

Число сочетаний равнается биномиальному коэффициенту:
С(n,k) = n! ÷ ((n-k)!k!).

Пусть, например, множество A = { a, b, c, d }, тогда n = |A| = 4 и тогда:

1. C(0, 4) = 4! ÷ (4!0!) = 1 пустое сочетание: {}.
2. C(1, 4) = 4! ÷ (3!1!) = 4 одноэлементных сочетаний: { a }, { b }, { c }, { d }.
3. C(2, 4) = 4! ÷ (2!2!) = (3 • 4) ÷ 2 = 6 парных сочетаний: { a, b }, { a, c }, { a, d }, { b, c }, { b, d }, { c, d }.
4. C(3, 4) = 4! ÷ (1!3!) = 4 трёхэлементных сочетаний: { a, b, c }, { a, b, d }, { a, c, d }, { b, c, d }.
5. С(4, 4) = 4! ÷ (0!4!) = 1 сочетание, содержащее все элементы множества: { a, b, c, d }.
6. Проверка: 2^4 = C(0, 4) + C(1, 4) + C(2, 4) + C(3, 4) + C(4, 4), 1 + 4 + 6 + 4 + 1 = 16 = 2^4, значит посчитали правильно.

Например, в множестве из 7 элементов число сочетаний из трёх элементов равняется C(3, 7) = 7! ÷ (4!3!) = (5 • 6 • 7) ÷ (2 • 3) = 35.

Сочетание с повторениями

Сочетанием с повторениями из n по k (англ. k-combination with repetitions of a set A, k-multicombination of a set A) называют неупорядоченный набор из k элементов, выбранных (не обязательно единожды) из множества A, содержащего n элементов. Одни и те же элементы множества A могут выбираться несколько раз в одно сочетание с повторениями.

Фактически, сочетание с повторениями из n по k эквивалентно мультимножеству мощности k, состоящему из элементов множества мощности n. Поэтому будем обозначать сочетания с повторениями как мультимножества: { 3, 2, 2 }.

Число k может быть больше числа n, поскольку элементы могут повторяться.

Например, если множество A = { парень, девушка }, то сочетаниями с повторениями из двух по три являются: { парень, парень, парень }, { парень, парень, девушка }, { парень, девушка, девушка }, { девушка, девушка, девушка }.

Число сочетаний с повторениями

Числом сочетаний с повторениями из n по k (англ. number of combinations with repetitions) называют количество всевозможных сочетаний с повторениями для заданных параметров k (количество элементов в сочетании с повторениями) и n (мощность множества A, из которого делается выборка).

Число сочетаний с повторениями обозначается (( n k )) и выражается через биномиальный коэффициент:
(( n k )) = С(n+k-1,k) = (n+k-1)! ÷ ((n-1)!k!).

Например, в множестве из 7 элементов число сочетаний с повторениями из трёх элементов равняется C(3, 7 + 3 - 1) = C(3, 9) = 9! ÷ (6!3!) = (7 • 8 • 9) ÷ (2 • 3) = 84.

Задача (выбор героев в игре)

«В игре соперничают две команды. Сколько существует способов выбрать 5 героев из 100 возможных в одну команду и затем столько же героев в другую команду при условии, что один герой не может браться дважды?»

Ответ

С(100, 5) • С(95, 5)

Решение

Выбор 5 героев (уникальных объектов) из 100 - сочетание из 100 по 5, то есть C(100, 5).

Поскольку 5 героев уже выбрано и герои не могут повторяться, следующая команда выбирает из 100 - 5 = 95 героев, то есть C(95, 5).

Тогда, чтобы обе команды одновременно сделали выбор героев, используем правило произведения: С(100, 5) • С(95, 5).

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

• Перестановка множества
• Перестановка мультимножества
• Круговая перестановка

Перестановка множества

Перестановкой множества A (англ. permutation of a set A) называют упорядоченный набор, содержащий все элементы (без повторений) множества A в определённом порядке.

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

Перестановки удобно обозначать как кортежи, но они не являются кортежами из-за требования уникальности. Например, для множества A = { 3, 5, 7 } существуют перестановки: (3, 5, 7), (3, 7, 5), (5, 3, 7), (5, 7, 3), (7, 5, 3), (7, 3, 5).

Для обозначения переменных, содержащих перестановки, принято использовать малые буквы греческого алфавита: α, β, σ, τ, π. Например, σ = (5, 7, 3).

Перестановка как биекция

Иногда перестановку рассматривают как биективное отображение между элементами множества A и натуральными числами N (от 1 до мощности множества A), которые обозначают номер элемента в перестановке. Таким образом, каждому числу соответствует один элемент, а каждому элементу - одно число.

Например, в перестановке (снег, град, дождь) элементу дождь соответствует число 3, а числу 3 соответствует элемент дождь, но при этом в перестановке (дождь, град, снег) элементу дождь уже соответствует число 1.

Число перестановок множества

Числом перестановок множества A мощности n (англ. number of permutations of a set A) называют количество всех возможных перестановок множества A. Это число обозначают P(n) и оно равняется факториалу мощности множества A, то есть P(n) = n!.

Например, для множества A = { 8, 16, 32, 64 } существует P(4) = 4! = 1 • 2 • 3 • 4 = 24 возможных перестановки.

Перестановка мультимножества

Перестановкой мультимножества A (англ. multiset permutation) называют упорядоченный набор элементов конечного мультимножества A, в котором каждый элемент x мультимножества A встречается ровно столько раз, какова его множественность m(x) в мультимножестве A.

Например, перестановками мультимножества A = { x, x, y } являются наборы: (x, x, y), (x, y, x), (y, x, x).

Число перестановок мультимножества

Пусть мультимножество A содержит элементы x1, x2, ..., xk и множественности этих элементов равны m(x1), m(x2), ..., m(xk) соответственно, тогда |A| = m(x1) + m(x2) + ... + m(xk) = n и число перестановок мультимножества A равно n! ÷ (m(x1)! • m(x2)! • ... m(xk)!).

Например, если A = { x, y, x, z }, то |A| = m(x) + m(y) + m(z) = 2 + 1 + 1 = 4 = n и число перестановок мультимножества A равно n! ÷ (m(x)! • m(y)! • m(z)!) = 4! ÷ (2! • 1! • 1!) = 3 • 4 = 12.

Круговая перестановка

Обычно перестановки линейно упорядочены (англ. linearly ordered), то есть в каждой из них имеется первый, второй, третий, ..., n-ый (последний) элементы.

Тем не менее бывают случаи, когда реальные объекты расположены по кругу. Расположение таких объектов называется круговой перестановкой (англ. circular permutation).

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

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

Линейно упорядоченная перестановка может быть преобразована в круговую перестановку, если условиться, что за последним элементом линейной перестановки снова следует первый элемент этой перестановки (счёт зацикливается, каждый раз начинаясь сначала).

Например, линейно упорядоченная перестановка (красный, жёлтый, зелёный) может быть преобразована в круговую перестановку, тогда очерёдность элементов следующая: красный, жёлтый, зелёный, красный, жёлтый, зелёный, красный, ....

Эквивалентность круговых перестановок

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

То есть круговая перестановка (a, b, c) эквивалентна круговым перестановкам (c, a, b) и (b, c, a).

Число круговых перестановок

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

Например, число круговых перестановок множества { a, b, c } равно (3 - 1)! = 2! = 2: (a, b, c) и (a, c, b).

Например, число круговых перестановок множества { a, b, c, d } равно (4 - 1)! = 3! = 6:

(a, b, c, d),
(a, b, d, c),
(a, c, b, d),
(a, c, d, b),
(a, d, b, c),
(a, d, c, b).

Размещения

• Размещение
• Размещение с повторениями (слово в алфавите)

Размещение

Размещением из n по k (англ. k-permutation of n) называют упорядоченный набор, содержащий в определённом порядке k элементов (без повторений) некоторого множества A мощности n.

Размещения тоже будем обозначать как упорядоченные наборы: (1, 2, 3).

Например, если A = { a, b, c, d }, то n = |A| = 4 и размещения из 4 по 2:

(a, b), (b, a),
(a, c), (c, a),
(a, d), (d, a),
(b, c), (c, b),
(b, d), (d, b),
(c, d), (d, c).

Число размещений

Число размещений из n по k обозначается A(n, k) в русскоязычной литературе, P(n, k) в англоязычной литературе и равно A(n, k) = P(n, k) = n! ÷ (n - k)! = n • (n - 1) • ... • (n - k + 1).

Например, существует A(5, 3) = 5! ÷ 2! = 3 • 4 • 5 = 60 размещений из 5 по 2. Таким образом, в некотором множестве A = { a, b, c, d, e } можно выбрать и расставить 3 элемента 60-ю способами.

Связь между размещениями, комбинациями и перестановками

Понятие размещения является обобщением понятия перестановки: переставляются местами не все элементы множества A, а заданное количество k <= n этих элементов:
A(n, n) = P(n).

Между комбинациями, перестановками и размещениями существует связь.

Говоря простыми словами, размещение - это выбор k элементов из n и перестановка этих k элементов. То есть каждому размещению k элементов из n A(n, k) соответствует комбинация k элементов из n C(n, k) и некоторая перестановка выбранных k элементов P(k).

Учитывая сказанное выше , по правилу произведения имеем следущее выражение:
A(n, k) = C(n, k) • P(k)= n! ÷ ((n - k)! • k!) • k! = n! ÷ (n - k)!.

Размещение с повторениями (слово в алфавите)

Размещением с повторениями множества A (англ. permutation with repetitions of a set A) называют упорядоченный набор элементов множества A, в котором некоторые элементы множества A могут повторяться, использоваться несколько раз.

Например, для множества { x, y, z } существуют размещения с повторениями (x, z, y, x), (y, y, z) и так далее.

Понятие “размещение с повторениями” является частным случаем кортежа, все элементы которого принадлежат одному и тому же множеству.

Слово длины k в алфавите A

Само понятие “размещение с повторениями” используется довольно редко. Тем не менее но существует другое, более практичное понятие с тем же определением: слово длины k в алфавите A, состоящем из n символов.

Например, слова area, rare являются некоторыми из слов длины 4 в алфавите A = { a, e, r }.

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

Число размещений с повторениями длины k множества A мощности n или, что то же самое, число слов длины k в алфавите A мощности n равняется n^k.

Например, для множества A = { a, b, c } существует 3^2 = 9 размещений с повторениями длины k = 2: (a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c).

Например, для алфавита B = { h, e } существует 2^3 = 8 слов длины k = 3: hhh, hhe, heh, ehh, hee, eeh, ehe, eee.

Партиция и композиция натуральных чисел

• Партиция натурального числа
• Композиция натурального числа

Партиция натурального числа

Партицией натурального числа n (англ. partition of a positive integer n, integer partition) называют представление натурального числа n как суммы натуральных чисел, в которой порядок следования слагаемых не важен, то есть партиции 3 + 1 = 4 и 1 + 3 = 4 считаются одинаковыми.

Слагаемое в партиции называют частью (англ. part) этой партиции.

Например, для натурального числа n = 3 существует 4 партиции:

3
2 + 1 (или 1 + 2)
1 + 1 + 1

В партиции 2 + 1 слагаемые 2 и 1 называют частями этой партиции.

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

Для удобства партиции можно обозначать как мультимножества. Например, для натурального числа n = 4 существует 5 партиций: { 4 }, { 3, 1 }, { 2, 2 }, { 2, 1, 1 }, { 1, 1, 1, 1 }.

Число партиций натурального числа

Функцией партиций (англ. partition function) называют функцию p(n), которая принимает натуральное число n и возвращает число партиций, соответствующее числу n.

Не существует явной формулы, которая позволяет вычислить число партиций (значение функции p(n)) для произвольного n, но существуют рекуррентные соотношения, позволяющие сделать это их последовательным применением n раз.

Ниже представлены значения функции p(n) при значениях аргумента n от 1 до 10.

n	1	2	3	4	5	6	7	8	9	10
p(n)	1	2	3	5	7	11	15	22	30	42

Композиция натурального числа

Композицией натурального числа n (англ. composition of a positive integer n) называют представление натурального числа n как суммы натуральных чисел, в которой порядок следования слагаемых имеет значение, то есть композиции 3 + 1 = 4 и 1 + 3 = 4 считаются различными.

Например, для натурального числа n = 4 существует 7 композиций:

4,
3 + 1, 1 + 3,
2 + 1 + 1, 1 + 2 + 1, 1 + 1 + 2,
1 + 1 + 1 + 1.

Композицию числа можно рассматривать как упорядоченный набор с повторениями, поэтому её бывает удобно обозначать как кортеж. Например, обозначать композицию 1 + 3 как (1, 3), а 3 + 1 как (3, 1).

Будем называть слагаемое в композиции её компонентой (англ. component). Например, в композиции 1 + 3 слагаемое 1 - это первая компонента, а слагаемое 3 - вторая компонента.

Число композиций натурального числа

Число композиций натурального числа n (англ. number of compositions of a positive integer n) равно 2^(n - 1).

Слабая композиция

Слабой композицией натурального числа n (англ. weak composition of a positive integer n) называют представление натурального числа n как суммы целых неотрицательных чисел, то есть помимо натуральных чисел в качестве компоненты может использоваться ноль 0.

Для любого натурального числа существует бесконечно много различных слабых композиций (если не ограничить число компонент композиции). Например, 4 = 4 + 0 + 0 + ... + 0.

Например, слабые композиции натурального числа 3 из 2 компонент:

3 + 0, 0 + 3,
2 + 1, 1 + 2.

Например, слабые композиции натурального числа 3 из 3 компонент, представленные в виде кортежей:

(3, 0, 0), (0, 3, 0), (0, 0, 3),
(2, 1, 0), (2, 0, 1),
(1, 2, 0), (1, 0, 2),
(0, 2, 1), (0, 1, 2),
(1, 1, 1).

Метод “звёзды и столбцы” (stars and bars)

• О методе “звёзды и столбцы”
• Теорема #1 (число композиций натурального числа n из k компонент)
• Теорема #2 (число слабых композиций натурального числа n из k компонент)
• Решение задач методом “звёзды и столбцы”

О методе “звёзды и столбцы”

В комбинаторике “звёзды и столбцы” (англ. stars and bars) - это графический метод доказательства некоторых важных комбинаторных теорем, который получил широкое распространение благодаря Уильяму Феллеру.

Метод так же подходит для решения некоторых классических комбинаторных задач. Например, размещение k одинаковых шаров в n различных лунках.

Теорема #1 (число композиций натурального числа n из k компонент)

«Для любой пары натуральных чисел n и k число кортежей, состоящих из k натуральных чисел, сумма которых даёт n, то есть число композиций натурального числа n из k компонент (англ. number of k-compositions), равно числу подмножеств мощности k - 1, выбранных из множества мощности n - 1, то есть равно C(n-1, k-1).»

Например, для n = 5 и k = 2 существует C(n-1, k-1) = C(4, 1) = 4 композиции:

4 + 1
3 + 2
2 + 3
1 + 4

Например, для n = 5 и k = 3 существует C(n-1, k-1) = C(4, 2) = 6 композиций:

3 + 1 + 1
1 + 3 + 1
1 + 1 + 3
2 + 2 + 1
2 + 1 + 2
1 + 1 + 2

Доказательство методом “звёзды и столбцы”

Представим, что натуральное число n - это число каких-либо объектов (например, звёзд ★). Тогда число n = 5 будет означать, что имеется набор объектов ★★★★★.

Для составления композиции числа n = 5 из k компонент, необходимо представить число 5 в виде суммы нескольких натуральных чисел, что эквивалентно разбиению набора ★★★★★ на k наборов меньшей длины, каждый из которых представляет некоторое натуральное число и поэтому должен содержать не менее одного объекта ★.

Будем разбивать набор объектов столбцами |. Тогда композиция 2 + 3 эквивалентна ★★|★★★, композиция 3 + 1 + 1 эквивалентна ★★★|★|★ и так далее.

Можно заметить, что для составления композиции из k компонент необходимо расставить k - 1 столбцов.

Поскольку каждый набор содержит не менее одного объекта, столбец можно разместить только между двумя звёздами (наборы |★★|★★★ и ★★||★★★ нам не подходят). Тогда между n звёздами существует ровно n - 1 ячеек, в которые можно разместить столбцы. Например, если обозначить ячейку символом •, то доступные ячейки обозначаются ★•★•★•★•★.

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

Замечание

Если сложить все композиции натурального числа n из k компонент от k = 1 до k = n, получится число композиций натурального числа n, которое равно 2^(n - 1).

Теорема #2 (число слабых композиций натурального числа n из k компонент)

«Для любой пары натуральных чисел n и k число кортежей, состоящих из k целых неотрицательных чисел, сумма которых даёт n, то есть число слабых композиций натурального числа n из k компонент, равно числу мультимножеств мощности k - 1, выбранных из множества мощности n + 1, то есть равно (( n+1, k-1 )) = С(n+k-1, k-1).»

Например, для n = 5 и k = 2 существует C(n+k-1, k-1) = C(6, 1) = 6 слабых композиций:

5 + 0
4 + 1
3 + 2
2 + 3
1 + 4
0 + 5

Например, для n = 5 и k = 3 существует C(n+k-1, k-1) = C(7, 2) = 21 слабая композиция.

Доказательство методом “звёзды и столбцы”

Доказательство этой теоремы очень похоже на доказательство предыдущей. Натуральное число n = 5 так же представляется набором объектов ★★★★★, а в случае композиции этот набор объектов разделяется на несколько наборов столбцами |.

Основное отличие заключается в том, что в слабой композиции в качестве компонент могут использоваться нули, а значит наборы могут быть пустыми (могут не содержать объектов ★). Например, обозначение |★★|★★★ соответствует композиции 0 + 2 + 3, а обозначение ★★||★★★ соответствует композиции 2 + 0 + 3.

Итак, чтобы составить композицию из k компонент, мы, как и прежде, расставляем k - 1 столбцов.

Поскольку набор может не содержать объектов, столбец | можно разместить где угодно. Тогда между n звёздами существует ровно n + 1 ячеек, в которые можно разместить столбцы. Например, если обозначить ячейку символом •, то доступные ячейки обозначаются •★•★•★•★•★•. Более того, в одну ячейку может быть размещено несколько столбцов. Например, ★★||★★★.

Таким образом, необходимо разместить k - 1 столбцов в n + 1 ячеек, причём одна ячейка может содержать несколько столбцов. Иначе говоря, необходимо сделать множественный выбор k - 1 элементов из n + 1, что равно числу сочетаний с повторениями из n + 1 по k - 1, то есть (( n+1, k-1 )) = С(n+k-1, k-1).

Решение задач методом “звёзды и столбцы”

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

Примерная формулировка задач для теоремы #1:
«Имеется n одинаковых объектов и k различных ячеек. Сколько существует способов разместить объекты в ячейки, если каждая ячейка содержит не менее одного объектаф»

Примерная формулировка задач для теоремы #2:
«Имеется n одинаковых объектов и k различных ячеек. Сколько существует способов разместить объекты в ячейки, если каждая ячейка может содержать ни одного, один или несколько объектов?»

.