П. Г. Демидова Кафедра дискретного анализа Дискретная математика Методические указания Рекомендовано Научно-методическим советом университета для студентов, обучающихся по специальности Прикладная информатика в экономике Ярославль 2011 УДК 004+621 ББК В 174я73 Д 48 Рекомендовано Редакционно-издательским советом университета в качестве учебного издания. <...> Предназначены для студентов, обучающихся по специальности 080801.65 Прикладная информатика в экономике (дисциплина «Дискретная математика», блок ЕН), очной формы обучения. <...> П. Г. Демидова, 2011 2 Значительное место в дискретной математике занимает комбинаторика, которая является древнейшей и, возможно, ключевой ветвью мат ематики. <...> Условно в комбинаторной теории можно выделить следующие три большие части (см. схему): Теорию конфигураций, включающую блок-схемы, подс тановок, теорию кодирования. г руппы Теорию перечисления, с одержащую производящие фу нкции, теоремы обращения и исчисление конечных разностей. <...> Например, перечислительная комбинаторика сящиеся и к конфигурациям, и к упорядоченным множествам. <...> 3 к рассматривает задачи, отно Теория конфигураций и теория перечисления Теория конфигураций – традиционный и наиболее разработанный раздел комбинаторики, она рассматривает задачи выбора и расположения элементов некоторого, обычно конечного, множества в соответствии с заданными правилами. <...> Перечислительная комбинаторика основным методом исследования провозгласила метод производящих функций, используя который было доказано громадное число комбинаторных тождеств. <...> Для подсчёта числа этих конфигураций используются правила суммы и произведения. <...> Правило суммы можно перефразировать на теоретико-множественном языке. <...> Правило произведения можно распространить на выбор последовательности (x1, x2, …, xn) произвольной конечной длины n. <...> На теоретико-множественном языке правило произведения формулируется так: | Aх B | = | A | | B |. <...> 4 Последовательность (x1, x2, …, xk <...>
Дискретная_математика_методические_указания.pdf
Министерство образования и науки Российской Федерации
Ярославский государственный университет им. П. Г. Демидова
Кафедра дискретного анализа
Дискретная математика
Методические указания
Рекомендовано
Научно-методическим советом университета для студентов,
обучающихся по специальности
Прикладная информатика в экономике
Ярославль 2011
Стр.1
УДК 004+621
ББК В 174я73
Д 48
Рекомендовано
Редакционно-издательским советом университета
в качестве учебного издания. План 2010/2011 учебного года
Рецензент
кафедра дискретного анализа
Ярославского государственного университета им. П. Г. Демидова
Д 48
Дискретная математика: методические указания
/ сост.: В. Б. Калинин, А. В. Николаев; Яросл. гос. ун-т
им. П. Г. Демидова. – Ярославль : ЯрГУ, 2011. – 48 с.
Настоящий практикум содержит набор задач по
комбинаторике и теории графов, различных по сложности.
К более трудным задачам даны указания. Это
позволит эффективно использовать различные формы
самостоятельной работы и поможет студентам хорошо
подготовиться к зачету.
Предназначены для студентов, обучающихся по специальности
080801.65 Прикладная информатика в экономике
(дисциплина «Дискретная математика», блок ЕН),
очной формы обучения.
УДК 004+621
ББК В 174я73
Ярославский государственный
университет им. П. Г. Демидова,
2011
2
Стр.2
Значительное место в дискретной математике занимает комбинаторика,
которая является древнейшей и, возможно, ключевой
ветвью мат ематики.
Всякому анализу
предшествует
комбинаторное
рассмотрение, всякая серьёзная теория имеет комбинаторный
аналог. Комбинаторика располагает столь многообразными
методами, решает столь разнообразные задачи, что трудно
чётко обозначить её границы. Условно в комбинаторной теории
можно выделить следующие три большие части (см. схему):
Теорию конфигураций, включающую блок-схемы,
подс тановок, теорию кодирования.
г руппы
Теорию перечисления, с одержащую производящие фу нкции,
теоремы обращения и исчисление конечных разностей.
Теорию порядка, включающую конечные у порядоч енные
множества и решётки, матрицы и теоремы существо вания,
подобные теоремам Холла и Рамсея.
Следует ещё раз подчеркнуть в высшей степени усл овный
характер представленной схемы. Повсеместно можно набл юдать
взаимную связь перечисленных разделов комбинаторики. Например,
перечислительная комбинаторика
сящиеся и к конфигурациям, и к упорядоченным множествам.
3
к рассматривает задачи, отно
Стр.3
Теория конфигураций
и теория перечисления
Теория конфигураций – традиционный и наиболее разработанный
раздел комбинаторики, она рассматривает задачи выбора
и расположения элементов некоторого, обычно конечного,
множества в соответствии с заданными правилами. Перечислительная
комбинаторика основным методом исследования провозгласила
метод производящих функций, используя который
было доказано громадное число комбинаторных тождеств.
Элементарными комбинаторными конфигурациями являются
сочетания, размещения, перестановки. Для подсчёта числа этих
конфигураций используются правила суммы и произведения.
Правило суммы. Если элемент A можно выбрать m
способами, а элемент B можно выбрать k способами, то выбор
элемента A или B можно осуществить m + k способами. Правило
суммы можно перефразировать на теоретико-множественном
языке. Обозначим через | A | число элементов множества A, через
A B – объединение множеств A и B, через AxB – декартово
произведение множеств A и B. Тогда для непересекающихся
множеств A и B выполняется равенство:
| A B | = | A | + | B |.
Обобщением правила суммы является правило произведения.
Правило произведения. Если элемент A можно выбрать m
способами, а после каждого выбора элемента A элемент B можно
выбрать k способами, тогда упорядоченную пару элементов (A,
B) можно выбрать m*k способами.
Правило произведения можно распространить на выбор
последовательности (x1, x2, …, xn) произвольной конечной длины
n. На теоретико-множественном языке правило произведения
формулируется так: | Aх B | = | A | | B |.
Размещения.
Назовём множество, содержащее n элементов, n-множеством.
4
Стр.4
Последовательность (x1, x2, …, xk ) длины k без повторяющихся
элементов из элементов данного n-множества назовём
k-размещением.
Обозначим символом
число размещений из n по k элементов
(от фран. «arrangement» – размещение). Используя правило
произведения, вычислим число
. Пусть произвольное
размещение длины k имеет вид:
(x1, x2, …, xk ).
Элемент x1 можно выбрать n способами. После каждого
выбора x1 элемент x2 можно выбрать (n – 1) способами. После
каждого выбора элементов x1 и x2 элемент x3 можно выбрать
(n – 2) способами и т. д. После каждого выбора элементов x1 , x2,
…, xk-1 элемент xk можно выбрать (n – (k – 1)) = (n – k + 1)
способами. Тогда, по правилу произведения, последовательность
(x1; x2; , …, xk ) можно выбрать числом способов, равным
n(n – 1)(n – 2) … (n – k + 1) =
(1.1)
Произведение в левой части равенства (1.1) умножим и
разделим на (n – k)!, получим:
.
Если в формуле (1.2) k = n, то
танием.
Обозначим через
ментов. Формулу для числа
число k-сочетаний из данных n элеполучим,
рассуждая следующим
образом. Если каждое сочетание упорядочить всеми возможными
5
(1.2)
есть число Pn перестановок
из n элементов Pn = n! (от «permutation» – перестановка).
Сочетания.
k-подмножество данного n-множества называется k-соче
Стр.5