Сделай Сам Свою Работу на 5

Подмножества конечных множеств и сочетания





Если A = {a0 , … , an–1 } – конечное множество из n элементов, то символом В(А) будем обозначать булеан множества A, т.е. множество всех подмножеств множества А. Для того, чтобы поближе познакомиться с булеаном, рассмотрим следующую задачу: как перечислить все элементы булеана В(А) конечного n-элементного множества А = {a0 , … , an–1} ? Для бесконечных множеств булеан, очевидно, тоже бесконечен и поэтому менее обозрим, нежели в конечном случае.

Каждому подмножеству X Í A сопоставим n-значное двоичное число e(X) = en–1×2n–1+…+e0×20 = ( )2 с цифрами ei Î {0, 1} (0 £ i £ n–1), однозначно определяющее это подмножество. Вместо двоичного числа в этих рассуждениях можно рассматривать и просто набор e(X) = (en–1 ; … ; e0) длины n из нулей и единиц. Итак, положим (0 £ i £ n–1). Кстати, именно такой способ интерпретации множеств реализуется в некоторых языках программирования.

Примеры. 1.Если A = {a0 , a1 , a2} и X = {a0 , a2}, то e(X) = 1012 = 5, а если X = {a1 }, то e(X) = 0102 = 2. Вообще, можно составить полный список подмножеств множества А:

 

Количество элементов Подмножество X e(X)
Æ 0002 = 0
{a2 } 1002 = 4
{a1 } 0102 = 2
{a0 } 0012 = 1
{a1 , a2 } 1102 = 6
{a0 , a2 } 1012 = 5
{a0 , a1 } 0112 = 3
{a0 , a1 , a2 } 1112 = 7

Видно, что значения e(X) пробегают всё множество {0, 1, 2, 3, 4, 5, 6, 7}, и В(А) состоит из восьми элементов.



2. Перечислить все подмножества четырёхэлементного множества A = {a0 , a1 , a2 , a3 }.

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

набор подмножество
(0, 0, 0, 0) Æ
(0, 0, 0, 1) {a0 }
(0, 0, 1, 0) {a1 }
(0, 0, 1, 1) {a1 , a0 }
(0, 1, 0, 0) {a2 }
(0, 1, 0, 1) {a0 , a2 }
(0, 1, 1, 0) {a1 , a2 }
(0, 1, 1, 1) {a0 , a1 , a2 }
(1, 0, 0, 0) {a3 }
(1, 0, 0, 1) {a0 , a3 }
(1, 0, 1, 0) {a1 , a3 }
(1, 0, 1, 1) {a0 , a1 , a3 }
(1, 1, 0, 0) {a2 , a3 }
(1, 1, 0, 1) {a0 , a2 , a3 }
(1, 1, 1, 0) {a1 , a2 , a3 }
(1, 1, 1, 1) {a0 , a1 , a2 , a3 }

 

В общем случае наименьшее значение e(X), очевидно, равно 0…02 = 0 для множества X = Æ, а наибольшее значение равно 1…12 = 1×2n–1+…+1×20 = = 2n–1+…+ 2+1 = = 2n – 1 при X = {a0 , … , an–1 } = A.Таким образом построена функция e : В(A) ® {0, 1, … , 2n – 1}. Докажем, что она биективна.

Инъективность: " X1 , X2 Î В(А) e(X1) = e(X2) ® X1 = X2 . Действительно, если = e(X1) = e(X2) = , то e0 = d0 , … , en–1 = dn–1 . Поэтому для любого элемента ai Î A верно ai Î X1 Û ei = 1 Û di = 1 Û ai Î X2 и значит, множества X1 и X2 состоят из одних элементов, т.е. равны.



Сюръективность: " n Î {0, 1, … , 2n–1} $ X Î В(А) e(X) = n. Действительно, по любому двоичному числу n = образуем множество X по правилу ai Î X Û ei = 1 (0 £ i £ n–1). Ясно, что e(X) = = n.

