Операции на множествах и их свойства. Теорема о мощности декартова произведения конечных множеств. Теорема о счетности множества рациональных чисел. Изоморфизмы и автоморфизмы алгебр, страница 3

Билет №13.Сочетания без повторений и их число. Связь с биномом Ньютона.

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

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

Пример:

Теорема. Число всех r-сочетаний из множества А, равно .

Доказательство:

Доказано, что общее количество всех упорядоченных r-элементных подмножеств равно .

Мы знаем, что число способов упорядочить r элементное подмножество равно . Следовательно, число выборок будет в r! раз больше числа сочетаний. Следовательно, .

Пример:

Сколько баскетбольных команд можно составить из 10 человек?

Ответ:

Бином Ньютона.

(подмножество в множестве 0)

Эта сумма равна числу подмножеств из мощности множества n, т.е. мощности булеана этого множества.

Билет №14. Размещения данного состава и их число. Полиноминальная формула.

Размещением состава  называется m-выборка с повторениями в которую а₁ входит ровно k₁ раз,… а_m входит ровно k_m раз.

Теорема. Пусть - целые неотрицательные числа, причем . Число способов, которыми можно представить множество А из n элементов в виде суммы m подмножеств  число элементов которых составляет соответственно равно:

Доказательство:

Разложим множество А, состоящее из n элементов на сумму m подмножеств  так, чтобы где заданы, причем . Последнее условие означает, что множества  не должны иметь общих элементов.

Вначале выберем k₁ – элементное подмножество (существует  способов это сделать). Затем из оставшихся (n-k₁) элементов выберем k₂-элементное подмножество (число способов при этом ) и т.д.

Согласно правилу умножения общее число способов выбрать подмножества  будет:

Полиноминальная формула.

при n=2 – бином Ньютона

Пример:

найти коэффициенты при x²y³ в выражении

m=3, n=5

k₁=2, k₂=3, k₃=0

Билет №15. Сочетания с повторениями и их число.

Любое подмножество мощности r, некоторые элементы которого могут повторятся называется r-сочетаниями с повторениями из .

Пример:

Из элементов трех типов можно составить такие сочетания с повторениями по два элемента r=2;

Теорема. Число всех r-сочетаниями с повторениями из множества , где  равно .

Доказательство:

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

aa 1100          bc  0101

ac  1001         bb  0110

ab  1010         cc  0011

Всего в каждой строке (r+n-1) символов, из них r- единиц, (n-1) – нулей. Чтобы однозначно задать сочетание, надо задать номера мест, на которых будут стоять нули (это можно сделать  способами), или номера мест, где будут стоять единицы (это можно сделать  способами). Поэтому число сочетаний с повторениями можно вычислить по формуле .

Билет №16. Задача о количестве целочисленных решений линейного уравнения.

Задача 1.

Сколько существует решений уравнения , где x_i≥0 и целое (r≥0).

Решение:

Каждому решению  ставим в соответствие B – неупорядоченную выборку из  такую, что

а₁ входит х₁ раз в В

а₂ входит х₂ раз в В

       …………..

а_n входит х_n раз в В

Решений существует столько, сколько существует r-сочетаний с повторениями из множества А, а именно .

Задача 2.

Сколько существует целочисленных решений уравнения , где x_i≥a_i (a_i – целые числа, возможно отрицательные).

Решение:

Пусть

, и пусть

, где .

Таким образом, если

1. <0, то решений нет

2. ≥0, то решение есть, а именно

Пример:

, при

r= -10, n=3, s=2+(-20)+3= -15;

Билет №17. Формула включений и исключений и ее применение в комбинаторике.

Пусть А и В – два конечных множества. Тогда, если , то . Пусть теперь . Тогда в  каждый элемент из  будет учтен два раза. Поэтому .

Теорема.

         Доказательство:

n=3;

X – конечное множество, причем .

- некоторые свойства элементов из Х.

 - множество элементов в Х, обладающих свойством .

- количество элементов в Х, обладающих одновременно свойствами .

- количество элементов в Х, не обладающих ни одним из свойств.

Тогда  (это равенство автоматически вытекает из второй формы записи формулы включений и исключений).

Пример:

n=3

Билет №18. Задача о беспорядках (применение формулы включений и исключений).

Задача:

Имеется n различных предметов a₁,a₂,…,a_n и  n различных ячеек b₁,b₂,…,b_n. Сколькими способами можно разместить предметы по ячейкам так, чтобы никакой предмет a_i не попал в ячейку b_i?

Решение:

В качестве исходного множества Х возьмем совокупность всевозможных расположений предметов по ячейкам. Тогда . Введем свойства , при i=1,2,…,n. Число  расположений, при которых предмет  находится в ячейке , =1,…,k_ν равно (n-k)!. Тогда

Используя теперь формулу включений и исключений, получаем, что число N₀

Расположений, при которых ни одно из свойств не выполняется (т.е ни один из предметов a_i не попал в ячейку b_i), равно

Обобщение задачи о беспорядках.

Задача.

Ровно S-элементов попали в . Сколько существует таких распределений?

Решение:

 N₀(S) – число таких решений.

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

.