Чему равняется количество подмножеств мощности k множества мощности n ?

ЗАДАЧИ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ.

Часть первая, 2012 – 2013 уч.год

1. Расставить следующие числа в порядке возрастания методом фон-Неймана:

2. Члены последовательности {a_n} связаны рекуррентным соотношением:

a_n+1 =a_n + 2n, a₀ = 3. Найти a₁₀₀.

3. . Члены последовательности {a_n} связаны рекуррентным соотношением:

a_n+2 = 3a_n - 2 a_n+1 ; a₀ = -1, a₂.= 2 Найти a₆ . Найти a₁₁

4.Найти пошагово пересечение двух множеств методом слияния :

(3,5,12,15,16,20) ; (2,3,4,6,8,9,10,11,12,13,18).

5. Члены последовательности {a_n} связаны рекуррентным соотношением:

a_n+1 =a_n + n²; a₀ = 0. Найти a₅ . Найти a₁₅₀.

6. В окружности проводят последовательно хорды так, что каждая последующая пересекает все предыдущие. На сколько подобластей разбивают круг 6 таких хорд? 38 хорд?

8. В колоде 36 карт. Берут наугад три карты. Найти количество способов, при котором ровно две из них будут пиковой масти и ровно две – дамы.

9. Имеется три красных карточки, четыре белых и две желтых. Берут наугад три карточки из имеющихся девяти. Сколько имеется способов вытаскиваний, при которых ровно две из вытащенных трех карточек имеют одинаковый цвет?

10. Члены последовательности {a_n} связаны рекуррентным соотношением:

a_n+2 = a_n+1 + 2 a_n ; a₀ = 1, a₁.= 1 Найти a₆ . Найти a₃₁

12. Произвести пошагово слияние двух списков с сохранением возрастания:

(3,5,12,15,16,20) ; (2,6,8,9,18).

13. Найти все разбиения числа 10 на три слагаемые и количество таких разбиений.

Найти также количество разбиений числа 10 на такие слагаемые, что наибольшее равно 3. Ответ обосновать.

14. Найти все разбиения числа 10 на четыре слагаемые и количество таких разбиений.

Найти также количество разбиений числа 10 на такие слагаемые, что наибольшее равно 4. Ответ обосновать.3

15. Найти количество разбиений числа 12 на нечетные слагаемые и количество разбиений 12 на попарно различные слагаемые. Сравнить эти количества; ответ обосновать.

16. Расставить следующие числа в порядке возрастания методом Хоара (двоичная сортировка):

17. В трех ячейках располагают 5 шаров так, что в каждой ячейке может быть помещено любое количество шаров. Сколько имеется различных способов заполнения ?

18. Расставить следующие числа в порядке возрастания путем введения массива-множества:

20. Расставить следующие числа в порядке возрастания методом Флойда (хип):

21. Отношение А задано матрицей: . Найти обратное отношение, ядро данного отношения, ядро отношения, обратного к А, а т……акже транзитивные замыкания найденных ядер.

22. В четырех ячейках располагают 3 шара так, что в каждой ячейке может быть помещено любое количество шаров. Сколько имеется различных способов заполнения ?

БОНУСЫ

Оформляются в виде решения задач, подаваемых на конкурс студенческих работ. Должны содержать:

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

- Введение – краткий обзор круга решаемых задач.

- аналитический обзор – описание имеющихся алгоритмов (Интернет, библиотека).

После этого - точная постановка задачи, решение которой предлагается в работе.

- Подробное описание алгоритма.

- Результаты тестовых расчетов. Оформление с использованием визуальных средств (формы).

- Заключение; возможные перспективы развития и использования.

- Электронная версия работы.

1. Троичное слияние списков.
2. Алгоритмическая реализация метода Дж.фон-Неймана
3. Выявление связных компонент неориентированного графа.
4. Нахождение разбиений заданного числа.
5. Нахождение разбиений числа на заданное количество слагаемых
6. Нахождение разбиений числа, при котором наибольшее слагаемое равно заданному числу.
7. Прямое решение рекуррентных уравнений.

арадокс Рассела — открытый в 1901 году^[1] Бертраном Расселом и позднее независимо переоткрытый Э. Цермело теоретико-множественный парадокс, демонстрирующий противоречивость логической системы Фреге, являвшейся ранней попыткой формализации наивной теории множеств Г. Кантора.