Теорема (о нумерации подмножеств конечного множества). (1) Существует биективное соответствие f : В(A) ® {0, … , 2n – 1} между всеми подмножествами конечного множества A = {a1 , … , an} из n элементов и интервалом целых чисел 0 .. 2n – 1.

(2) Существует биективное соответствие f : Вm(A) ® Bm Í {0, … , 2n–1} между всеми m-элементными подмножествами конечного множества A = {a1 , … , an} из n элементов и всеми целыми числами диапазона 0 .. 2n – 1, имеющими в своей двоичной записи ровно m единиц (и n–m нулей).

Следствие (о количественаборов из нулей и единиц длины n).Количество всевозможных наборов из нулей и единиц длины n равно 2n .

Доказательство следствия очевидно, т.к. количество всевозможных наборов из нулей и единиц длины n равно количеству чисел от 0 до 2n – 1, т.е. 2n.

Следствие доказано.

Следствие (о количестве подмножеств n-элементного множества). Любое n-элемен­тное множество содержит 2n подмножеств.

Доказательство. Построенное выше взаимно однозначное отображение e : В({a0 , … , an–1}) ® {0, 1, … , 2n – 1} показывает, что количество элементов в В({a0 , … , an–1}) равно количеству элементов в {0, 1, … , 2n – 1}, т.е. 2n .

 

Если A = {a1 , … , an } – конечное множество из n элементов, то сочетанием (или выборкой) из n объектов a1 , … , an по k штук (сочетанием из n по k) называется произвольное k-элементное подмножество Í A. Количество всех сочетаний из n по k обозначается .



Теорема (о перечислении сочетаний). Существует взаимно однозначное соответствие между всеми сочетаниями из n элементов конечного множества A = {a1 , … , an} по m и всеми целыми числами диапазона 0 .. 2n – 1, имеющими в своей двоичной записи ровно m единиц (и n–m нулей).

Следствие (о количестве всех сочетаний из n элементов). Общее количество всех сочетаний из n элементов по всем m (0 £ m £ n) равно 2n .

Имея алгоритм перечисления всех подмножеств множества A, легко понять, как получить алгоритм перечисления сочетаний. Нужно среди всех наборов из нулей и единиц длины n отобрать наборы ровно с k единицами и построить по ним соответствующие k-элементные множества.

Пример: Выписать все сочетания из четырёх элементов по двадля множества A = {1, 2, 3, 4}.

Среди всех наборов из нулей и единиц, перечисленных выше, отбираем только те, которые содержат 2 единицы и 4 нуля:

 

набор сочетание
(0, 0, 1, 1) {1, 2}
(0, 1, 0, 1) {1, 3}
(0, 1, 1, 0) {2 , 3}
(1, 0, 0, 1) {1, 4}
(1, 0, 1, 0) {2, 4}
(1, 1, 0, 0) {3, 4}

Вычислим теперь количество сочетаний из n по k. Ясно, что результат не зависит от конкретной природы элементов множества A. Поэтому будем считать, что множество A состоит из n независимых переменных. Для произвольных a1 , … , ak Î A рассмотрим произведение (1+a1×x)×(1+a2×x)×…×(1+an×x). Если раскрыть скобки, то в полученной сумме мономов (без приведения подобных) моном степени s получается при перемножении произвольно выбранных s элементов , где i1 < i2 < … < is . Таким образом, коэффициент при таком мономе соответствует выбору сочетания { }, причём это соответствие взаимно однозначно, т.к. множество { } однозначно определяется элементами и не зависит от порядка их перечисления. После приведения подобных при xs будет стоять коэффициент, равный сумме всех произведений вида , а количество таких слагаемых в точности равно количеству сочетаний из n по s.

(1+a1×x)×(1+a2×x)×…×(1+an×x) =

= 1 + (a1+…+ak)×x+(a1×a2+a1×a3+…+ak–1×ak)×x2 + …

… +(a1×…×an–1+…+a2×…×an)×xn–1 + a1×…×an×xn .

Если теперь подставить a1 = a2 = … = an = 1, то, с одной стороны, при xk получится количество сочетаний из n по k, а с другой, – мы придём к формуле бинома Ньютона:

