Лабораторный практикум № 1. дискретка. Отображения. Обратные отображения эта тема является очень важной, терминами из этой темы мы будем пользоваться во многих других вопросах
 Скачать 86.29 Kb.
|
|
ОТНОШЕНИЯ ЭКВИВАЛЕНТНОСТИ Отношение 𝜌 ⊆ A × 𝐵 называется отношением эквивалентности, если 𝜌 рефлексивно, симметрично и транзитивно. Далее, нам понадобится определение разбиения множества. Множества А1, А2, …, Аk образуют разбиение множества А, если 1) ∀ 𝑖 (𝐴𝑖 ≠ ∅) (то есть непустое, иначе можно разбить на бесконечно много множеств) 2) ∀ 𝑖,𝑗 (𝑖 ≠ 𝑗 → 𝐴𝑖 ∩ 𝐴𝑗 = ∅) (то есть различные множества попарно не пересекаются) 3) ⋃ 𝐴𝑖 = 𝐴 𝑘 𝑖=1 (то есть объединение всех частей даёт исходное множество) Перед доказательством важной теоремы о классах эквивалентности разберём один пример. Пусть у нас есть множество А, элементами которого являются разноцветные карандаши. Разобьём элементы по группам по цвету (красный, зелёный, жёлтый и тд). Очевидно, что карандаши у нас одного цвета, поэтому попасть в две или более группы они не могут. Теперь рассмотрим отношение Одного цвета(a, b). Оно рефлексивно, симметрично (если а и b одного цвета, то b и a одного цвета) и транзитивно (если а и b одного цвета и b и c одного цвета, то a и c одного цвета). А значит, это отношение эквивалентности. Теперь применим это отношение к нашим группам карандашей. Очевидно, что если брать два карандаша a и b из одной группы, то эта пара карандашей будет лежать в этом отношении Одного цвета(a, b). А если брать два карандаша из разных групп, то эти два карандаша не будут лежать в этом отношении. Так вот, наши группы в данном примере являются так называемыми классами эквивалентности. Также заметим, что здесь у нас присутствовало не простое отношение, а именно отношение эквивалентности. И оказывается, что если для какого-то множества А определено отношение эквивалентности, то им всегда (как в нашем примере) можно как-то разделить на классы эквивалентности множество А так, чтобы элементы из одного класса лежали в отношении, а элементы из разных классов - не лежали, причём классы эквивалентности – непересекающиеся. ТЕОРЕМА. Если 𝜌 ⊆ 𝐴 × 𝐴 - отношение эквивалентности, то 𝜌 порождает разбиение множества А на непересекающиеся классы эквивалентности, причём элементы из одного класса лежат в отношении 𝜌, а элементы из разных классов не лежат в отношении 𝜌. ДОКАЗАТЕЛЬСТВО. Доказательство состоит из 4 этапов: 1) нужно построить обычное разбиение множества А 2) нужно доказать, что данное разбиение является разбиением на классы 3) нужно доказать, что любые два элементы из одного класса находятся в отношении 𝜌 4) нужно доказать, что любые два элемента из разных классов не находятся в отношении 𝜌 Для понимания первые два пункта будут самые тяжёлые, вторые же два пункта - самые лёгкие. 1) Начнём с первого пункта. Нам необходимо построить хотя бы какое-то разбиение множества А. Пусть наше множество А имеет какие-то элементы. Возьмём произвольный элемент х из А и будем рассматривать те элементы, которые находятся с х в отношении 𝜌. Множество таких элементов для элемента х обозначим как [x] = {y | x𝜌y}. Про это множество мы должны кое-что понять. Отношение эквивалентности включает в себя свойство рефлексивности, то есть ∀ 𝑥 ∈ 𝐴 𝑥𝜌𝑥, а это означает, что x ∈ [x], то есть множество [x] непустое. По такому принципу мы разделили элементы нашего множества на несколько групп. Но есть один нюанс. Если, например, [x] = {a1, a2, a3, a4, x}, то мы также можем определить множества [a1], [a2], [a3], [a4], и они тоже будут содержать элементы a1, a2, a3, a4, поскольку отношение 𝜌 - отношение эквивалентности, а значит, симметрично (a1𝜌x, a2𝜌x, a3𝜌x, a4𝜌x). Мы получили одинаковые множества [x] = {a1, a2, a3, a4, x}, [a1] = {a1, a2, a3, a4, x}, …, [a4] = {a1, a2, a3, a4, x}. Наша задача – построить хотя бы какое-нибудь разбиение множества А на группы, поэтому мы вправе удалить одинаковые вхождения групп в наше множество А. То есть, можем, например, оставить множество [x] ={a1, a2, a3, a4, x}. В учебнике Костенко это прописано так: Из семейства множеств {[x] x A } удалим кратные вхождения одинаковых множеств.Таким образом, мы уже точно разделили наше множество А на несколько групп. Семейство данных множеств и образует наше множество А: ⋃𝑥 ∈𝐴 [𝑥] = 𝐴 (знак ⋃ означает объединение). Обозначим это семейство буквой F. Это был, пожалуй, самый трудный пункт. Теперь осталось доказать 3 оставшихся пункта. 2) Для того, чтобы доказать, что это и есть разбиение на классы, мы должны доказать, что ∀ [𝑥],[𝑦] ∈ 𝐹 ([x] ≠ [y] → [x] ∩ [y] = ∅). То есть либо наши группы не пересекаются, либо же, если они имеют хотя бы один общий элемент, то они совпадают. Доказывается методом от противного. То есть пусть [x] ≠ [y] и [x] ∩ [y]= z. Нам нужно доказать, что [x] ⊆ [y] и [y] ⊆ [x] (Это правило, которое нужно для доказательства совпадения множеств). В этом и последующих пунктах просто пользуемся определением отношения эквивалентности (то есть рефлексивностью, симметричностью и транзитивностью). Рассмотрим элемент a ∈ [𝑥]. 1) Из симметричности: 𝑥𝜌𝑧 → 𝑧𝜌𝑥 2) Из транзитивности: 𝑦𝜌𝑧 & 𝑧𝜌𝑥 → 𝑦𝜌𝑥 3) Также из транзитивности: 𝑦𝜌𝑥 & 𝑥𝜌𝑎 → 𝑦𝜌𝑎 => a ∈ [𝑦]. В силу произвольности a ∈ [𝑥] мы получаем, что [x] ⊆ [y] (то есть что [x] является подмножеством [y]). Обратное вхождение доказывается аналогично, поэтому получаем, что [x] = [y]. Но мы предположили, что они не равны, поэтому получаем противоречие, и значит, разные классы не имеют общих элементов. Этим мы и доказали, что F образует разбиение множества А на классы ([x] это и есть наши классы эквивалентности). 3) Теперь докажем, что элементы из одного класса находятся в отношении эквивалентности. Пусть a, b ∈ [𝑥]. Пользуемся снова свойствами отношения эквивалентности: 1) Симметричность: 𝑥𝜌𝑎 → 𝑎𝜌𝑥 2) Транзитивность: 𝑎𝜌𝑥 & 𝑥𝜌𝑏 → 𝑎𝜌𝑏, то есть (a, b) ∈ 𝜌, что и требовалось доказать. 4) Докажем, наконец, что элементы из разных классов не находятся в отношении 𝜌. Доказывается методом от противного. Пусть a∈ [𝑥], b ∈ [𝑦], (a, b) ∈ 𝜌. Тогда по транзитивности: 𝑥𝜌𝑎 & 𝑎𝜌𝑏 → 𝑥𝜌𝑏, то есть b ∈ [𝑥] и, следовательно, [𝑥] ∩ [y] ≠ ∅), но классы эквивалентности у нас должны быть непересекающимися. Получили противоречие, а значит, любые два элемента из разных классов не находятся в отношении 𝜌, что и требовалось доказать. Доказательство немаленькое, но понять суть не сложно, так как самым трудным является первый пункт, а последующие пункты основываются лишь на определении отношения эквивалентности. Оказывается, что верно и обратное утверждение этой теоремы. Если на множестве А определено разбиение А1, А2, …, Аk, то на множестве А можно определить отношение эквивалентности с помощью соотношения: ∀ 𝑥, 𝑦 ∈ 𝐴 (𝑥𝜌𝑦 < = > ∃𝑖 (𝑥 ∈ 𝐴i & 𝑦 ∈ 𝐴i)). То есть просто можем определить отношение Лежат в одном подмножестве множества А(x, y). Доказывается через определение отношения эквивалентности: 1) Рефлексивность: ∀ 𝑥 ∈ 𝐴 (𝑥 ∈ 𝐴i & 𝑥 ∈ 𝐴i) – верно 2) Симметричность: ∀ 𝑥, 𝑦 ∈ 𝐴 (𝑥 ∈ 𝐴i & 𝑦 ∈ 𝐴i -> 𝑦 ∈ 𝐴i & 𝑥 ∈ 𝐴i) – верно 3) Транзитивность: ∀ 𝑥, 𝑦, 𝑧 ∈ 𝐴 ((𝑥 ∈ 𝐴i & 𝑦 ∈ 𝐴i)& (𝑦 ∈ 𝐴i & 𝑧 ∈ 𝐴i) -> (𝑥 ∈ 𝐴i & 𝑧 ∈ 𝐴i)) – верно А значит, данное отношение является отношением эквивалентности, что и требовалось доказать. ОТНОШЕНИЯ ПОРЯДКА Определение. 𝜌 ⊆ A × 𝐴 - отношение порядка, если 𝜌 - рефлексивно, транзитивно и антисимметрично. Для отношений порядка не существует такой уникальной характеризационной теоремы, как у отношений эквивалентности. Для начала стоит понять, как отношение порядка изображается в виде диаграммы. 1) В отношении порядка, как и в отношении эквивалентности, не рисуются петли. Напомню, петли показывают то, что отношение рефлексивно. 2) Так как отношение порядка антисимметрично, то мы не можем сказать, что, если a𝜌𝑏, то b𝜌𝑎 при a и b не равных друг другу. Мы можем такое сказать только в том случае, если a и b друг другу равны (определение антисимметричности: ∀ 𝑥, 𝑦 ∈ 𝐴 𝑥𝜌𝑦 & 𝑦𝜌𝑥 → 𝑥 = 𝑦). На диаграмме симметричность означает то, что из x будет идти ориентированная дуга в y и наоборот, из y будет идти ориентированная дуга в x. При антисимметричности такое возможно только в случае, если x = y. Поэтому диаграмма будет напоминать некую иерархию, некое дерево. Пример отношения порядка: Как видно, противоположно направленных дуг (симметричность) здесь нет, образуется некоторая иерархия. 3) Теперь насчёт транзитивности. Здесь у нас элемент a по транзитивности находится в отношении со всеми элементами. По логике мы тогда должны рисовать дуги, идущие из a во все элементы диаграммы (и так для любых элементов, которые связаны между собой транзитивностью). Но тогда получится очень много дуг, поэтому принято такие дуги не рисовать на диаграмме: То есть если a𝜌𝑏 и b𝜌с, то по транзитивности a𝜌𝑐, но мы эту дугу рисовать не будем. При таком раскладе на диаграмме не будет возникать циклов (то есть отсутствует симметричность, из-за которой мы могли попасть в предыдущий элемент), то есть если по отношению a𝜌𝑐, то c𝜌𝑎 быть не может (если a не равно c). В соответствии с такими диаграммами в отношении порядка можно выделить уникальные элементы (максимальные, наибольшие, минимальные, наименьшие). Разберём эти понятия. 1) Элемент a ∈ 𝐴 называется максимальным в отношении порядка 𝜌 ⊆ A × 𝐴, если ∀ 𝑏 ∈ 𝐴 (b𝜌𝑎 → 𝑎 = 𝑏). То есть если в отношении на диаграмме из элемента b идёт дуга в элемент a, то элементы a и b равны друг другу. То есть это просто может быть петля, так как a = b. 2) Элемент a ∈ 𝐴 называется наибольшим в отношении порядка 𝜌 ⊆ A × 𝐴, если ∀ 𝑏 ∈ 𝐴 a𝜌𝑏. То есть из элемента a на диаграмме отношения порядка идут дуги на все оставшиеся элементы. Отличие максимального элемента от наибольшего можно понять исходя из диаграммы: Здесь мы видим, что под определение максимального элемента подходят элементы a и b. Но никакой из этих двух элементов не будет являться наибольшим на левой диаграмме, поскольку, например, по направлению дуг на диаграмме нельзя сказать, что выполняется a𝜌𝑏 и b𝜌𝑎 (Те два элемента a и b, которые в примере, и эти же два элемента в определении нужно различать, это не одни и те же элементы). На правой диаграмме наибольшим будет элемент a. ТЕОРЕМА. Если элемент a ∈ 𝐴 является наибольшим в отношении порядка, то он является максимальным. ДОКАЗАТЕЛЬСТВО. Предположим противное: элемент a наибольший, но не максимальный. Определение максимального элемента: ∀ 𝑏 ∈ 𝐴 (b𝜌𝑎 → 𝑎 = 𝑏). Напишем отрицание этого определения: ∃𝑏1 ∈ 𝐴 (b1𝜌𝑎 & 𝑎 ≠ 𝑏1) (В доказательстве нужно писать не b1, а b, я пишу b1, чтобы не возникало путаницы). Но так как a – наибольший элемент, то ∀ 𝑏 ∈ 𝐴 a𝜌𝑏. Мы получили, что для b1 a𝜌𝑏1 и b1𝜌𝑎, а это противоречит свойству антисимметричности отношения порядка. Значит, предположение неверно, а значит, условие теоремы верно. Обратное утверждение будет неверным. Можно привести пример, когда элемент a ∈ 𝐴 является максимальным, но не является наибольшим, и этим примером может послужить как раз представленная выше диаграмма с элементами a и b. 3) Элемент a ∈ 𝐴 называется минимальным в отношении порядка 𝜌 ⊆ A × 𝐴, если ∀ 𝑏 ∈ 𝐴 (a𝜌𝑏 → 𝑎 = 𝑏). Здесь определение – полная противоположность определению максимального элемента: если из a идёт какая-то дуга в элемент b, то a и b совпадают. То есть опять же, это может быть только петля. 4) Элемент a ∈ 𝐴 называется наименьшим в отношении порядка 𝜌 ⊆ A × 𝐴, если ∀ 𝑏 ∈ 𝐴 b𝜌𝑎. А здесь – полная противоположность определению наибольшего элемента: в элемент a идут дуги из всех оставшихся элементов диаграммы отношения порядка. Отличие минимального элемента от наименьшего также можно понять из данной диаграммы: Здесь опять же, элементы f и h, по аналогии с максимальными и наибольшими элементами, будут являться минимальными, так как если, например, из f (из h аналогично) идёт какая-то дуга в элемент z, то f и z совпадают. В данном случае возможны только петли. Наименьших элементов на левой диаграмме нет. Наименьшим элементом на правой диаграмме же будет являться элемент h, так как для любого элемента z 𝑧𝜌ℎ. ТЕОРЕМА. Если элемент a ∈ 𝐴 является наименьшим в отношении порядка, то он является минимальным. Доказательство аналогично тому, что выше. Как не перепутать понятия (максимальный, наибольший и тд) и их определения? Принцип простой: если само понятие содержит больше букв (в слове максимальный 12 букв, а в слове наибольший 10 букв), то у этого понятия будет пообъемнее определение (у максимального элемента запись определения больше по размеру). Да, немного странный принцип, но другого я ничего придумать не смог ОТНОШЕНИЯ ЛИНЕЙНОГО ПОРЯДКА Теперь рассмотрим одну из разновидностей отношения порядка – отношение линейного порядка. Для начала снова обратимся к диаграммам, которые выше. Из данной диаграммы видно, что, например, ни пара (a, b), ни пара (b, a) не лежат в отношении порядка, так как нельзя дугами перейти из одного элемента в другой. Теперь рассмотрим следующую диаграмму: Здесь уже, какую пару элементов не возьми, эта пара в каком-то порядке (то есть либо 𝑥𝜌𝑦, либо 𝑦𝜌𝑥) будет лежать в отношении порядка. Именно эта диаграмма представляет собой отношение линейного порядка. Отношение порядка 𝜌 ⊆ A × 𝐴 называется отношением линейного порядка, если ∀ 𝑎, 𝑏 ∈ 𝐴 (𝑎𝜌𝑏 или 𝑏𝜌𝑎) (вместо «или» должен быть знак дизъюнкции). ТЕОРЕМА. Если A = {a1, a2, …, an}, 𝜌 ⊆ A × 𝐴 – отношение линейного порядка на множестве A, то диаграмма для 𝜌 имеет вид: ai1 -> ai2 -> … -> ain Да, индексы не 1, 2, …, n, а i1, i2, …, in, но здесь ничего нет сложного. Под i1, i2, …, in понимается всего лишь перестановка элементов множества. Ведь, если, например, мы скажем, что A = {a1, a2, a3} и определим отношение порядка a2 -> a1 -> a3, то у нас индексы не будут в порядке возрастания, а будут в какой-то другой последовательности (i1 = 2, i2 = 1, i3 = 3). То есть буква i вводится, чтобы показать, что перестановка элементов может быть какой угодно в отношении, всё зависит от ситуации. Надеюсь, это понятно. ДОКАЗАТЕЛЬСТВО. Доказательство проводится с помощью метода математической индукции. Но чтобы проводить доказательство, нам нужно понять, по какой переменной будет индукция. В данном случае индукция по количеству элементов множества А (обозначим количество за n). 1) База индукции: n = 1. Такая диаграмма будет состоять из одного элемента, и эта диаграмма будет удовлетворять условию. 2) Индуктивное предположение: пусть утверждение верно для n ≤ k и диаграмма для k элементов имеет вид ai1 -> ai2 -> … -> aik 3) Индуктивный переход: докажем, что для n = k + 1 теорема будет верна. Мы предполагаем, что n > 1, так как случай n = 1 мы рассмотрели в базе индукции. Поэтому в нашей диаграмме обязательно будет элемент a1. Рассмотрим этот элемент. Здесь нужно ввести два множества: первое – множество элементов, левее a1, второе – множество элементов, правее a1. L = {x | 𝑥𝜌𝑎1 & 𝑥 ≠ 𝑎1} R = {x | 𝑎1𝜌𝑥 & 𝑎1 ≠ 𝑥} Даже на диаграмме ai1 -> ai2 -> … -> aik видно, что те элементы, которые левее какого-то фиксированного, в записи отношения (𝑥𝜌𝑎1) стоят первее, и аналогично с элементами, которые стоят правее фиксированного. Эти два множества являются попарно непересекающимися, то есть в них не найдётся никакого общего элемента. На множествах L и R определён линейный порядок (доказывается несложно, просто по определению), и значит, их можно представить в виде диаграмм: L = ai1 -> … -> ais (s вводится из-за того, что мы не знаем положение элемента a1 в диаграмме) R = ais+1 -> … -> aik В сумме в двух множествах L и R k элементов, а с элементом a1 будет k+1. Поскольку элемент a1 находится между этими множествами на диаграмме, то итоговая диаграмма ai1 -> … -> ais -> a1 -> ais+1 -> … -> aik состоит из k+1 элементов. А это нам и требовалось доказать. ЗАМЕЧАНИЕ. Если 𝜌 ⊆ A × 𝐴 – отношение линейного порядка на множестве A, то 𝜌 -1 – также отношение линейного порядка. Для таких отношений максимальные и минимальные элементы меняются местами. Это можно понять, например, из определения обратного отношения. 9-11. РАЗМЕЩЕНИЯ И СОЧЕТАНИЯ Пусть дано множество A = {a1, a2, …, an} и мы хотим выбрать несколько элементов из этого множества (например, m элементов). m-размещением n-элементного множества называется всякая последовательность, выставленная в линию, из m элементов этого множества. m-сочетанием n-элементного множества называется всякая совокупность из m элементов этого множества. В чём отличие последовательности от совокупности? Если мы выбрали 3 элемента из {b1, b2, b3, b4} то последовательностью будет являться каждая перестановка этих элементов (одна перестановка – одна последовательность – одно размещение). Например, (b1, b2, b3) и (b2, b1, b3) являются двумя разными последовательностями, а значит, двумя различными размещениями. Последовательности обозначаются круглыми скобками, совокупности – фигурными. В совокупности элементов порядок их следования роли не играет, а играет роль только то, какие элементы мы берём. Например, {b1, b2, b3} и {b2, b1, b3} – одна и та же совокупность (а значит, одно и то же сочетание). А {b1, b2, b3} и {b1, b2, b4} – две разные совокупности (а значит, два разных сочетания). Теперь поговорим про вывод формул размещений и сочетаний с повторениями и без повторений. 1) Размещения без повторений An m Пусть дано множество {a1, a2, …, an} и мы хотим выбрать из него m элементов. Тогда первый элемент можно выбрать n способами, второй – (n-1) способами, … последний (m-тый) элемент можно выбрать (n – (m - 1)) = (n – m + 1) способами. Первый элемент, можно сказать, выбирается (n – 0) способами, второй (n – 1) способами и тд. Я подчеркнул и выделил курсивом, чтобы показать закономерность между номером элемента и способом его выбора, а именно номер будет на единицу больше числа, которое стоит после знака «минус». Именно поэтому m-тый элемент по закономерности будет выбираться (n – (m – 1)) способами, а не, например, n – m. В итоге по правилу умножения получаем количество размещений из n элементов по m без повторений: An m = n(n-1)…(n-m+1) Домножим и разделим это выражение на одно и то же число (n-m)! An m = (n(n-1)…(n-m+1)(n-m)(n-m-1)…1)/(n-m)! = n!/(n-m)! 2) Размещения с повторениями Здесь всё гораздо проще, каждый элемент выбирается n разными способами, причём, если мы хотим выбрать всего m элементов, то количество размещений из n элементов по m с повторениями равно n^m. 3) Сочетания без повторений Cn m Для того, чтобы найти количество сочетаний без повторений, просто достаточно вспомнить, как ищутся размещения без повторений, и отличие между сочетанием и размещением (между совокупностью и последовательностью). Существует всего An m = n!/(n-m)! m-размещений без повторений n-элементного множества. Если задано какое-то сочетание без повторений {b1, b2, …, bm}, то из элементов этого сочетания можно составить m! различных размещений без повторений (так как первый элемент выбирается m способами, второй (m-1) способами, …, последний (m-тый) элемент выбирается 1 способом). Таким образом, получаем следующее равенство: Cn m × m! = An m, так как количество размещений явно будет больше за счёт перестановок элементов в m! раз количества сочетаний. Отсюда Cn m = An m/m! = n!/((n-m)!m!) 4) Сочетания с повторениями Самое сложное, но понять можно. Идея поиска количества сочетаний с повторениями состоит в том, чтобы не искать напрямую это количество, а попробовать придумать альтернативный способ, как это можно сделать, чтобы облегчить себе жизнь. Самый простой способ – попробовать представить произвольное сочетание с повторениями в виде чего-нибудь. Попробуем рассмотреть, например, множество {a1, a2, a3, a4, a5}. Пусть мы хотим выбрать 6 элементов (с повторениями) из этого множества. Количество таких сочетаний равно C5 6 (с чертой вверху). Рассмотрим теперь произвольное такое сочетание. Пусть мы выбрали элементы в такой совокупности: {a1, a1, a2, a2, a2, a4}. То есть первый элемент выбрали двумя способами, второй – тремя, третий – нуль (это будет важно потом), четвёртый – одним, пятый – нуль. Всего элементов у нас m = 6 штук. Оказывается, что удобно представить сочетание с повторениями в виде двоичной последовательности длиной m+n-1. Попробуем сначала просто написать нули, их будет ровно столько, сколько мы берём элементов с повторениями (в данном случае m = 6 нулей): 000000. А теперь разделим нашу группу из m = 6 нулей единицами на n = 5 частей. Всего нам для этого понадобится n-1 = 4 единицы. Каждая такая расстановка единиц будет помогать нам составлять какое-то сочетание с повторениями из n = 5 элементов по m = 6 элементов. Если говорить о примере выше, то расстановка единиц будет такой: 0010001101. Мы получили 5 групп нулей (две из них пустые, и это означает, что в данное сочетание с повторениями эти элементы не входят). Первая группа будет отвечать за то, сколько раз первый элемент входит в данное сочетание с повторениями (a1 входит 2 раза), вторая группа - сколько раз второй элемент входит в данное сочетание с повторениями (a2 входит 3 раза), третья группа - сколько раз третий элемент входит в данное сочетание с повторениями (a3 входит 0 раз, ну то есть не входит), четвёртая группа - сколько раз четвёртый элемент входит в данное сочетание с повторениями (a4 входит 1 раз), пятая группа - сколько раз пятый элемент входит в данное сочетание с повторениями (a5 не входит). Это мы рассмотрели одно из сочетаний из n элементов по m с повторениями, а нам нужно найти все такие сочетания. Для этого нужно просто найти количество перестановок n-1 единицы в последовательности длиной m+n-1. А количество способов сделать это Cm+n-1 n-1 . Преобразуем: Cm+n-1 n-1 = (m+n−1)! (n−1)!(m+n−1−(n−1))! = (m+n−1)! (𝑛−1)!𝑚! = (𝑚+𝑛−1)! (𝑚+𝑛−1−𝑚)!𝑚! (В последнем действии добавил и отнял m). Но, если расписать Cm+n-1 m, то получится то же самое, и именно это количество сочетаний принято за формулу количества сочетаний из n элементов по m с повторениями. Всё бы ничего, но для того, чтобы найти это количество, нам ещё перед эти надо доказать, что между количеством сочетаний с повторениями и количеством различных двоичных последовательностей существует взаимно однозначное (биективное) соответствие. То есть нужно ещё доказать, что биективное соответствие здесь действительно присутствует. С сюръективностью здесь просто: каждая двоичная последовательность разбивается на определённое количество групп нулей, обозначающих количество вхождений элементов в сочетание с повторениями. То есть каждой последовательности достанется какое-то сочетание с повторениями. Теперь про инъективность. Нужно показать, что два разных сочетания с повторениями соответствуют разным двоичным последовательностям. А это так и есть, поскольку разные сочетания с повторениями предполагают, что хотя бы 1 элемент множества встречается в сочетаниях разное количество раз. И, следовательно, два разных сочетания с повторениями не будут соответствовать одной и той же двоичной последовательности. Сюръективность и инъективность выполняются, поэтому соответствие биективно. Если не помните тему про инъективность и сюръективность - перечитайте тему «Отображения. Обратные отображения» Вроде кажется очевидным, но такое доказывать нужно. |