Парадокс Рассела формулируется следующим образом:

Пусть — множество всех множеств, которые не содержат себя в качестве своего элемента. Содержит ли само себя в качестве элемента? Если да, то, по определению , оно не должно быть элементом — противоречие. Если нет — то, по определению , оно должно быть элементом — вновь противоречие.

Противоречие в парадоксе Рассела возникает из-за использования в рассуждении внутренне противоречивого^[2] понятия множества всех множеств и представления о возможности неограниченного применения законов классической логики при работе с множествами. Для преодоления этого парадокса было предложено несколько путей. Наиболее известный состоит в предъявлении для теории множеств непротиворечивой формализации , по отношению к которой являлись бы допустимыми все «действительно нужные» (в некотором смысле) способы оперирования с множествами. В рамках такой формализации утверждение о существовании множества всех множеств было бы невыводимым.

Действительно, допустим, что множество всех множеств существует. Тогда, согласно аксиоме выделения, должно существовать и множество , элементами которого являются те и только те множества, которые не содержат себя в качестве элемента. Однако предположение о существовании множества приводит к парадоксу Рассела. Следовательно, ввиду непротиворечивости теории , утверждение о существовании множества невыводимо в этой теории, что и требовалось доказать.

В ходе реализации описанной программы «спасения» теории множеств было предложено несколько возможных её аксиоматизаций (теория Цермело — Френкеля ZF, теория Неймана — Бернайса — Гёделя NBG и т. д.), однако ни для одной из этих теорий до настоящего момента не найдено доказательства непротиворечивости. Более того, как показал Гёдель, разработав ряд теорем о неполноте, такого доказательства не может существовать (в некотором смысле).

универсум

Универсальное множество (универсум) — множество, содержащее все мыслимые объекты. В связи с парадоксом Рассела данное понятие трактуется в настоящее время как «множество, включающее все множества, участвующие в рассматриваемой задаче».

Реализация операции пересечения упорядоченных множеств Z = X Y. По определению операции в множество Z следует записывать элемент xi или yj при выполнении условия xi = yj. Можно ли при сопоставле- нии элементов множеств X и ограничится проверкой условия xi = yj и перехо- дить к сравнению следующей пары? Нет, этого достаточно только, если Х = Y, при этом получение Z потребует n операций сравнения, где n = |X| = |Y|. Таким образом, Nср.л.= n – это минимальное количество операций сравнения, т.е. оценка в лучшем. Давайте рассмотрим пример. Пусть X = 1, 3, 6 и Y = 2, 4, 5 . Выполнив сравнение xi = yj для первых элементов этих масси- вов, мы определили, что они не равны, следовательно никакой элемент из этой пары пока нельзя заносить в множество Z. Однако мы можем исключить из дальнейшего рассмотрения тот элемент, который имеет меньшее значение (большее, если бы множества были упорядочены по убыванию). Следова- тельно, кроме операции сравнения xi = yj необходимо проверять условие xi yj. Таким образом, при каждом сравнении элементов нам в худшем слу- чае придется проверять результаты двух операций xi = yj и xi yj.

Схема алгоритма, основанного на изложенных соображениях, представ- лена на рис. 4.

i : = 1 i n j m Нет Да Конец xi yj i : = i + 1 Да Нет k : =0 j : = j + 1 Да j : = 1 i : = i + 1 zk : = xi Начало k : = k + 1 j : = j + 1 xi yj Нет

Рис. 4. Схема алгоритма выполнения операции пересечения упорядоченных множеств

Ясно, что количество операций сравнения элементов будет максималь- ным, если множества X и Y не пересекаются (для общих элементов пересека- ющихся множеств проверка xi yj не будет выполняться и два элемента – xi и yj будут исключены из рассмотрения). Учитывая, что Х и Y упорядоченные множества, максимальное количество операций сравнения будет, например при n m, если выполняется условие (1). Нетрудно видеть, что максимальное количество операций сравнения (оценка в худшем) будет определяться по формуле