(1 + x)n = 1+n×x+ ×x2 + … + ×xk + … +n×xn–1+xn .

Следовательно, биномиальный коэффициент, который равен количеству сочетаний из n элементов по k.

Из формулы бинома Ньютона немедленно получаются следующие полезные равенства:

Кроме того, – известные свойства биномиальных коэффициентов.

Отметим ещё раз связь между размещениями, сочетаниями и перестановками. Сочетание из n по k отличается от размещения без повторений тем, что для сочетания не важен порядок элементов. Поэтому, произвольным образом переставляя элементы размещения, будем получать одно и то же сочетание. Количество перестановок рассматриваемого сочетания равно k ! , так что одному сочетанию соответствует k ! размещений. Поэтому .

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

Рассмотрим задачу: сколько всего букетов можно составить из семи роз, пяти фиалок и трёх тюльпанов, если каждый букет состоит из одной розы, двух фиалок и двух тюльпанов (порядок цветов в букете не важен) ?

Это – простая задача на сочетания и принцип умножения: = = 7×10×3 = 210.

Другая задача: сколько букетов, содержащих 3 цветка, можно составить из роз, фиалок и тюльпанов (цветов достаточное количество и порядок цветков в букете не существенен) ?

Здесь букет можно мыслить как набор , в которых р – розы, ф – фиалки, т – тюльпаны и k1 + k2 + k3 = 3. Поэтому возможны следующие случаи:

роз 3: такой набор единственный (р; р; р);

роз 2: таких наборов два (р; р; ф), (р; р; т);

роз 1: таких наборов три (р; ф; ф), (р; ф; т); (р; т; т);

роз 0: таких наборов четыре (ф; ф; ф), (ф; ф; т), (ф; т; т); (т ; т; т).

Всего, таким образом, получится 10 букетов. Хотя результат и получен, но не вполне понятно, как решать эту задачу для букетов из большего количества k цветов в букете: даже для k = 5 перечислить все букеты затруднительно ! Поэтому надо задуматься об общем методе решения задачи.

Пусть – количество букетов, составляемых из k видов цветов, каждый из которых содержит j цветов. Тогда, нужно найти , и согласно схеме перечисления по количеству роз . Здесь учитывает единственный набор (р; р; р), – количество “хвостов” (ф) и (т) при двух розах, – количество “хвостов” (ф; ф), (ф; т); (т; т) при одной розе, и – количество букетов (ф; ф; ф), (ф; ф; т), (ф; т; т); (т; т; т) при отсутствии роз. Ясно, что . Аналогично . Так что теперь получим .

Таким образом, найден более перспективный способ подсчёта букетов, основанный на рекуррентном соотношении .

Если A = {a1 , … , an } – конечное множество из n элементов, то сочетанием n элементов с повторениями называется любой упорядоченный набор вида , где ki Î N0 . Если ki = 0, то это значит, что в наборе элемент ai отсутствует. Числа ki , … , kn называются кратностями элементов a1 , … , an в сочетании с повторениями. Число сочетаний с повторениями длины k = k1 + … + kn будем обозначать через .

Перечислить все сочетания с повторениями длины k можно рекурсивно. Ясно, что существует ровно n различных сочетаний с повторениями длины 1: (a1), … , (an). Если уже умеем перечислять все сочетания с повторениями, но от меньшего чем n количества элементов, то вначале выпишем единственное сочетание кратности k по a1 : , затем перечислим все сочетания с повторениями кратности k – 1 по a1 (и кратности 1 по элементам множества A1 = A \ {a1}= {a2 , … , an }) – их . Затем – кратности k – 2 по a1 (и кратности 2 по элементам множества A1) – их , и т.д., пока не перечислим все сочетания кратности 1 по a1 (и кратности k – 1 по элементам множества A1 ) – их , и наконец, все сочетания кратности 0 по a1 (и кратности k по элементам множества A1 ) – их .

Пример: Перечислим все сочетания с повторениями длины 4 для трёхэлементного множества A = {1, 2, 3}.

(1; 1; 1; 1),

(1; 1; 1; 2), (1; 1; 1; 3),

