# Элементы теории множеств и комбинаторики Информатика · 8 класс Источник: https://razlozheno.ru/subject/informatika/8/elementy-teorii-mnozhestv-i-kombinatoriki Разберём, что такое множество, как его элементы связаны с множеством и друг с другом (пересечение, объединение, дополнение) и как считать варианты по правилам суммы и произведения. ## Чему научишься - Ты сможешь записать множество, его элементы и подмножество знаками $\in$, $\notin$, $\subset$, $\emptyset$ и не перепутать их. - Ты сможешь найти пересечение, объединение и дополнение множеств и посчитать $|X \cup Y|$ с учётом общих элементов. - Ты сможешь выбрать между правилом суммы и правилом произведения и посчитать число слов $M = N^k$. ## С чего начать В классе 12 человек ходят на футбол и 9 — на шахматы. Значит, в секциях всего 21 ученик? А ещё: как быстро узнать, сколько комплектов «футболка + джинсы» можно собрать из 3 футболок и 2 пар джинсов, не выписывая их все? В уроке есть ответ на оба вопроса. ## 1. Множество: что внутри и что снаружи *Элементы, подмножества и пустое множество* Начнём с вопроса: как назвать «кучу» предметов одним словом, чтобы потом с ней что-то делать: сравнивать, склеивать, считать? Математики придумали для этого **множество**. Представь рюкзак: неважно, как он называется и что в нём лежит — тетрадь, яблоко или ключи. Важно одно: про любую вещь можно сказать, лежит она в рюкзаке или нет. **Множество** **Множество** — совокупность объектов произвольной природы, которая рассматривается как единое целое. **Элементы множества** **Элементы множества** — объекты, входящие в состав множества. «Произвольной природы» значит буквально: в одном множестве могут лежать числа, буквы, люди, города. «Как единое целое» значит: мы смотрим на рюкзак целиком, а не на каждую вещь по отдельности. Множества принято обозначать прописными латинскими буквами $A, B, C, \dots$. Задать множество можно двумя способами: 1. **Перечислением элементов** в фигурных скобках: $A = \{1, 2, 3\}$. При этом действуют важные правила записи конечного множества: порядок элементов в фигурных скобках не имеет значения (например, $\{1, 2, 3\}$ и $\{3, 1, 2\}$ — это одно и то же множество), а повторять элемент нельзя (каждый элемент входит в множество ровно один раз). 2. **Характеристическим свойством** — описанием свойства, которым обладают все элементы множества и только они. Например: «множество всех чётных однозначных натуральных чисел» — это характеристическое свойство задаёт множество $\{2, 4, 6, 8\}$. Если элемент лежит в множестве, пишем $2 \in A$. Если не лежит — $5 \notin A$. Число элементов множества $M$ обозначают $|M|$ — это мощность множества. Для $A$ выше $|A| = 3$. *Рисунок: Круг с подписью M на окружности и точкой X внутри него.* *Рисунок: Круг с подписью M на окружности и точкой X снаружи него.* **Как не перепутать $\in$ и $\subset$** **Аналогия.** Множество — комната, элемент — человек в ней. «Петя в комнате» — это $\in$. «Комната в доме» — это уже $\subset$: одна комната целиком лежит в другой, большей. **Оговорка:** в математике элементом может быть и само множество, но на этом уровне такое не нужно. **Как запомнить (правило самопроверки).** Перед знаком смотри, что стоит слева. Отдельный предмет — ставь $\in$. Целый набор в скобках $\{\dots\}$ — ставь $\subset$. **Пустое множество** **Пустое множество** — множество, не содержащее ни одного элемента. Обозначение: $\emptyset$. Пустое множество — это пустой рюкзак. Сам рюкзак есть, а вещей в нём нет. Не путай его с нулём: $|\emptyset| = 0$, но сам $\emptyset$ — не число, а множество. **Подмножество** Множество $P$ называется **подмножеством** множества $M$, если каждый элемент множества $P$ принадлежит множеству $M$. Запись: $P \subset M$. **Пример: Подмножество или нет?** 1. Пусть $M = \{1, 2, 3, 4\}$, $P = \{2, 4\}$, $Q = \{2, 5\}$. 2. Проверяем $P$: элемент $2$ есть в $M$, элемент $4$ есть в $M$. Значит, $P \subset M$. 3. Проверяем $Q$: элемент $2$ есть в $M$, а $5 \notin M$. Один «чужой» элемент — и подмножеством $Q$ не является. **Неправильно:** $2 \subset A$, потому что двойка есть в множестве $A = \{1, 2, 3\}$. **Правильно:** Двойка — элемент, поэтому $2 \in A$. Знак $\subset$ ставят между множествами: $\{2\} \subset A$. **Проверь себя:** Верно ли, что $\{1, 3\} \subset \{1, 2, 3\}$? А что $4 \in \{1, 2, 3\}$? **Ответ:** Первое верно: и $1$, и $3$ лежат во втором множестве. Второе неверно: $4 \notin \{1, 2, 3\}$. ### Проверь себя **Что представляет собой множество согласно определению из учебного материала?** - Строго упорядоченная последовательность только числовых объектов. - Совокупность объектов произвольной природы, которая рассматривается как единое целое. — верно - Группа объектов одинаковой природы, содержащая обязательно конечное число элементов. - Графическое изображение точек внутри замкнутого круга Эйлера. > В материале множество определяется именно как совокупность объектов произвольной природы, рассматриваемая как единое целое. **Какими способами можно задать множество согласно приведенному источнику?** - Сложением или умножением мощностей алфавита. - Перечислением всех его элементов или характеристическим свойством его элементов. — верно - Только построением дерева вариантов или графическим ключом. - Только перечислением всех его элементов в круглых скобках. > В источнике указано два основных способа задания множеств: перечисление элементов и характеристическое свойство. **Какое из утверждений о порядке элементов при задании множества перечислением является верным?** - Порядок расположения элементов в фигурных скобках значения не имеет. — верно - Порядок важен только для бесконечных множеств. - При изменении порядка элементов образуется совершенно новое подмножество. - Элементы обязательно должны быть записаны строго по возрастанию. > Записи с разным порядком элементов (например, $\{1, 3, 5\}$ и $\{3, 1, 5\}$) имеют абсолютно одинаковый смысл. **Для каких множеств применим способ задания перечислением всех элементов?** - Только для конечных множеств при условии, что число элементов небольшое. — верно - Исключительно для пустого множества. - Для любых множеств, включая бесконечные. - Только для множеств, состоящих из латинских букв. > В источнике прямо указано, что первый способ применим только для конечных множеств с невеликим числом элементов. **Какая математическая запись используется для утверждения «число 4 не является элементом множества $M$»?** - $4 \in M$ - $4 \notin M$ — верно - $4 \subset M$ - $|4| = M$ > Знак $\notin$ обозначает непринадлежность элемента данному множеству. **Что обозначает запись $|M| = 5$ в теории множеств?** - Элемент 5 принадлежит множеству $M$. - Множество $M$ состоит из пяти подмножеств. - Множество $M$ содержит числа от 1 до 5 включительно. - В множестве $M$ содержится 5 элементов. — верно > Вертикальные черты вокруг названия множества обозначают количество элементов в нём. **Какое множество называется пустым?** - Множество, которое не является подмножеством самого себя. - Множество с бесконечным числом элементов. - Множество, не содержащее ни одного элемента. — верно - Множество, состоящее только из нуля. > По определению из текста, множество без элементов называется пустым и обозначается символом $\varnothing$. **В каком случае говорят, что множество $P$ есть подмножество множества $M$ ($P \subset M$)?** - Когда множества $P$ и $M$ не имеют ни одного общего элемента. - Когда объединение $P$ и $M$ дает пустое множество. - Когда количество элементов в $P$ строго больше, чем в $M$. - Когда каждый элемент множества $P$ принадлежит множеству $M$. — верно > Это точное определение подмножества, приведенное в источнике. **Какие из перечисленных множеств всегда являются подмножествами любого множества $M$?** - Само множество $M$ и пустое множество. — верно - Только множество всех натуральных чисел. - Только одноэлементные подмножества. - Только двухэлементные подмножества. > В тексте явно указано: «Само множество М является своим подмножеством... Пустое множество также является подмножеством М». **Каково перечисление всех элементов множества $O$ всех цифр восьмеричной системы счисления?** - $O = \{0, 8\}$ - $O = \{0, 1, 2, 3, 4, 5, 6, 7, 8\}$ - $O = \{0, 1, 2, 3, 4, 5, 6, 7\}$ — верно - $O = \{1, 2, 3, 4, 5, 6, 7, 8\}$ > В восьмеричной системе счисления используются ровно восемь цифр от 0 до 7. ## 2. Операции над множествами *Пересечение, объединение и дополнение* Вернёмся к секциям. Футболисты — одно множество, шахматисты — другое. Есть ребята, которые ходят и туда, и туда. Как их учесть? Для этого у множеств есть три операции: найти общее, склеить в одно и найти «остаток». **Пересечение множеств** **Пересечение** множеств $X$ и $Y$ — множество общих элементов двух множеств. Обозначение: $X \cap Y$. *Рисунок: Два пересекающихся круга X и Y, общая часть заштрихована.* **Объединение множеств** **Объединение** множеств $X$ и $Y$ — множество, состоящее из всех элементов множеств $X$ и $Y$ и не содержащее никаких других элементов. Обозначение: $X \cup Y$. *Рисунок: Два пересекающихся круга X и Y с заштрихованными областями.* Общая часть попала в объединение один раз. Если у двух футболистов-шахматистов есть по одной фамилии в обоих списках, в общем списке каждая фамилия записывается один раз. Отсюда и ответ на вопрос из начала: ученики из пересечения посчитаны дважды. **Сколько элементов в объединении** $|X \cup Y| = |X| + |Y| - |X \cap Y|$ $|X|$ и $|Y|$ — числа элементов в каждом множестве, $|X \cap Y|$ — число общих элементов, $|X \cup Y|$ — число элементов в объединении. **Почему вычитаем пересечение** **Аналогия.** Два человека несут пакеты, и у обоих в списке покупок есть молоко. Если сложить длины списков, молоко посчитается два раза. Купить его надо один раз, поэтому лишнее вычитаем. **Как запомнить (правило самопроверки).** Объединение никогда не больше суммы: $|X \cup Y| \le |X| + |Y|$. Получилось больше — забыл вычесть пересечение. Если общих элементов нет ($X \cap Y = \emptyset$), вычитать нечего, остаётся просто сумма. **Пример: Ответ на вопрос про секции** 1. Пусть футбол — множество $X$, $|X| = 12$. Шахматы — множество $Y$, $|Y| = 9$. Допустим, $4$ ученика ходят и туда, и туда: $|X \cap Y| = 4$. 2. Считаем: $|X \cup Y| = 12 + 9 - 4 = 17$. 3. Всего в секциях $17$ человек, а не $21$: четверо были посчитаны дважды. **Проверь себя:** В классе $|X| = 10$ человек любят чай, $|Y| = 7$ — кофе, а $|X \cup Y| = 15$. Сколько человек любят и чай, и кофе? **Ответ:** Из $15 = 10 + 7 - |X \cap Y|$ получаем $|X \cap Y| = 2$. Теперь особые случаи: когда одно множество целиком лежит внутри другого. Если $P \subset M$, то $P$ — это кружок внутри большого круга $M$. **Законы для вложенных множеств** $M \cap P = P \quad (\text{если } P \subset M)$ $M \cup P = M \quad (\text{если } P \subset M)$ $M \cap M = M$ $M \cup M = M$ **Малый круг внутри большого** **Аналогия.** Общее у большой и маленькой матрёшки — это маленькая матрёшка: всё, что есть в ней, есть и в большой. Вместе они занимают место большой. Со «своей копией» так же: общее у $M$ и $M$ — это $M$, склейка $M$ с $M$ — тоже $M$. **Как запомнить (правило самопроверки).** Пересечение — всегда меньшее из двух, объединение — всегда большее. Когда одно вложено в другое, ответ виден сразу, без вычислений. **Дополнение подмножества** Если множество $P$ является подмножеством множества $M$, то **дополнением** $P$ до $M$ называется множество, состоящее из тех элементов $M$, которые не вошли в $P$. Обозначение: $\overline{P}$. Дополнение — это «остаток»: взял из коробки конфет свои любимые $P$, а то, что осталось лежать, и есть $\overline{P}$. Вместе $P$ и $\overline{P}$ дают всё $M$, поэтому $|P| + |\overline{P}| = |M|$. Два крайних случая: **Дополнение крайних множеств** $\overline{M} = \emptyset$ $\overline{\emptyset} = M$ **Взял всё или ничего** **Аналогия.** Коробка конфет $M$. Забрал все конфеты — в коробке осталось ничего: $\overline{M} = \emptyset$. Не взял ни одной — в коробке осталось всё: $\overline{\emptyset} = M$. **Как запомнить (правило самопроверки).** Дополнение «переворачивает» крайности: всё превращается в ничего, ничего — во всё. **Три операции рядом** | | Пересечение $X \cap Y$ | Объединение $X \cup Y$ | Дополнение $\overline{P}$ | | --- | --- | --- | --- | | Что получается | только общие элементы | все элементы обоих множеств | то, что осталось в $M$ после $P$ | | Сколько элементов | не больше меньшего множества | не больше суммы $\lvert X \rvert + \lvert Y \rvert$ | $\lvert M \rvert - \lvert P \rvert$ | | Когда нужно | «и то, и другое» | «хотя бы одно из двух» | «всё, кроме» | **Неправильно:** В классе $|X| = 12$ и $|Y| = 9$, значит $|X \cup Y| = 21$ всегда. **Правильно:** Так только если общих нет. В общем случае $|X \cup Y| = |X| + |Y| - |X \cap Y|$. ### Проверь себя **Что называется пересечением двух множеств $X$ и $Y$?** - Множество, состоящее из всех элементов этих множеств без повторений. - Множество их общих элементов. — верно - Множество элементов, принадлежащих $X$, но не входящих в $Y$. - Произведение количества элементов множества $X$ на количество элементов $Y$. > Пересечение по определению состоит только из тех элементов, которые одновременно принадлежат и $X$, и $Y$. **Чему равно пересечение двух множеств $M$ и $X$, если они не имеют общих элементов?** - Пустому множеству ($\varnothing$). — верно - Множеству $X$. - Множеству $M$. - Числу 0. > Если общих элементов нет, то результирующее множество не содержит элементов, то есть является пустым: $M \cap X = \varnothing$. **Что называется объединением двух множеств $X$ и $Y$?** - Множество, состоящее из всех элементов этих множеств и не содержащее никаких других элементов. — верно - Сумма мощностей множеств без учета их состава. - Множество, содержащее только общие элементы $X$ и $Y$. - Множество элементов, оставшихся после удаления общих элементов. > Объединение включает в себя все элементы первого и второго множеств. **Какая формула используется для вычисления числа элементов объединения двух пересекающихся множеств $X$ и $Y$?** - $|X \cup Y| = |X| + |Y| + |X \cap Y|$ - $|X \cup Y| = |X \cap Y|^k$ - $|X \cup Y| = |X| \times |Y|$ - $|X \cup Y| = |X| + |Y| - |X \cap Y|$ — верно > Чтобы не посчитать общие элементы дважды, из суммы элементов вычитается число элементов их пересечения. **При каком условии операция дополнения множества $P$ до множества $M$ имеет смысл?** - Когда мощности множеств $P$ и $M$ совпадают и равны нулю. - Только если $M$ является пустым множеством. - Только тогда, когда второе множество $P$ является подмножеством первого множества $M$. — верно - Когда множества $P$ и $M$ не имеют общих элементов. > В источнике четко указано, что дополнение имеет смысл не для всех множеств, а только когда $P \subset M$. **Что называется дополнением подмножества $P$ до множества $M$?** - Множество, состоящее из тех элементов $M$, которые не вошли в $P$. — верно - Множество, состоящее из элементов $P$, не входящих в $M$. - Объединение всех одноэлементных подмножеств множества $P$. - Множество общих элементов $P$ и $M$. > Дополнение $\overline{P}$ содержательно дополняет $P$ элементами из $M$, которых в $P$ не хватало. **Пусть $M = \{1, 3, 5, 7, 9\}$ и $P = \{1, 3, 5\}$. Чему равно дополнение $\overline{P}$ до $M$?** - $\overline{P} = \{1, 3, 5\}$ - $\overline{P} = \{1, 3, 5, 7, 9\}$ - $\overline{P} = \varnothing$ - $\overline{P} = \{7, 9\}$ — верно > Элементы 7 и 9 — это единственные элементы множества $M$, которые не входят в подмножество $P$. **Чему равны дополнение множества $M$ до $M$ и дополнение пустого множества до $M$?** - Оба дополнения равны $M$. - Дополнение $M$ до $M$ равно $M$, а дополнение $\varnothing$ до $M$ равно $\varnothing$. - Дополнение $M$ до $M$ равно $\varnothing$, а дополнение $\varnothing$ до $M$ равно $M$. — верно - Оба дополнения равны $\varnothing$. > В $M$ не остается элементов вне $M$ (получаем $\varnothing$), а из $M$ вне $\varnothing$ выходят все элементы (получаем $M$). ## 3. Правила суммы и произведения *Как считать варианты и слова* Теперь второй вопрос из начала: сколько комплектов «футболка + джинсы»? Такие задачи называют комбинаторными. **Комбинаторные задачи** **Комбинаторные задачи** — задачи, связанные с рассмотрением тех или иных комбинаций (вариантов) из элементов конечных множеств. Всё держится на двух правилах. Различие простое: **«или»** — складываем, **«и»** — умножаем. Выбираешь одну вещь из разных куч — сумма. Выбираешь пару, где сначала одно, а потом другое, — произведение. **Правило суммы** Если выбор некоторого объекта может быть осуществлён $n$ различными способами, а выбор другого объекта — $m$ различными способами, отличными от предыдущих, то число способов, которыми можно осуществить выбор какого-нибудь одного из этих объектов, равно сумме $n + m$. **Правило суммы в записи множеств** $|X \cup Y| = |X| + |Y| = n + m \quad (\text{если } X \cap Y = \emptyset)$ **Буфет: «или»** **Аналогия.** В буфете 3 вида пирожков и 2 вида булочек. Берёшь что-то одно: пирожок или булочку. Все варианты разные, значит, $3 + 2 = 5$ способов. **Как запомнить (правило самопроверки).** Слово «или» и разные, не пересекающиеся кучи — плюс. Если кучи пересекаются, вспомни формулу с вычитанием $|X \cap Y|$. **Правило произведения** Если выбор некоторого объекта может быть осуществлён $n$ различными способами и если после каждого такого выбора другой объект можно выбрать $m$ различными способами, то число способов, которыми можно осуществить выбор упорядоченной пары этих объектов, равно произведению $n \cdot m$. **Число пар** $N_{\text{пары}} = n \cdot m$ *Рисунок: Схема-дерево: четыре юноши, для каждого показаны два варианта девушек.* Видно, почему умножаем: у каждого из $n$ юношей своя «связка» из $m$ вариантов. Складываем $m$ ровно $n$ раз — получается $n \cdot m$. Точно так же комплектов «футболка + джинсы» будет $3 \cdot 2 = 6$, это и есть ответ на второй вопрос в начале. *Рисунок: Четыре круга с точками, соединёнными линиями в форме прямоугольника.* **Меню: «и»** **Аналогия.** В столовой выбираешь первое **и** второе. Каждое первое сочетается с каждым вторым, поэтому вариантов столько, сколько клеток в таблице: строки на столбцы. **Как запомнить (опорное число).** Слово «и» и последовательные выборы — умножай. Проверка: $2$ футболки и $2$ джинсов дают $2 \cdot 2 = 4$ комплекта — те же четыре клетки таблицы $2 \times 2$. **Сумма или произведение** | | Правило суммы | Правило произведения | | --- | --- | --- | | Слово в задаче | «или»: одно из | «и»: сначала это, потом то | | Что считаем | один объект | упорядоченную пару | | Действие | $n + m$ | $n \cdot m$ | | Условие | способы не совпадают | после любого выбора $m$ способов | | Пример | пирожок или булочка | футболка и джинсы | Правило произведения работает и для длинных «слов». Слово — это $k$ символов подряд, каждый из алфавита в $N$ символов. На первом месте $N$ вариантов, на втором тоже $N$ (после любого выбора первого), и так $k$ раз. Перемножаем $k$ одинаковых чисел $N$. **Число слов фиксированной длины** $M = N^k$ $M$ — максимально возможное количество комбинаций (слов) фиксированной длины, $N$ — количество символов в алфавите (мощность алфавита), $k$ — длина слова. **Кодовый замок** **Аналогия.** Кодовый замок с $k$ колёсиками, на каждом $N$ положений. Крутишь каждое независимо — и число комбинаций растёт как лавина. **Как запомнить (опорное число).** Два символа и три места: $2^3 = 8$. Значит, $N$ — то, что *возводят*, а $k$ — во сколько раз *повторяют*. Не путай с $N \cdot k$: при $N = 2$, $k = 3$ это $6$, а слов $8$. **Пример: Сколько четырёхзначных кодов из цифр** 1. Алфавит — десять цифр: $N = 10$. Длина слова $k = 4$. 2. По формуле $M = N^k = 10^4$. 3. Получаем $M = 10000$ кодов — от $0000$ до $9999$. **Проверь себя:** Алфавит из 3 символов. Сколько слов длины 2? **Ответ:** $M = 3^2 = 9$. **Почему в задачах «хотя бы одно» нужны оба правила** Часто в одной задаче есть и «или», и «и». Например, выбираем одну вещь из двух групп — складываем, а в каждой группе вариант сам собой получается умножением. Сначала определи, какие выборы независимы («и»), а какие взаимно исключают друг друга («или»), потом считай по частям. ### Проверь себя **Сформулируйте правило суммы в комбинаторике согласно источнику.** - Выбор объектов из пересекающихся множеств всегда осуществляется вычитанием $n - m$. - Количество способов выбора всегда равно $n^m$. - Если выбор объекта $A$ осуществляется $n$ способами, а объекта $B$ — $m$ способами, то выбор пары $(A, B)$ осуществляется $n \cdot m$ способами. - Если выбор объекта $A$ осуществляется $n$ способами, а объекта $B$ — $m$ способами (отличными от предыдущих), то выбор «либо $A$, либо $B$» осуществляется $n + m$ способами. — верно > Правило суммы применяется при выборе одного из объектов некоторого типа из непересекающихся вариантов. **Сформулируйте правило произведения в комбинаторике согласно источнику.** - Выбор пары возможен только для бесконечных множеств. - Число способов выбора одного из двух объектов равно сумме $n + m$. - Если выбор объекта $A$ осуществляется $n$ способами и после каждого такого выбора объект $B$ можно выбрать $m$ способами, то выбор упорядоченной пары можно сделать $n \cdot m$ способами. — верно - Число способов выбора упорядоченной пары всегда равно $n + m - 1$. > Правило произведения применяется для подсчета числа способов формирования последовательных выборов или пар. **Какой наглядный приём часто используется для организованного перебора всех возможных вариантов решений комбинаторной задачи?** - Замена фигурных скобок на круглые. - Запись характеристического свойства. - Построение графика кругов Эйлера. - Построение дерева вариантов. — верно > В задаче 2 источника дерево вариантов показано как систематический способ наглядного перебора всех комбинаций. **В группе 4 шахматиста и 2 шахматистки. Сколькими способами тренер может составить команду из одного юноши и одной девушки по правилу произведения?** - 6 способами - 16 способами - 24 способами - 8 способами — верно > По правилу произведения $4 \cdot 2 = 8$ способов сформировать пару из юноши и девушки. **Сколько различных графических ключей можно создать из 4 вершин квадрата, если использовать каждую вершину в качестве узла ломаной линии ровно один раз?** - 256 вариантов - 10 вариантов - 16 вариантов - 24 варианта — верно > Первую вершину можно выбрать 4 способами, вторую — 3, третью — 2, четвёртую — 1: $4 \cdot 3 \cdot 2 \cdot 1 = 24$. **Какая формула позволяет определить максимально возможное количество слов $M$ фиксированной длины $k$ в алфавите мощности $N$?** - $M = N \cdot k$ - $M = N + k$ - $M = N^k$ — верно - $M = k^N$ > Каждая из $k$ позиций слова может содержать любой из $N$ символов, что по правилу произведения дает $N \cdot N \dots = N^k$. **Алфавит некоторого языка содержит 3 символа, а каждое слово состоит ровно из 5 символов. Сколько всего слов существует в этом языке?** - 125 слов - 243 слова — верно - 24 слова - 15 слов > По формуле $M = N^k$ получаем $M = 3^5 = 3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 = 243$. **Приложении смартфона требует ввод пароля из 4 полей с алфавитом из первых 5 букв английского алфавита. Чему равно количество вариантов паролей?** - 625 вариантов — верно - 120 вариантов - 20 вариантов - 1024 варианта > Мощность алфавита $N = 5$, длина пароля $k = 4$. По формуле $M = N^k = 5^4 = 625$. **Из скольких элементов состоит множество всех цепочек из 0 и 1, состоящих ровно из трёх символов?** - 9 элементов - 8 элементов — верно - 6 элементов - 3 элемента > Алфавит состоит из 2 символов ($N=2$), длина цепочки $k=3$. Количество цепочек равно $2^3 = 8$. ## Ключевые термины - **Множество** — Совокупность объектов произвольной природы, которая рассматривается как единое целое. - **Элементы множества** — Объекты, входящие в состав множества. - **Пустое множество** — Множество, не содержащее ни одного элемента. - **Подмножество** — Множество $P$ называется подмножеством множества $M$, если каждый элемент множества $P$ принадлежит множеству $M$. - **Пересечение множеств** — Множество общих элементов двух множеств $X$ и $Y$. - **Объединение множеств** — Множество, состоящее из всех элементов множеств $X$ и $Y$ и не содержащее никаких других элементов. - **Дополнение подмножества** — Если множество $P$ является подмножеством множества $M$, то дополнением $P$ до $M$ называется множество, состоящее из тех элементов $M$, которые не вошли в $P$. - **Комбинаторные задачи** — Задачи, связанные с рассмотрением тех или иных комбинаций (вариантов) из элементов конечных множеств. - **Правило суммы** — Если выбор некоторого объекта может быть осуществлён $n$ различными способами, а выбор другого объекта — $m$ различными способами, отличными от предыдущих, то число способов, которыми можно осуществить выбор какого-нибудь одного из этих объектов, равно сумме $n + m$. - **Правило произведения** — Если выбор некоторого объекта может быть осуществлён $n$ различными способами и если после каждого такого выбора другой объект можно выбрать $m$ различными способами, то число способов, которыми можно осуществить выбор упорядоченной пары этих объектов, равно произведению $n \cdot m$. ## Итог - Множество — совокупность объектов как единое целое; элемент лежит в нём ($\in$) или нет ($\notin$); $P \subset M$, если все элементы $P$ есть в $M$. - Пересечение $X \cap Y$ — общие элементы, объединение $X \cup Y$ — все элементы обоих, дополнение $\overline{P}$ — остаток $M$ после $P$. - Общие элементы в объединении считаем один раз: $|X \cup Y| = |X| + |Y| - |X \cap Y|$. - «Или» с разными способами — сумма $n + m$, «и» (упорядоченная пара) — произведение $n \cdot m$. - Слов длины $k$ в алфавите из $N$ символов: $M = N^k$. ## Шпаргалка ### Формулы подсчёта - **$\lvert X \cup Y \rvert = \lvert X \rvert + \lvert Y \rvert - \lvert X \cap Y \rvert$** — элементов в объединении, есть общие - **$\lvert X \cup Y \rvert = n + m$** — объединение без общих элементов - **$N_{\text{пары}} = n \cdot m$** — выбор упорядоченной пары объектов - **$M = N^k$** — число слов длины $k$ в алфавите $N$ ### Знаки и обозначения - **$\in$, $\notin$** — элемент принадлежит, не принадлежит множеству - **$\subset$** — подмножество: все элементы внутри большего - **$\emptyset$** — пустое множество, элементов нет - **$\overline{P}$** — дополнение $P$ до $M$ - **$M \cap P = P$** — если $P \subset M$ - **$M \cup P = M$** — если $P \subset M$ ### Сумма или произведение | | Правило суммы | Правило произведения | | --- | --- | --- | | Слово | «или» | «и» | | Действие | $n + m$ | $n \cdot m$ | | Способы | не совпадают | $m$ после любого выбора | ### Как решать комбинаторную задачу 1. **Прочитай** — пойми, что выбираем: один объект или пару 2. **Найди слово** — «или» — сумма, «и» — произведение 3. **Проверь общие** — есть пересечение — вычти его 4. **Посчитай** — подставь числа и запиши ответ ## Любопытное - Слов из $k$ символов растёт очень быстро: добавишь один символ к длине — число слов умножится на $N$. Так короткий пароль в $8$ символов из $10$ цифр даёт уже $10^8$ вариантов. - Пустое множество $\emptyset$ — подмножество любого множества: в нём просто нет элементов, которые могли бы не оказаться в $M$.