Реализация операции объединения упорядоченных множеств Z = X Y. В соответствии с определением операции в ходе сравнения эле- ментов множеств Х и Y нам надо записывать в множество Z различные эле- менты из того и другого множеств, а если элементы совпадают, то записы- вать один из них. Однако при сопоставлении двух элементов упорядоченных множеств установление факта, что xi yj, является необходимым, но не до- статочным основанием для занесения xi X или yj Y в множество Z. При упорядочивании по возрастанию элемент xi следует заносить в множество Z, если xi yj, а элемент yj – при yj xi(или xi при xi yj, а yj – при yj xi). Сле- довательно, кроме отношения равенства нам необходимо проверять и отно- шение «меньше».

При выполнении условия xi yj следует переходить к сравнению xi с yj+1. Однако, если для некоторого xi справедливо xi ym, это означает, что все эле- менты xi+1, xi+1,…, xn ym. Для обнаружения этой ситуации и выполнения со- ответствующих операций после выхода из цикла сравнения элементов мно- жеств X и Y необходимо проверять условие i n. При выполнении данного условия в множество Z следует записать все оставшиеся элементы множества X, начиная с xi. Аналогично возможна ситуация, когда yj > xn. Следовательно, необходимо также проверять условие j m и при его выполнении в множе- ство Z записывать оставшиеся элементы множества Y, начиная с yj. На рис. 3 показан алгоритм выполнения операции объединения упорядоченных мно- жеств X и Y.

Алгоритм сортировки

Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.
Дан массив^[1] A из n элементов^[2]:

,

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

1. закон трихотомии: для любых либо , либо , либо ;

2. транзитивность: для любых если и , то .

Задачей сортировки по неубыванию является нахождение перестановки элементов с индексами от , при которой ключи располагаются в порядке неубывания:

^[3]

В результате работы алгоритма и применения перестановки получается отсортированный массив:

Аналогично можно определить сортировку по невозрастанию.

Понятие бинарного отношения

Пусть дано декартово произведение двух непустых множеств А и

В, при этом множества могут быть любыми: пересекающимися, равны-

ми, входящими одно в другое и т.д. Элементами множества А×В явля-

ются упорядоченные пары (ai

, bj), где ai∈A; bj∈B; i=1, 2,…, |А|; j=1, 2,

3,…, |B|. Всякое подмножество декартова произведения А×В называется

бинарным отношением, определенным на паре множеств А и В (по ла-

тыни «бис» обозначает «дважды»).

Для обозначения бинарного отношения применяют знак R. По-

скольку R – это подмножество множества А×B, то можно записать

R⊆А×В . Если же требуется указать, что (а, b)∈R, т. е. между элемента-

ми а∈А и b∈B существует отношение R, то пишут aRb. Пусть, например

A = {1, 2, 3}, B = {1, 2, 3, 4, 5, 6}. (1)

Множество A×B содержит 18 упорядоченных пар. Выделим на

этом множестве отношение «больше»: а>b, где а∈А и b∈B. Тогда

R={(2, 1), (3, 1), (3, 2)},

т.е. из 18 пар множества А×B три упорядоченные пары принадлежат

отношению aRb, где R обозначает слово «больше». Если вместо букв

подставить их значения, то получим верные утверждения:

2>1; 3>1; 3>2.

Очевидно, что в этом случае справедливо равенство:

aRb={(2, 1), (3, 1), (3, 2)}.

Рассмотрим еще один пример. Пусть R обозначает «меньше про-

стого числа» на множествах (1). Тогда

aRb={(1, 2), (1, 3), (1, 5), (2, 3), (2, 5), (3, 5)}.

Если вместо всех трех букв a, R, b подставить их значения, то по-

лучим шесть верных утверждений:

1 меньше простого числа 2;

1 меньше простого числа 3, и т. д.

При подстановке других значений а и b (но при том же R) будем

получать ложные утверждения.

Среди подмножеств множества A×B имеется 2

|A×B|

-2 собственных

подмножеств и два несобственных: одно из них пусто, а второе совпа-

дает с самим множеством А×B. Формально оба эти несобственные под-

множества также представляют собой некоторые отношения между

элементами множеств А и B.

Пусть, например, 10

А={1, 2, 3, 4}; В={а, b, с, е, f }.

Выделим в множестве А×В отношение Т: «четное число, гласная