(1; 1; 2; 2), (1; 1; 2; 3), (1; 1; 3; 3),

(1; 2; 2; 2), (1; 2; 2; 3), (1; 2; 3; 3); (1; 3; 3; 3),

(2; 2; 2; 2), (2; 2; 2; 3), (2; 2; 3; 3); (2; 3; 3; 3), (3; 3; 3; 3).

Таким образом, = 15. Попутно получаем = 5, = 4, = 3.

Проанализировав приведённый выше алгоритм перечисления всех сочетаний с повторениями длины k, получим рекуррентную формулу:

.

Сразу не видно, как получить формулу для . Поэтому вначале поэкспериментируем:

s = 1: Ясно, что .

s = 2: Имеем

.

s = 3: Имеем

Возникает гипотеза о том, что . Для её обоснования достаточно проверить выполнение рекуррентного соотношения:

.

Это следует из основного равенства для биномиальных коэффициентов:

– верно.

Другой способ доказательства формулы состоит в том, что каждому сочетанию с повторениями можно биективно сопоставить некоторое сочетание из n+k–1 по k. Именно, сопоставим каждому сочетанию с повторениями обычное сочетание n+k–1 элементов множества = {a1 , … , an , b1 , … , bk–1} по k :

{a1 , … , an ; b1 , … , … , }.

В этом сочетании каждому ai кратности ki > 0 соответствует группа элементов количество которых ki – 1. Если кратность элемента равна 0, то ни он сам, ни соответствующая ему группа во множестве не участвуют. Общее количество элементов в построенном сочетании будет 1+(k1–1)+1+(k2–1)+…+1+(kn–1) = k.

Пример: Сочетаниям с повторениями длины 3 из множества A = {1, 2} сопоставим следующие сочетания элементов множества = {1, 2, b1 , b2}: (2; 2; 2) ® {2, b1 , b2}, (1; 2; 2) ® {1, 2, b2}, (1; 1; 2) ® {1, 2, b1}, (1; 1; 1) ® {1, b1 , b2}. Видно, что установленное соответствие является в данном примере взаимно однозначным.

Это соответствие взаимно однозначно и в общем случае:

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

{a1 , … , an ; b1 , … , , … , },

то из правила построения этого сочетания сразу следует, что s1–1 = p1–1 = t1–1, т.е. s1 = t1 , s2–1 = p2–1 = t2–1, т.е. s2 = t2 , … , sn–1 = pn–1 = tn–1, т.е. sn = tn , так что рассматриваемые сочетания с повторениями совпадают.

сюръективность: по любому сочетанию

{a1 , … , an ; b1 , … , … , }

однозначно восстанавливается его прообраз. Действительно, если a1 не участвует в сочетании, то его кратность в сочетании с повторениями равна 0.Если же a1 участвует в сочетании, то выделяем максимальный отрезок подряд участвующих в этом сочетании элементов b1 , … , и записываем в искомом сочетании с повторениями элемент a1 с кратностью s1 . При этом ситуация, когда элемент b1 не входит в сочетание возникнуть не может, т.к. в противном случае элементов из множества {b1 , … , bk–1} будет участвовать меньше k–1, а поскольку рассматриваемое сочетание имеет n+k–1 элемент, то количество участвующих в нём элементов из множества A должно быть больше n, что невозможно. Точно так же процесс построения искомого сочетания с повторениями происходит и далее.

Примеры: 1.Сочетанию {a1 , a3 , b1 , b2} из пяти элементов по четыре соответствует сочетание с повторениями (a1 ; a1 ; a1; a3) длины 4 элементов множества A = {a1 , a2 , a3}.

2. Сочетанию {a2 , a3 , b1 , b3 } из пяти элементов по четыре соответствует сочетание с повторениями (a2 ; a2 ; a3 ; a3 ) длины 4 элементов множества A = {a1 , a2 , a3}.

3. Сочетанию {a2 , b1 , b2 , b3 } из пяти элементов по четыре соответствует сочетание с повторениями (a2 ; a2 ; a2; a2) длины 4 элементов множества A = {a1 , a2 , a3}.

 

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.