ДИСКРЕТНАЯ МАТЕМАТИКА (1). В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с
 Скачать 4.33 Mb.
|
|
2.9. Сочетания с повторениями Сочетанием с повторениями из n элементов по k называется мультимножество мощности k, составленное из элементов элементного множества. Например, из элементов множества М = {1,2,3} можно составить такие сочетания по два с повторениями {1,1}, {1,2}, {1,3}, {2,2}, {2,3}, {3,3}. Теорема 2.7. Количество различных сочетаний из n элементов пос повторениями равно 1 Доказательство Каждое сочетание полностью определяется, если указать, сколько раз входит каждый элемент множества в сочетание. Поставим в соответствие каждому сочетанию последовательность нулей и единиц, составленную последующему правилу ставим подряд столько единиц, сколько раз входит первый элемент множества в сочетание, далее ставим нуль, и после него пишем столько единиц, сколько раз входит второй элемент множества в это сочетание и т.д. Например, написанным выше сочетаниям из трех элементов по два будут соответствовать такие последовательности 1100, 1010, 1001, 0110, 0101, 0011. Таким образом, каждому сочетанию с повторениями из n по k соответствует последовательность из k единиц и n – 1 нулей. Количество таких последовательностей равно числу способов, которыми можно выбрать n – 1 мест для нулей из n + k –1 общего числа мест ( 1 1 n k n C ), или, тоже самое, — числу способов выбора k мест для единиц из n + k – 1 мест ( k k n C 1 ). Рассмотрим алгоритм порождения сочетаний с повторениями вне- убывающем лексикографическом порядке. Сочетания с повторениями из трех элементов потри, в неубывающем лексикографическом порядке запишутся следующим образом 111 133 112 222 113 223 122 233 123 333 Сочетания с повторениями в лексикографическом порядке можно порождать, используя метод поиска с возвращением. Начиная с го места будем последовательно формировать элементы сочетания F. На 80 первое место в сочетании можно ставить элементы из множества {1..n}. Формирование го элемента сочетания опишем рекурсивным алгоритмом, блок-схема которого представлена на рис. В цикле перебираются элементы множества {b..n}, которые можно поставить на е место. Если на е место поставлен элемент x, то минимальный элемент, который можно поставить на i + е место, тоже равен x. Если заполнено е место, то сочетание сформировано и выводим его, иначе заполняем следующее i + е место по алгоритму 2.7. Алгоритм 2.7 порождения сочетаний с повторениями из n элементов по k. Вход i — заполняемое место в сочетании F; b — минимальный элемент, который можно поставить на е место. Выход последовательность всех сочетаний с повторениями из n элементов по k в неубывающем лексикографическом порядке. Глобальные параметры F — формируемое сочетание n — мощность множества k — количество элементов в сочетании. + Рис. Рекурсивный алгоритм порождения сочетаний с повторениями из n элементов по k x {b..n} F i := x Конец Сочетание (i+1, x) F Сочетание (i, b) 81 сочетание 3 {1,1,1) множество {1,2,3} 4 сочетание сочетание {1,1,2) {1,1,?} 5 2 сочетание {1,1,3) множество множество 7 сочетание {1,2,3} 6 {2,3} {1,2,2) сочетание сочетание 8 {1,?,?} {1,2,?} сочетание 9 {1,2,3) 1 множество {3} 10 сочетание сочетание {1,3,3) множество {1,3,?} {1,2,3} сочетание 11 множество 13 сочетание {?,?,?} 12 {2,3} {2,2,2) множество сочетание 14 {2,3} {2,2,?} сочетание сочетание 15 {2,2,3) 17 {2,?,?} множество {3} 16 сочетание сочетание {2,3,3) {2,3,?} множество множество {3} 18 {3} 19 сочетание сочетание сочетание {3,3,3) {3,?,?} {3,3,?} Рис. Схема получения всех сочетаний с повторениями по алгоритму 2.7 Пусть задано множество {1,2,3} и требуется получить все сочетания с повторениями из элементов этого множества по 3. Схема получения всех сочетаний по алгоритму 2.7 представлена на рис. В этой схеме представлены формируемые сочетания и множества, элементы которых можно поставить на очередное место в сочетании. В исходной ситуации все места сочетания не определены и на первое место можно поставить любой элемент множества {1,2,3}. В схеме к стрелкам приписаны номера действий. В результате выполнения первого действия на первое место сочетания ставится элемент 1 и на второе место после этого можно поставить любой элемент того же множества {1,2,3}. После выполнения действия 2 на второе место сочетания устанавливается элемент 1 и на 82 третье место после этого опять можно поставить любой элемент множества. После выполнения действия 3 первое сочетание {1,1,1} сформировано. Затем выполняется шаг назад и действие 4, ставящее элемент 2 из множества {1,2,3} на третье место и второе сочетание {1,1,2} сформировано и т.д. После выполнения шестого действия на второе место устанавливается элемент 2 и, после этого, на третье место можно поставить элемент из множества {2,3}, и следующее сочетание, после выполнения седьмого действия, будет {1,2,2}. Аналогичным образом формируются все остальные сочетания. 2.10. Упорядоченные разбиения множества Упорядоченным разбиением множества М называется последовательность из непустых, попарно непересекающихся подмножеств множества М, объединение которых дает множество М. 2.10.1. Упорядоченные разбиения множества на k подмножеств с мощностями (n 1 ,n 2 ,…,n k ) Рассмотрим упорядоченные разбиения множества M на k подмножеств с мощностями (n 1 ,n 2 ,…,n k ) . Одно такое разбиение представляет собой последовательность (М 1 ,М 2 ,…,М k ) подмножеств множества М, таких, что |M 1 | = n 1 , |M 2 | = n 2 ,…, |M k | = n k . На первом месте в разбиении может располагаться любое подмножество мощности n 1 , на втором — любое подмножество мощности n 2 и т.д. Теорема 2.8. Количество всех различных упорядоченных разбиений элементного множества М на k подмножеств с мощностями (n 1 ,n 2 ,…, n k ) определяется формулой ! ! ! ! ) ,..., , ( 2 1 2 1 k k n n n n n n n n P . Доказательство При формировании последовательности (ММ, М) на первое место подмножество М мощности n 1 можно выбрать из n элементов множества М способами, на второе место подмножество М мощности n 2 можно выбрать из оставшихся n – n 1 элементов множества М 2 1 n n n C способамии так далее, на последнее место подмножество М мощности n k можно выбрать из оставшихся элементов множества М k k n n n n n C 1 способами. По правилу произведения получаем, что общее количество упорядоченных разбиений равно ! ! ! ! ) ,..., , ( 2 1 2 1 1 2 1 3 2 1 2 1 1 k n n n n n n n n n n n n n n k n n n n n C C C C n n n P k k , что совпадает с числом перестановок с повторениями. 83 Доказательство Упорядоченное разбиение можно задать разрядным вектором P, в котором P i представляет собой номер подмножества, которому принадлежит элемент i множества М. Вектор Р представляет собой перестановку с повторениями мультимножества {n 1 *1,n 2 *2,…, n k *k}. Следовательно, количество всех различных упорядоченных разбиений элементного множества М на k подмножеств с мощностями n 1 ,n 2 ,…,n k равно количеству перестановок с повторениями мультимножества {n 1 *1,n 2 *2,…, n k *k} и определяется формулой ! ! ! ! ) ,..., , ( 2 1 2 1 k k n n n n n n n n P . Алгоритм порождения упорядоченных разбиений элементного множества М на k подмножеств с мощностями (n 1 ,n 2 ,…,n k ) представляет собой алгоритм 2.6 порождения перестановок с повторениями мультимножества, в котором перестановки с повторениями интерпретируются как разбиения. В табл. 2.1 представлены упорядоченные разбиения множества М = {1,2,3,4,5} натри подмножества первые два — двухэлементные и третье — одноэлементное. Таблица 2.1 Упорядоченные разбиения множества М = {1,2,3,4,5} № п/п Перестановка с повторениями Упорядоченное разбиение 1 2 3 1 (1,1,2,2,3) ({1,2},{3,4},{5}) 2 (1,1,2,3,2) ({1,2},{3,5},{4}) 3 (1,1,3,2,2) ({1,2},{4,5},{3}) 4 (1,2,1,2,3) ({1,3},{2,4},{5}) 5 (1,2,1,3,2) ({1,3},{2,5},{4}) 6 (1,2,2,1,3) ({1,4},{2,3},{5}) 7 (1,2,2,3,1) ({1,5},{2,3},{4}) 8 (1,2,3,1,2) ({1,4},{2,5},{3}) 9 (1,2,3,2,1) ({1,5},{2,4},{3}) 10 (1,3,1,2,2) ({1,3},{4,5},{2}) 11 (1,3,2,1,2) ({1,4},{3,5},{2}) 12 (1,3,2,2,1) ({1,5},{3,4},{2}) 13 (2,1,1,2,3) ({2,3},{1,4},{5}) 14 (2,1,1,3,2) ({2,3},{1,5},{4}) 15 (2,1,2,1,3) ({2,4},{1,3},{5}) 16 (2,1,2,3,1) ({2,5},{1,3},{4}) 17 (2,1,3,1,2) ({2,4},{1,5},{3}) 84 Окончание табл 1 2 3 18 (2,1,3,2,1) ({2,5},{1,4},{3}) 19 (2,2,1,1,3) ({3,4},{1,2},{5}) 20 (2,2,1,3,1) ({3,5},{1,2},{4}) 21 (2,2,3,1,1) ({4,5},{1,2},{3}) 22 (2,3,1,1,2) ({3,4},{1,5},{2}) 23 (2,3,1,2,1) ({3,5},{1,4},{5}) 24 (2,3,2,1,1) ({4,5},{1,3},{2}) 25 (3,1,1,2,2) ({2,3},{4,5},{1}) 26 (3,1,2,1,2) ({2,4},{3,5},{1}) 27 (3,1,2,2,1) ({2,5},{3,4},{1}) 28 (3,2,1,1,2) ({3,4},{2,5},{1}) 29 (3,2,1,2,1) ({3,5},{2,4},{1}) 30 (3,2,2,1,1) ({4,5},{2,3},{1}) 2.10.2. Упорядоченные разбиения множества на k подмножеств с мощностями {n 1 ,n 2 ,…,n k } Рассмотрим упорядоченные разбиения множества M на k подмножеств с мощностями {n 1 ,n 2 ,…,n k }, где {n 1 ,n 2 ,…,n k } может быть мультимножеством. Одно такое разбиение представляет собой последовательность (М 1 ,М 2 ,…,М k ) подмножеств множества М, таких, что |M 1 | = n 1 , |M 2 | = n 2 ,…, |M k | = n k . На первое место в разбиении можно поставить подмножество любой мощности n i {n 1 ,n 2 ,…,n k }, после этого на второе место — подмножество любой мощности n j {n 1 ,n 2 ,…,n k } – {n i } и т.д. Среди подмножеств в разбиении (М 1 ,М 2 ,…,М k ) можно выделить l 1 подмножеств мощности 1, l 2 подмножеств мощности 2 и т.д., l n подмножеств мощности n. Например, в разбиении ({1,2},{3,4},{5}) l 1 = 1, l 2 = 2, l 3 = l 4 = l 5 = 0. Очевидно, что 1 l 1 + 2 l 2 + … + n l n = n. Теорема 2.9. Количество всех различных упорядоченных разбиений элементного множества М на k подмножеств с мощностями {n 1 ,n 2 ,…, n k } определяется формулой ! ! ! ! ) ! ( ) ! 2 ( ) ! 1 ( ! ! ! ! ! ! ! ! ! } ,..., , { 2 1 2 1 2 1 2 1 2 Доказательство Рассмотрим упорядоченное разбиение множества M на k подмножеств с мощностями (n 1 ,n 2 ,…,n k ). Если мощности подмножеств попарно различны, то из такого разбиения можно получить k! 85 упорядоченных разбиений множества M на k подмножеств с мощностями, изменяя всеми способами порядок следования подмножеств. Но так как упорядоченное разбиение множества M на k подмножеств с мощностями (n 1 ,n 2 ,…,n k ) может содержать подмножества с одинаковыми мощностями, то из такого разбиения можно получить ! ! ! ! 2 упорядоченных разбиений множества M на k подмножеств с мощностями. Количество всех различных упорядоченных разбиений элементного множества М на k подмножеств с мощностями (n 1 ,n 2 ,…, n k ) определяется формулой ! ! ! ! ) ,..., , ( 2 1 2 1 k k n n n n n n n n P , следовательно. Рассмотрим формулу ! ! ! ! ) ,..., , ( 2 1 2 1 k k n n n n n n n n P . В знаменателе сначала расположим все сомножители со значением 1!, их будет l 1 штук, затем — все сомножители со значением 2!, их будет штуки так далее, ив конце — все сомножители со значением n!, их будет штук. Теперь эту формулу можно записать в виде n l l l k n n n n n n P ) ! ( ) ! 2 ( ) ! 1 ( ! ) ,..., , ( 2 1 2 1 , а формулу, определяющую количество всех различных упорядоченных разбиений элементного множества М на k подмножеств с мощностями {n 1 ,n 2 ,…, n k } — в виде ! ! ! ! ) ! ( ) ! 2 ( ) ! 1 ( ! } ,..., , { 2 1 2 1 2 1 n l l l k n l l l k n n n n n P n . Для порождения упорядоченных разбиений элементного множества М на k подмножеств с мощностями {n 1 ,n 2 ,…,n k } можно порождать перестановки с повторениями мультимножества {n 1 ,n 2 ,…,n k } и каждую перестановку использовать для порождения упорядоченных разбиений элементного множества М на k подмножеств с мощностями (n 1 ,n 2 ,…, n k ), в результате чего будут получены все упорядоченные разбиения элементного множества М на k подмножеств с мощностями {n 1 ,n 2 ,…, n k }. 86 2.10.3. Все упорядоченные разбиения множества на k подмножеств Рассмотрим все упорядоченные разбиения множества M на k подмножеств. Одно такое разбиение представляет собой последовательность (М 1 ,М 2 ,…,М k ) подмножеств множества М, таких, что |M 1 | + |M 2 | +…+ |M k | = |M| . При подсчете количества упорядоченных разбиений множества M на k подмножеств будем использовать понятие композиции числа n из k частей. Композицией натурального числа n из k частей с ограничением n i > 0 называется элементная последовательность (n 1 ,n 2 ,…,n k ) натуральных чисел, такая, что n 1 + n 2 + … + n k = n. Теорема 2.10. Количество композиций числа n из k частей с ограничением равно 1 Доказательство Разделим отрезок длины n на n отрезков единичной длины с помощью (n – 1) точки. Тогда композиции n взаимно однозначно соответствует пометка некоторых k – 1 точек разделения. Элементами композиции в этом случае будут расстояния между соседними точками разделения. Например, композиция (2,2,1) числа 5 представлена на рис. Рис. Представление композиции (2,2,1) числа Каждая композиция числа n из k частей с ограничением n i > 0 соответствует способу выбора (k – элементного подмножества точек из n – 1 точек. То есть число таких композиций равно 1 Теорема 2.11. Количество всех различных упорядоченных разбиений элементного множества М на k подмножеств определяется формулой m i ki i i n n n n n k P 1 2 1 ! ! ! ! ) ( , где 1 1 k n C m , (n 1i ,n 2i ,…,n ki ) — я композиция числа n из k частейс ограничением. Доказательство Элементы композиции (n 1 ,n 2 ,…n k ) числа n из k частей будем считать мощностями подмножеств в упорядоченном разбиении (М 1 ,М 2 ,…,М k ) множества М на k частей. Количество всех различных упорядоченных разбиений элементного множества М на k подмножеств с мощностями (n 1 ,n 2 ,…,n k ) определяется формулой ! ! ! ! ) ,..., , ( 2 1 2 1 k k n n n n n n n n P , а количество композиций числа n из k частей определяется формулой 1 1 k n C m , следовательно, количество всех различных упорядоченных разбиений элементного множества М на k подмножеств определяется формулой m i ki i i n n n n n k P 1 2 1 ! ! ! ! ) ( , где 1 1 k n C m , (n 1i ,n 2i ,…,n ki ) — я композиция числа n из k частейс ограничением. Для порождения упорядоченных разбиений элементного множества М на k подмножеств можно получить все композиции числа n из k частей с ограничением n i > 0 и к каждой композиции (n 1 ,n 2 ,…, n k ) применить алгоритм 2.6 порождения перестановок с повторениями мультимножества, в котором перестановки с повторениями интерпретировать как разбиения. Для порождения композиций числа n из k частей с ограничением n i > 0 можно использовать алгоритм 2.5 порождения сочетаний и каждое сочетание преобразовать в соответствующую ему композицию или непосредственно, используя метод поиска с возвращением. Начиная с го места будем последовательно формировать элементы композиции С. Формирование го элемента композиции опишем рекурсивным алгоритмом, блок-схема которого представлена на рис, В цикле перебираются элементы множества, которые можно поставить на е место. Минимальный элемент, который можно поставить на е место при i < k равен 1, а максимальный – такой, что сумма сформированных i элементов плюс количество оставшихся элементов композиции не превышает числа n, те. n – S – k + i, где S — сумма сформированных i – 1 элементов. На последнее, е место композиции можно поставить только, где х — элемент, поставленный на k – е место, S + x — сумма k – 1 элементов композиции. Если заполнено k – е место, то однозначно заполняем последнее место, как описано выше, и выводим композицию, иначе заполняем следующее i + е место по алгоритму Алгоритм 2.8 порождения композиций числа n из k частей с ограничением n i > 0 Вход i — заполняемое место в композиции S — сумма первых i – 1 элементов композиции. Выход последовательность всехкомпозиций числа n из k частей с ограничением. Глобальные параметры С — формируемая композиция n — исходное число k — количество элементов в композиции. + Рис. Рекурсивный алгоритм порождения композиций числа n из k частей с ограничением n i > 0 |