буква»:

Т = {(2, а), (4, а), (2, е), (4, е)}. (2)

Объединим множества А и В: М=А∪В. Очевидно, что в множест-

ве М

отношение Т будет иметь такой же вид, что и (3.2).

Мы в дальнейшем будем пользоваться понятием бинарного отно-

шения, определенным как через квадрат одного и того же множества,

так и через декартово произведение двух различных множеств.

Данный раздел темы назван «Бинарные отношения», однако при

необходимости будем рассматривать и n-арные отношения, как под-

множества множества А

n

.

Задавать бинарные отношения можно разными способами. Один

из них мы уже рассмотрели. Это использование правила, согласно кото-

рому указываются все элементы, входящие в данное отношение. Вместо

правила можно привести список элементов заданного отношения путем

непосредственного их посимвольного перечисления. Существуют еще

три способа задания отношений – табличный, в виде графов и с помо-

щью сечений. Наиболее употребительным является табличный способ.

Его основу составляет прямоугольная система координат, где по одной

оси откладываются элементы одного множества, по второй – другого.

Пересечения координат образуют точки, обозначающие элементы де-

картова произведения

Бинарные отношения задаются двухмерными системами коорди-

нат. Очевидно, что все элементы декартова произведения трёх мно-

жеств могут быть представлены в трехмерной системе координат, че-

тырех множеств – в четырехмерной системе и т.д.

Второй способ представления отношений – в виде графов – при-

меняется так же часто, как и первый (табличный). Однако для его изло-

жения необходимо привлечение таких понятий, как орграф, дуга, дву-

дольный граф и некоторые другие, в связи с чем с этим способом мы

познакомимся позже.

Способ задания отношений с помощью сечений используется ре-

же, поэтому рассматривать его не будем. При необходимости каждый

желающий может ознакомиться с ним, обратившись к специальной ли-

тературе.

Отношения строгого порядка

Отношения нестрогого порядка

Упорядоченные множества

Отношения соответствия

Функциональные отношения. Отображения.

Функциональные отношения. Отображения

Пусть даны множества X и Y. Бинарное отношение xRy является

функциональным (функцией), если каждому элементу х∈X соответст-

вует не более одного элемента у∈Y. Из этого определения следует, что

одно-многозначные и много-многозначные отношения функциональ-

ными быть не могут.

Для обозначения функции используются различные записи:

X Y f→ , f:X→Y; f(x); (х, у)∈F, y=F(x), где F⊂X×Y . Значение функции

у∈Y называют образом элемента x∈X, а сам элемент х∈X – прообразом.

Множество X – это область определения функции, Y – область значе-

ний.

Функция у=F(x) является всюду определенной, если каждому

элементу х∈Х соответствует один элемент у∈Y. В этом случае функцию

называют также отображением (или инъекцией) множества X в множе-

ство Y . Функция является недоопределенной (частично определенной),

если имеется хотя бы один элемент х∈X, которому не соответствует ни-

какой элемент у∈Y. Отсюда следует, что недоопределенные функции

отображениями не являются.

Чему равняется количество подмножеств мощности k множества мощности n ?

Если конечное множество состоит из элементов, то оно имеет ровно подмножеств.

Этот факт хорошо известен. А вот как его доказывать? Существует довольно много различных доказательств. Предлагаю всем желающим в этой теме рассказать про те доказательства, которые им известны. Среди них попадаются довольно забавные. И наверняка я сам знаю далеко не все варианты, бует интересно посмотреть на новые.

P. S. Кстати, неравенство , верное для всех натуральных чисел, можно помимо индукции и исследования поведения дифференцируемой функции доказать ссылкой на теорему Кантора. Теорема Кантора гласит, что для любого множества множество всех его подмножеств имеет мощность строго большую, чем мощность . Подставляя вместо конечное множество из элементов, получаем требуемое неравенство.
Ограничимся случаем Пусть где при Каждое подмножество однозначно определяется упорядоченным набором ответов "да" или "нет" на вопросы причем всякий такой набор ответов определяет некоторое подмножество и разные наборы ответов определяют разные подмножества Следовательно, число подмножеств множества совпадает с числом упорядоченных наборов ответов на вопросов. Осталось заметить, что последнее равно