КОМБИНАТОРНЫЕ ОБЪЕКТЫ Комбинаторика – раздел математики, изучающий конфигурации конечных множеств. <...> С учетом этого словосочетание «комбинаторный объект»будем использовать в качестве синонима термина «конфигурация». <...> Число размещений с повторениями из n по m будем обозначать ˜ размещений является m-й декартовой степенью множества M и, 3 n . <...> Последнее условие означает, что все компоненты соответствующего набора должны быть различны. <...> Очевидно, что размещение без повторений существует лишь в случае m n;при m = n кортеж (1.3) будем называть n. <...> Можно показать, что число размещений без повторений из n по m дается формулой Am n = n(n−1) · . · (n−m+1), из которой следует, что число перестановок длины n Pn = An n = n(n−1) · . <...> Поскольку множество M состоит из n элементов, каждую из m компонент кортежа (1.3) можно заполнить одним из n способов, следовательно, число способов составить кортежи (1.2) n · . · n m раз = nm. <...> Таким образом, число размещений без повторений составит n(n−1) · . · (n−m+1). <...> Таким образом, число возможных способов сформировать группу двоечников C5 20 = 20! <...> Найти число способов, которыми можно рассадить 11 человек на одну лавку. <...> По смыслу задачи указанный кортеж является размещением (порядок, в котором рассажены люди, имеет значение) без повторний (один человек не может сесть более чем на одно место) из 11 по 11. <...> Таким образом, число способов рассадить 11 человек на лавке P11 = 11! <...> В мешке Деда Мороза находится 20 различных подарков. <...> По содержанию задачи этот кортеж является размещением (порядок важен, так как он определяет, какому ребенку достанется тот или иной подарок) без повторений (все подарки различны) из 20 по 17. <...> Это означает, что при циклической перестановке элементов x1,.,x11 мы можем получить другое размещение, которое, однако, будет описывать тот же хоровод. <...> По смыслу задачи этот кортеж является перестановкой длины 10, и, следовательно, интересующее нас число способов <...>
Элементы_комбинаторики.pdf
УДК 519.1
ББК 22.141
Б43
Рецензент Р.С. Исмагилов
Б43
Белоусов А.И.
Элементы комбинаторики : метод. указания к выполнению
домашнего задания / А.И. Белоусов, П.А. Власов. –М.: Изд-во
МГТУ им. Н.Э. Баумана, 2012. – 53, [3] с. : ил.
Методические указания содержат краткий теоретический материал,
необходимый для выполнения домашнего задания по курсу «Дискретная
математика». Рассмотрены примеры решения задач, приведены
задачи для самостоятельной работы.
Для студентов 2-го курса, обучающихся по специальности ИУ-7.
Рекомендовано Учебно-методической комиссией НУК ФН МГТУ
им. Н.Э. Баумана.
УДК 519.1
ББК 22.141
Учебное издание
Белоусов Алексей Иванович
Власов Павел Александрович
ЭЛЕМЕНТЫ КОМБИНАТОРИКИ
Методические указания
к выполнению домашнего задания
Редактор В.М. Царев
Корректор Н.А. Фетисова
Компьютерная верстка В.И. Товстоног
Подписано в печать 16.03.2011. Формат 60×84/16.
Усл. печ. л. 3,26. Тираж 300 экз. Изд. № 29.
Заказ
Издательство МГТУ им. Н.Э. Баумана.
Типография МГТУ им. Н.Э. Баумана.
105005, Москва, 2-я Бауманская ул., 5.
МГТУ им. Н.Э. Баумана, 2012
c
Стр.2
ОГЛАВЛЕНИЕ
1. КОМБИНАТОРНЫЕ ОБЪЕКТЫ ............................... 3
1.1. Основные понятия........................................ 3
1.2. Формула включений и исключений . . . . . .................. 10
1.3. Задачи для самостоятельного решения .................... 15
2. ЛИНЕЙНЫЕ РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ ............. 16
2.1. Основные понятия........................................ 16
2.2. Линейные однородные рекуррентные соотношения
с постоянными коэффициентами ......................... 21
2.3. Линейные неоднородные рекуррентные соотношения
с постоянными коэффициентами ......................... 23
2.4. Задачи для самостоятельного решения .................... 32
3. ЭЛЕМЕНТЫ ТЕОРИИ ПОЙА ................................. 33
3.1. Группа автоморфизмов неориентированного графа ........ 33
3.2. Цикловой индекс группы ................................. 38
3.3. Характерные задачи теории Пойа ......................... 39
3.4. Основная теорема ........................................ 41
3.5. Задачи для самостоятельного решения .................... 46
Приложение ..................................................... 47
Литература ...................................................... 55
Стр.56