Дискретная математика 3

Дискретная

математика

С одержание

Введение3

Комбинаторика_ 3

§1. Правила суммы и прямого произведения.3

§2.Размещения с повторениями.4

§3. Размещения без повторений.4

§4. Перестановки.5

§5. Сочетания.5

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

§7. Перестановки с повторениями. Мультимножества.7

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

Методы подсчета и оценивания.8

§1. Производящие функции.8

§2. Линейные операции.8

§3. Сдвиг начала вправо.9

§4. Сдвиг начала влево.9

§5. Частичные суммы.9

§6. Дополнительные частичные суммы.9

§7. Изменение масштаба10

§8. Свертка.10

§9. Линейные рекуррентные соотношения.11

§10. Неоднородные линейные рекуррентные соотношения.12

§11. Числа Фибоначчи.15

Введение в теорию графов17

§1. Основные понятия теории графов.17

§2. Ориентированные и неориентированные графы.18

§3. Изоморфизм графов. Подграф. Связные графы.20

§4. Способы представления графов.24

§5. Число ребер простого графа. Разрезы.26

§6. Эйлеровы графы.27

§7. Гамильтоновы графы.29

§8. Деревья.29

§9. Двудольные графы.31

§10. Укладка графов.33

§11. Планарные и плоские графы. Теорема Эйлера о плоских графах.33

§12. Раскрашивание графов.35

Литература_ 36

Введение

Слово «дискретный» происходит от латинского discretus, что означает разделенность, прерывистость и противопоставляется непрерывности. Например, дискретное изменение какой-либо величины во времени – это изменение, происходящее через определенные промежутки времени (скачками); система целых чисел (в противоположность системе действительных чисел) является дискретной.

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

Комбинаторика

Простейшие понятия комбинаторики появились еще в доньютоновский период (П.Ферма, Б.Паскаль, Франция XVIII в.). Комбинаторика возникла как основа дискретной теории вероятностей в связи с исследованиями в области азартных игр.

Напомним некоторые важные обозначения. Множества будем обозначать заглавными буквами, а элементы множеств – малыми буквами.

а∈А – элемент а принадлежит множеству А.

{a, b, x, y} – в фигурных скобках изображаются множества заданные перечислением элементов.

|A| - мощность множества, количество множества.

А´В={(a,b) | a∈A, b∈B} – прямое произведение множеств.

АÈВ={x| x∈A или x∈B} – объединение множеств.

АÇВ={x| x∈A и x∈B} – пересечение множеств.

АВ={x| x∈A и xÏB} – разность множеств.

Æ – пустое множество.

U – универсальное множество.

=UА={x| xÏA} – дополнение множества.

§1. Правила суммы и прямого произведения.

Правило суммы . Пусть А и В конечные множества такие что АÇВ=Æ, |A|=m, |B|=n. Тогда |AÈB|=m+n.

В общем случае: Пусть X₁ , X₂ , …, X_n – попарно не пересекающиеся множества, X_i ÇX_j =Æ, где i¹j. Тогда выполняется равенство: .

Правило прямого произведения. Пусть А, В – конечные множества, |A|=m, |B|=n. Тогда |A´B|=m∙n.

В общем случае: Пусть X₁ , X₂ , …, X_k – произвольные множества, |X_i |=n_i , i=. Тогда |X₁ , X₂ , …, X_k |=|{(x₁ , x₂ , …, x_k )| x_i ∈X_i , i=}|=n₁ ∙n₂ ∙…n_k .

Пример. Сколько четырехзначных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, если: а) ни одна из цифр не повторяется более одного раза; б) цифры могут повторяться; в) числа должны быть нечетными (цифры могут повторяться)?

Решение.

а) Первой цифрой числа может быть одна из пяти цифр: 1, 2, 3, 4, 5. Когда первая цифра выбрана, то вторая может быть выбрана пятью способами, третья цифра уже может быть выбрана четырьмя способами, четвертая – тремя способами. Согласно правилу умножения общее число способов равно: 5∙5∙4∙3=300.

б) Первая цифра – одна из {1, 2, 3, 4, 5}. Каждая из следующих цифр будет из множества {0, 1, 2, 3, 4, 5}. Итак, число искомых чисел: 5∙6∙6∙6=1080.

в) Первая цифра принадлежит {1, 2, 3, 4, 5}. Четвертая цифра принадлежит {1, 3, 5}. Вторая и третья цифра принадлежит {0, 1, 2, 3, 4, 5}. Всего чисел: 5∙6∙6∙3=540.

§2.Размещения с повторениями.

Имеются предметы n различных видов а₁ , а₂ , …, а_{n .} Из них составляют всевозможные расстановки длины k. ( Н

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать