Рассмотрены комбинаторные вычисления, их основные операционные объекты: сочетания, перестановки, размещения и разбиения элементов конечных множеств и натуральных чисел. <...> Под разбиением множества понимается разделение его элементов на непересекающиеся подмножества, а разбиение целых чисел означает представление их в форме арифметической суммы слагаемых. <...> Во всех случаях физическая природа, технические свойства или информационный смысл элементов, которые образуют такие комбинаторные объекты, не имеет существенного значения, важна только их комбинаторная конфигурация, отражающая условия комбинаторной задачи. <...> В большинстве случаев используются факториальные функции, биномиальные коэффициенты, числа Стирлинга и Белла. <...> Необходимо отметить, что некоторые комбинаторные конструкции, образованные из комбинаторных чисел, например, числовые треугольники Паскаля и Стирлинга, имеют самостоятельное значение. <...> Следует отметить, что кроме размерности существуют и другие препятствия для организации перечислений комбинаторных объектов аналитическими методами: для реализации аналитического перечисления перестановок и размещений нужно построить некоммутативную алгебру производящих функций. <...> Особенно часто используется и наиболее естественно выглядит лексиграфический порядок, где символические записи комбинаторных объектов перечисляются как в словаре. <...> В частности, комбинаторные объекты могут быть сопоставлены последовательным целым числам и получены по их представлению в различных системах счисления. <...> В общем случае для обозначения числа сочетаний из n различных элементов по m элементов применяется следующая функциональная, индексная или векторная (Аппеля) символика: Cn m C m ⎛⎞ (, ) ~ ~ . m n ⎜⎟ ⎝⎠ n Независимо от формы обозначения, число сочетаний из n элементов по m элементов можно определить по следующим мультипликативной и факториальной формулам: 6 Cn m C mmm m n ⎝⎠ (, )==⎛⎞ −− +1) (1)…( ⎜⎟ −− n <...>
Методы_комбинаторных_вычислений.pdf
УДК 519.1
ББК 22.17
В44
Рецензенты: Н.В. Чичварин, Н.В. Филиппов
В44
Волосатова Т.М.
Методы комбинаторных вычислений : учеб. пособие /
Т.М. Волосатова, С.В. Родионов. — М.: Изд-во МГТУ им.
Н.Э. Баумана, 2011. — 103, [1] с. : ил.
Рассмотрены комбинаторные вычисления, их основные операционные
объекты: сочетания, перестановки, размещения и разбиения
элементов конечных множеств и натуральных чисел.
Рекомендовано для изучения в рамках курса «Лингвистическое и
программное обеспечение САПР» для студентов 2–5-го курсов.
УДК 519.1
ББК 22.17
Учебное издание
Волосатова Тамара Михайловна
Родионов Сергей Владимирович
МЕТОДЫ КОМБИНАТОРНЫХ ВЫЧИСЛЕНИЙ
Редактор К.А. Осипова
Корректор М.А. Василевская
Компьютерная верстка С.А. Серебряковой
Подписано в печать 26.08.2011. Формат 60×84/16.
Усл. печ. л. 6,05. Тираж 100 экз. Изд. № 134. Заказ .
Издательство МГТУ им. Н.Э. Баумана.
Типография МГТУ им. Н.Э. Баумана.
105005, Москва, 2-я Бауманская ул., 5.
© МГТУ им. Н.Э. Баумана, 2011
2
Стр.2
ОГЛАВЛЕНИЕ
Введение.......................................................................................................3
Сочетания элементов конечного множества ...............................................6
Число сочетаний.......................................................................................6
Тождества сочетаний ...............................................................................8
Бином Ньютона ......................................................................................11
Треугольник Паскаля .............................................................................15
Перечисление сочетаний натуральных чисел........................................23
Сочетания с повторениями элементов...................................................28
Перечисление бинарных сочетаний.......................................................31
Перечисление подмножеств конечного множества...............................37
Перестановки различных элементов .........................................................44
Определение перестановки....................................................................44
Лексиграфический порядок перестановок.............................................46
Инверсии перестановок..........................................................................50
Циклический сдвиг перестановки и подстановки .................................54
Транспозиции смежных элементов........................................................60
Цикловые классы подстановок и перестановок.....................................67
Разбиения и размещения элементов ..........................................................75
Разбиения конечного множества ...........................................................75
Разбиения целых чисел ..........................................................................85
Композиции целых чисел.......................................................................91
Размещения различных элементов.........................................................95
Размещения с повторением элементов ................................................100
Литература ..............................................................................................103
104
Стр.104