1. Основные понятия теории множеств. Способы задания множеств. Операции над множествами. Теоретикомножественные тождества
 Скачать 4.95 Mb.
|
|
Правило биекции Это правило, которое называется также принципом взаимно однозначного соответствия, формулируется следующим образом: если между множествами и можно установить взаимно однозначное соответствие (биекцию), то . В качестве примера применения этого принципа найдем мощность множества всех подмножеств данного множества . Такое множество называют булеаном множества и обозначают символом . Пусть – -множество. Так как мощность множества не зависит от природы его элементов, то можно принять . Поставим в соответствие произвольному подмножеству двоичное слово по следующему правилу: Это соответствие взаимно однозначное. Отсюда следует, что число всех подмножеств -множества равно числу двоичных слов длины , то есть . 5. Метод включений и исключений. Пример. Поставим задачу подсчитать количество элементов в объединении конечных множеств , которые могут иметь непустые пересечения между собой, т. е. это объединение в общем случае не является разбиением. Для двух множеств имеем формулу (1). Обозначим и применим эту формулу для трех множеств, используя дистрибутивность операций объединения и пересечения множеств: (6) В результате по индукции получаем формулу включений и исключений: (7) Подсчитаем теперь число элементов , обладающих ровно свойствами. Покажем, что в этом случае имеет место следующая формула включений и исключений: . (9) Действительно, элемент, обладающий ровно , , свойствами, не будет учитываться в формуле (9), а элемент, обладающий ровно свойствами, будет учитываться только один раз, так как При из формулы (9), как частный случай, имеем формулу обращения (8). Использование формулы (9) в комбинаторике называют методом включений и исключений. Пример 6. Найти число перестановок -множества, оставляющих на месте ровно элементов. Решение. Перестановки элементов данного -множества будем считать элементами -множества. Обозначим и свойство перестановки, состоящее в том, что элемент с номером в результате данной перестановки остается на месте. Тогда , . По формуле (9) . (10) 6. Понятие выборки. Размещения и формулы для их подсчета с повторениями и без повторений элементов. Примеры. 7. Понятие выборки. Перестановки и формулы для их подсчета с повторениями и без повторений элементов. Примеры. 8. Понятие выборки. Сочетания и формулы для их подсчета с повторениями и без повторений элементов. Примеры. Понятие выборки Набор элементов из множества называется выборкой объема из элементов или -выборкой. Выборка называется упорядоченной, если порядок следования элементов в ней задан. Две упорядоченные выборки, различающиеся лишь порядком следования элементов, считаются различными. Если порядок следования элементов не является существенным, то выборка называется неупорядоченной. В выборках могут допускаться или не допускаться повторения элементов. В зависимости от способа формирования все выборки в комбинаторике классифицируют как размещения, перестановки и сочетания с повторениями и без повторений элементов. Размещения -размещением с повторениями из элементов называется упорядоченная -выборка, в которой элементы могут повторяться. Число всех таких выборок, которые отличаются друг от друга составом элементов или их порядком, равно числу векторов в декартовом произведении . Это число обозначают . По правилу произведения получаем . (1) Пример 1. Для запирания сейфа используется диск, на который нанесены 12 символов, а секретное слово состоит из 5 символов. Сколько неудачных попыток может быть сделано человеком, не знающим секретного слова? Общее число комбинаций равно . Значит, неудачных попыток может быть 248831. -размещением без повторений из элементов называется упорядоченная -выборка, в которой элементы не повторяются. Число всех упорядоченных -множеств с различными элементами, которые можно составить из элементов -множества , обозначают . Для вычисления необходимо сделать выборов. 1-й элемент можно выбрать способами, 2-й – ( ) способами и т. д. Последний -й элемент можно выбрать способами. По правилу произведения . (2) Здесь – « -факториал» (0!=1!=1). Пример 2. Научное общество состоит из 25 человек. Надо выбрать президента общества, вице-президента, ученого секретаря и казначея. Сколькими способами может быть сделан этот выбор, если каждый член общества может занимать лишь один пост? Ответ: . Перестановки Решим следующую комбинаторную задачу. Сколькими способами можно упорядочить -множество ? Перестановками без повторений называют различные упорядоченные -множества, которые состоят из одних и тех же элементов, а отличаются друг от друга лишь порядком. Число таких перестановок обозначают . Формулу для получаем из выражения (2) при : . (3) Пример 3. Сколькими способами можно посадить на скамейку 9 человек? Ответ: =9!=362880. К перестановкам с повторениями приводит следующая задача. Имеется -множество , состоящее из различных элементов ( ). Сколько перестановок можно сделать из элементов первого типа, элементов второго типа,…, элементов -го типа? Перестановки элементов каждого типа можно делать независимо друг от друга. Поэтому по правилу произведения элементы множества можно переставлять друг с другом способами так, что перестановки не изменятся. Тогда число различных перестановок с повторениями буде равно , (4) где . Пример 4. Сколько перестановок можно сделать из букв слова «Миссисипи»? В данном случае , («М»), («и»), («с»), («п»). По формуле (4) . Сочетания В тех случаях, когда не имеет значения порядок элементов в подмножестве некоторого множества, а лишь его состав, говорят о сочетаниях. К сочетаниям без повторений приводит следующая задача комбинаторики. Сколько -элементных подмножеств с различными элементами можно составить из элементов -множества ? Такие подмножества называют сочетаниями без повторений из элементов по или короче -сочетаниями, а их число обозначают (от французского слова combinaison – сочетание). Другими словами, сочетаниями без повторений называется неупорядоченная -выборка, в которой элементы не повторяются. Формулу для числа сочетаний легко получить из формулы (2) для числа размещений. Выберем какое-нибудь -элементное подмножество . Его можно упорядочить способами, а число таких подмножеств есть . Тогда справедлива формула , (5) откуда . (6) Пример 5. Сколько всего партий играется в шахматном турнире с участниками? Ответ: , так как каждая партия однозначно определяется двумя ее участниками. Пусть множество состоит из элементов различных типов: . Множество , составленное из , в котором элементы могут повторяться, называется мультимножеством. Для задания мультимножества надо указать число вхождений в него каждого элемента: , где – мощность мультимножества. Число мультимножеств мощности , составленных из элементов -множества , называют сочетаниями с повторениями и обозначают . Другими словами, сочетаниями с повторениями называется неупорядоченная -выборка, в которой элементы могут повторяться. Зашифруем каждую комбинацию из элементов с помощью нулей и единиц: для каждого типа напишем столько единиц, сколько элементов этого типа входит в комбинацию, а различные типы отделим друг от друга нулями. Если элементы какого-нибудь типа не вошли в комбинацию, то надо писать два или большее число нулей. При этом получим единиц и нулей. Тогда число будет равно числу перестановок с повторениями из единиц и нулей: . Так как , то . (7) Встречаются задачи, в которых на сочетания с повторениями налагается дополнительное условие – в них обязательно должны входить элементы фиксированных типов . В этом случае . В частности, если и требуется, чтобы в -подмножество с повторениями входил по крайней мере один элемент каждого из типов , то получим мультимножеств. Пример 6. В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных? Решение. Мощность мультимножества , число различных элементов . Число способов покупки пирожных равно . 9. Свойства чисел C k/n. Треугольник Паскаля. Числа обладают целым рядом замечательных свойств, которые выражают различные соотношения между -подмножествами -множества . 1) . 2) . 3) . Это свойство можно доказать также формально, используя формулу (6). При имеем . Так как , то полагают . Кроме того, придерживаются соглашения при . Тогда свойство 3) позволяет последовательно вычислить числа при . Вычисления представляют в виде треугольника Паскаля. Этот треугольник имеет вид: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 …………………………………………….. 10. Задача о беспорядках. Сколькими способами можно разместить элементов множества в ячеек множества (по одному в каждой) так, чтобы никакой элемент не попал в ячейку ? Перестановку без повторений можно представить как биекцию множества на себя: . Перестановку называют беспорядком, если в ней каждый элемент стоит не на своем месте, то есть , . Задача о беспорядках состоит в том, чтобы подсчитать число перестановок-беспорядков. Например, , . Обозначим через множество все перестановок , в которых элемент стоит на -ом месте: . Множество состоит из перестановок, в которых хотя бы один элемент стоит на своем месте, а все остальные перестановки будут беспорядками. Тогда по формуле обращения . (8) Подсчитаем число перестановок в каждом из множеств и в их пересечениях. Если , то сужение отображения на множество является биекцией этого множества на себя. Следовательно, . Множество составлено из перестановок , в которых , . Сужение отображения на множество является биекцией этого множества на себя. Следовательно, . По индукции находим, что . По формуле включений и исключений В каждой из этих сумм слагаемые не зависят от индекса суммирования, поэтому для вычисления надо знать только их количество. В первой сумме слагаемых, число слагаемых во второй сумме равно количеству всевозможных пар , которые можно составить из индексов , то есть . Аналогично в -ой сумме имеем слагаемых. Отсюда . После подстановки в уравнение (8) и несложных преобразований находим . Выражение, стоящее в скобках, представляет собой частичную сумму ряда, сходящегося к , поэтому . Можно показать, что равно целому числу, ближайшему к : , где – целая часть числа . 11. Определение рекуррентного соотношения, его частного и общего решения. Примеры: числа Фибоначчи, число правильных n -разрядных двоичных слов, задача о расстановке скобок в выражении с неассоциативной бинарной операцией. Рекуррентным соотношением -го порядка между элементами последовательности чисел называется формула вида (1) Частным решением рекуррентного соотношения является любая последовательность , обращающая соотношение (1) в тождество. Соотношение (1) имеет бесконечно много частных решений, так как первые элементов последовательности можно задать произвольно. Например, последовательность является решением рекуррентного соотношения , так как имеет место тождество . Решение рекуррентного соотношения -го порядка называется общим , если оно зависит от произвольных постоянных , и путем подбора этих постоянных можно получить любое решение данного соотношения. Например, для соотношения (2) общим решением будет . (3) Действительно, легко проверить, что последовательность (3) обращает соотношение (2) в тождество. Поэтому надо только показать, что любое решение соотношения (2) можно представить в виде (3). Но любое решение этого соотношения однозначно определяется значениями и . Поэтому надо доказать, что для любых чисел и найдутся такие значения и , что Так как эта система имеет решение при любых значениях и , то решение (3) действительно является общим решением соотношения (2). Пример 1. Числа Фибоначчи. Пара кроликов приносит раз в месяц приплод из двух крольчат (самки и самца), причем новорожденные крольчата через два месяца после рождения уже приносят приплод. Сколько кроликов появится через год, если в начале года была одна пара кроликов? Из условия задачи следует, что через месяц будет две пары кроликов. Через два месяца приплод даст только первая пара кроликов, и получится 3 пары. A еще через месяц приплод дадут и исходная пара кроликов, и пара кроликов, появившаяся два месяца тому назад. Поэтому всего будет 5 пар кроликов и т. д. Обозначим через количество пар кроликов по истечении месяцев с начала года. Тогда через месяцев будут эти пар и еще столько новорожденных пар кроликов, сколько было в конце -го месяца, то есть еще пар. Таким образом, имеет место рекуррентное соотношение . (4) Так как , то последовательно находим: и т. д. Эти числа составляют последовательность 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,…, которую называют рядом Фибоначчи, а его члены – числами Фибоначчи. Найти число двоичных слов длины , в которых никакие две единицы не идут подряд. Будем называть такие слова правильными и обозначим их число через . Разобьем множество этих правильных слов на два класса: слова, оканчивающиеся на ноль, и слова, оканчивающиеся на единицу. Обозначим количество слов в этих классах и соответственно. По правилу сложения (5) Очевидно, что у слова, оканчивающегося на ноль, первые символов образуют правильное слово длины , или другими словами, имеется биекция между множеством правильных слов длины , оканчивающихся на ноль, и множеством правильных слов длины , то есть . Если правильное слово длины оканчивается на единицу, то предыдущий символ этого слова должен быть нулем, а первые символа должны образовывать правильное слово длины . Как и в предыдущем случае, снова имеем биекцию между множеством правильных слов длины , оканчивающихся на единицу, и множеством правильных слов длины . Следовательно. . Из формулы (5) получаем рекуррентное соотношение . (6) Для использования рекуррентного соотношения необходимы для данного вычисления всех предыдущих значений. Например, если нам нужно знать количество правильных слов из 10 символов, то его можно найти, последовательно заполняя следующую таблицу: Таблица 1
Первые два значения находятся непосредственно ( – слова 0 и 1; – слова 000, 010, 101), а остальные – по формуле (6). Пример 2. Задача о расстановке скобок в выражении с неассоциативной бинарной операцией.Пусть “ ” обозначает некоторую бинарную операцию. Рассмотрим выражение , в котором символ обозначает некоторую бинарную неассоциативную операцию. Сколько имеется различных способов расстановки скобок в этом выражении? Как пример неассоциативной операции можно привести векторное произведение. Другой пример – обычное сложение и умножение, выполняемое на компьютере. В силу того, что представление каждого числа в памяти компьютера ограничено определенным количеством разрядов, при выполнении каждой операции возникает погрешность и суммарный результат этих погрешностей зависит от расстановки скобок. Пусть – машинный ноль. Это означает, что . Тогда , в то время как . Обозначим число всевозможных способов расстановки скобок через . Тогда ; . Назовем операцию условно произведением. Для произвольного разобьем все способы расстановки скобок на классы, включив в -ый класс способы, при которых сначала вычисляется произведение первых и последних операндов с какой-то расстановок скобок, а потом вычисляется их произведение: (7) где . По определению количество способов расстановки скобок для вычисления первых операндов равно , последних – . По правилу произведения число расстановок скобок для выражения (4) равно . По правилу сложения , (8) Например, . 12. Линейные рекуррентные соотношения с постоянными коэффициентами. |