Файл: 1. Основные понятия теории множеств. Способы задания множеств. Операции над множествами. Теоретикомножественные тождества.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 03.12.2023
Просмотров: 81
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
называют различные упорядоченные -множества, которые состоят из одних и тех же элементов, а отличаются друг от друга лишь порядком. Число таких перестановок обозначают .
Формулу для получаем из выражения (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. Линейные рекуррентные соотношения с постоянными коэффициентами.
Формулу для получаем из выражения (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
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 |
Первые два значения находятся непосредственно ( – слова 0 и 1; – слова 000, 010, 101), а остальные – по формуле (6).
Пример 2. Задача о расстановке скобок в выражении с неассоциативной бинарной операцией.Пусть “ ” обозначает некоторую бинарную операцию. Рассмотрим выражение , в котором символ обозначает некоторую бинарную неассоциативную операцию. Сколько имеется различных способов расстановки скобок в этом выражении?
Как пример неассоциативной операции можно привести векторное произведение. Другой пример – обычное сложение и умножение, выполняемое на компьютере. В силу того, что представление каждого числа в памяти компьютера ограничено определенным количеством разрядов, при выполнении каждой операции возникает погрешность и суммарный результат этих погрешностей зависит от расстановки скобок. Пусть – машинный ноль. Это означает, что . Тогда , в то время как .
Обозначим число всевозможных способов расстановки скобок через . Тогда
;
.
Назовем операцию условно произведением. Для произвольного разобьем все способы расстановки скобок на классы, включив в -ый класс способы, при которых сначала вычисляется произведение первых и последних операндов с какой-то расстановок скобок, а потом вычисляется их произведение:
(7)
где .
По определению количество способов расстановки скобок для вычисления первых операндов равно , последних – . По правилу произведения число расстановок скобок для выражения (4) равно . По правилу сложения
, (8)
Например, .
12. Линейные рекуррентные соотношения с постоянными коэффициентами.