Методы комбинаторных вычислений

Московский государственный технический университет  
имени Н.Э. Баумана 
Т.М. Волосатова, С.В. Родионов 
МЕТОДЫ  
КОМБИНАТОРНЫХ  
ВЫЧИСЛЕНИЙ 
Рекомендовано Научно-методическим советом  
МГТУ им. Н.Э. Баумана в качестве учебного пособия  
 
 
 
 
 
 
 
 
 
 
Москва 
Издательство МГТУ им. Н.Э. Баумана 
2011 

УДК 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 

 
ВВЕДЕНИЕ 
Разнообразные комбинаторные задачи, связанные с вычислительной обработкой дискретных конечных структур, часто встречаются в технической практике и других предметных областях. 
Кроме того, комбинаторные категории и методы традиционно актуальны в ряде математических дисциплин. В частности, они применяются в теории вероятностей, теории графов, теории кодирования, теории чисел и теории игр. Необходимо также упомянуть 
их наиболее современные приложения, например, в статистической физике, математической биологии и для криптографического 
анализа информации. 
Основными операционными объектами таких комбинаторных 
вычислений являются сочетания, перестановки, размещения и разбиения элементов конечных множеств и натуральных чисел. Сочетания образуются неупорядоченной выборкой элементов конечного множества. Перестановки получаются расположением всех 
элементов конечного множества в различной последовательности. 
Размещения можно рассматривать как упорядоченные выборки 
элементов конечного множества, где они переставлены в различном порядке. Под разбиением множества понимается разделение 
его элементов на непересекающиеся подмножества, а разбиение 
целых чисел означает представление их в форме арифметической 
суммы слагаемых. Во всех случаях физическая природа, технические свойства или информационный смысл элементов, которые 
образуют такие комбинаторные объекты, не имеет существенного 
значения, важна только их комбинаторная конфигурация, отражающая условия комбинаторной задачи. При этом, как правило, 
требуется подсчитать или перечислить все комбинаторные объекты определенного класса, которые можно получить для заданного 
конечного множества элементов. 
 
3 

Для подсчета указанных выше основных комбинаторных объектов применяются специальные формулы или рекуррентные соотношения, которые оперируют различными специальными комбинаторными числами и функциями. В большинстве случаев 
используются факториальные функции, биномиальные коэффициенты, числа Стирлинга и Белла. Необходимо отметить, что некоторые комбинаторные конструкции, образованные из комбинаторных чисел, например, числовые треугольники Паскаля и 
Стирлинга, имеют самостоятельное значение. Их свойства представляют большой интерес как для разнообразных развлекательных приложений, так и для решения серьезных математических 
задач, в частности в теории чисел и высшей алгебре. Тем не менее 
комбинаторные задачи, связанные с подсчетом стандартных комбинаторных объектов, как правило, не вызывают серьезных проблем при вычислении. 
Для инженерной практики более характерны задачи, связанные 
с генерацией и перечислением различных комбинаторных конфигураций. В перечислительных задачах малой размерности, когда 
количество элементов, образующих искомые комбинаторные конфигурации невелико, необходимый результат может быть получен 
аналитическим путем с использованием, например, формального 
аппарата производящих функций или символического исчисления. 
Следует отметить, что кроме размерности существуют и другие 
препятствия для организации перечислений комбинаторных объектов аналитическими методами: для реализации аналитического 
перечисления перестановок и размещений нужно построить некоммутативную алгебру производящих функций. Это возможно, 
но сложно и, в конечном счете, не дает преимуществ по сравнению 
с численными методами. Среди них, разумеется, могут быть использованы универсальные методы перебора конечных дискретных структур, в частности различные варианты организации поиска 
с 
возвращением. 
Однако 
гораздо 
более 
удобным 
и 
привлекательным выглядит применение специализированных итерационных или рекурсивных алгоритмов, которые были разработаны для генерации и перечисления основных типов комбинаторных конфигураций. 
Такие специализированные алгоритмы обеспечивают систематический характер перечисления, когда искомые комбинаторные 
 
4 

объекты порождаются в определенном порядке. Особенно часто 
используется и наиболее естественно выглядит лексиграфический 
порядок, где символические записи комбинаторных объектов перечисляются как в словаре. Однако наиболее эффективными являются перечислительные алгоритмы, которые реализуют порядок 
минимальных изменений, когда последовательные комбинаторные 
объекты должны быть минимально различимы по составу или взаимному расположению своих элементов. Кроме лексиграфических 
алгоритмов и алгоритмов минимального изменения существует 
большое число других перечислительных алгоритмов, которые 
реализуют разнообразные порядки порождение основных комбинаторных объектов. В частности, комбинаторные объекты могут 
быть сопоставлены последовательным целым числам и получены 
по их представлению в различных системах счисления. Разумеется, такие обращения не всегда эффективны и по возможности следует их не использовать. Однако порядки, образованные таким 
способом могут быть удобны, например, для получения комбинаторного объекта непосредственно по заданному порядковому номеру или для решения обратной задачи, когда требуется найти номер любого комбинаторного объекта в определенном порядке. Все 
эти алгоритмы в совокупности образуют алгоритмическую базу 
комбинаторного анализа и широко используются для организации 
комбинаторных вычислений в инженерной практике или научных 
исследованиях. 
 
5 

 
СОЧЕТАНИЯ ЭЛЕМЕНТОВ КОНЕЧНОГО МНОЖЕСТВА 
Число сочетаний 
Сочетанием называется неупорядоченная выборка элементов 
конечного множества с фиксированным числом и без повторений 
элементов. Различные сочетания должны отличаться хотя бы одним элементом, а порядок расположения элементов не имеет значения. Например, из множества гласных латинских букв {AEIOU} 
можно составить 10 различных сочетаний по 3 буквы, образуя 
следующие неупорядоченные тройки: 
 
AEI, AEO, AEU, AIO, AIU, AOU, EIO, EIU, EOU, IOU. 
Отметим, что из тех же пяти букв можно получить также 10 различных сочетаний, если комбинировать их по 2 буквы: 
 
AE, AI, AO, AU, EI, EO, EU, IO, IU, OU. 
Если комбинировать те же буквы по 4, то получится только 5 различных сочетаний: 
 
AEIO, AEIU, AIOU, EIOU, AEOU. 
В общем случае для обозначения числа сочетаний из n различных элементов по m элементов применяется следующая функциональная, индексная или векторная (Аппеля) символика: 
 
( ,
) ~
~
.
m
n
n
C n m
C
m
⎛
⎞
⎜
⎟
⎝
⎠
 
Независимо от формы обозначения, число сочетаний из n элементов по m элементов можно определить по следующим мультипликативной и факториальной формулам: 
 
6 

…
…
 
 
(
1)
(
1)
!
( ,
)
.
(
1)
1
!(
)!
m
n
n
n n
n
m
n
C n m
C
m
m m
m n
m
⎛
⎞
−
−
+
=
=
=
=
⎜
⎟
−
−
⎝
⎠
Несложно проверить, что результат вычислений по этим формулам совпадает с результатами рассмотренного ранее примера с сочетаниями гласных латинских букв. В частности, при n = 5 и m = 3 
вычисления по этим формулам дадут следующий результат: 
 
3
5
5
5 4 3
5!
(5, 3)
10.
3
3 2 1
3!(5
3)!
C
C
⎛⎞
⋅
⋅
=
=
=
=
=
⎜⎟
⋅
⋅
−
⎝⎠
 
В общем случае все формулы для числа сочетаний имеют комбинаторный смысл и справедливы при любых целочисленных значениях n и m, таких, что n > m > 0. Если m > n и m < 0, то число 
сочетаний равно 0, так как в этом случае основное множество из n 
элементов вообще не имеет подмножеств мощности m: 
 
0
0.
m n
m
n
n
C
C
>
<
=
=
 
Кроме того, полезно помнить следующие граничные числа сочетаний, которые легко проверить непосредственной подстановкой в 
мультипликативную и факториальную формулы: 
n
n
n
n
n
n n
C
C
C
C
n
C
+
=
=
=
=
=
 
 
0
0
1
2
0
(
1)
1;
;
.
2
Следует также отметить, что мультипликативная формула остается 
справедливой, даже когда n является отрицательным целым и действительным числом, но значение m по-прежнему должно быть 
целым. При этом для всех отрицательных целых значений n важнейшим считают случай, когда n равно (−1): 
 
1
( 1)( 2)
(
)
( 1) .
(
1)
1
m
m
m
C
m m
−
−
−
−
=
= −
−
…
…
 
Некоторые нецелые значения n также могут оказаться полезны. Например, при отрицательном дробном значении n, равном (−1/2), и 
любом натуральном значении m получаем следующее соотношение: 
 
1/2
2
( 1/ 2)( 3/ 2)
( 2
1)/ 2
( 1/ 4)
.
(
1)
1
m
m
m
m
m
C
C
m m
−
−
−
−
+
=
= −
−
…
…
 
 
7 

Похожее соотношение можно получить для случая положительного вещественного значения n равного (+1/2). Причем соотношения 
для случаев, когда n равно (−1/2) и (+1/2), при любом натуральном 
значении m оказываются связаны следующим образом: 
1/2
1/ 2
1
.
(1
2 )
 
m
m
C
C
m
+
−
=
=
−
 
Все рассмотренные соотношения для дробных и отрицательных значений n получаются из мультипликативной формулы и 
формально справедливы, но не имеют никакой комбинаторной интерпретации. Однако обычно в комбинаторной практике рассматриваются задачи, которые связаны с определением чисел сочетаний при натуральных значениях n > m > 0. 
Тождества сочетаний 
Практическое использование мультипликативной и факториальной формул для определения числа сочетаний при произвольных значениях n и m оказывается менее продуктивно из-за экспоненциального роста факториальных произведений их числителя и 
знаменателя. Даже при сравнительно небольших величинах n и m 
эти произведения часто превосходят возможности представления 
целых чисел в современных вычислительных и программных системах. При этом их величины оказываются значительно больше 
результирующего значения числа сочетаний, которое может быть 
относительно невелико. Например, число сочетаний из n = 10 по 
m = 8 элементов равно всего 45. Однако чтобы найти это значение 
по факториальной формуле сначала нужно вычислить значительно 
большие величины 10! в числителе и 8! в знаменателе: 
 
8
10
10
10!
3628800
(10,8)
45.
8
8!(10
8)!
40320 2
C
C
⎛
⎞
=
=
=
=
=
⎜
⎟
−
⋅
⎝
⎠
 
Чтобы исключить трудоемкие операции обработки больших 
величин, для определения числа сочетаний можно воспользоваться 
различными рекуррентными соотношениями, которые непосредственно следуют из мультипликативной или факториальной формул. 
В частности, из мультипликативной формулы можно получить ре 
8 

куррентное соотношение, которое позволяет выносить за знак 
числа сочетаний отношение его нижнего и верхнего индексов: 
−
−
 
1
1
(
1)
(
1)
.
(
1)
1
m
m
n
n
n
n
m
n
n
C
C
m
m
m
−
−
+
=
=
−
…
…
 
Если при вычислениях важно сохранить неизменным верхний индекс числа сочетаний, тогда из факториальной формулы можно 
получить следующее рекуррентное соотношение: 
 
1
(
1)!
(
1)!
.
(
)(
1)!
!
(
1
)!
!
m
m
n
n
n n
n
n
n
C
C
n
m n
m
m
n
m n
m m
n
m
−
−
−
=
=
=
−
−
−
−
−−
−
 
Наконец, сохранение неизменным нижнего индекса обеспечивает 
соотношение, которое получается из факториальной формулы 
числа сочетаний путем умножения ее числителя и знаменателя на 
(n−m+1) и последующей группировки: 
 
1
(
1)
!
1
.
(
1)!(
(
1))!
m
m
n
n
n
m
n
n
m
C
C
m
m
n
m
m
−
−
−
−
+
=
=
−
−
−
 
После элементарных преобразований все три полученные рекуррентные соотношения можно представить в следующих видах: 
 
1
1
1
1
(
)
;
; (
1)
.
m
m
m
m
m
m
n
n
n
n
n
n
n
m C
nC
mC
nC
n
m
C
mC
−
−
−
−
−
=
=
−
+
=
 
−
−
=
+
 
Если теперь сложить левые и правые части двух первых формул и 
сократить результат на n, то получится рекуррентное соотношение, которое называется тождеством сложения для чисел сочетаний: 
 
1
1
1 .
m
m
m
n
n
n
C
C
C
−
Тождество сложения предоставляет основное рекуррентное правило 
для эффективного определения числа сочетаний при больших значениях n и m, так как оно позволяет заменить операции умножения 
в факториальных произведениях более простыми операциями сложения, причем для меньших чисел сочетаний. Используя тождество 
сложения, теперь несложно определить число сочетаний из n = 10 
по m = 8 элементов, которое рассматривалось ранее, выполнив следующую последовательность рекуррентных преобразований: 
 
9 

C
C
C
C
C
C
C
...
=
+
=
+
+
+
=
=
8
8
7
8
7
7
6
10
9
9
8
8
8
8
= 
2
3
4
5
6
7
8
9
45.
C
C
C
C
C
C
C
C
C
+
+
+
+
+
+
+
+
=
 
8
7
6
5
4
3
2
1
0
8
7
6
5
4
3
2
1
1
Кроме того, из тождества сложения можно вывести несколько 
полезных соотношений для вычисления конечных сумм, в частности формулу суммирования по нижнему индексу, которая имеет вид 
+
+
+
+
+
+
+
=
…
"
 
 
1
0
1
2
1 .
m
m
m
m
m
m
k
n
n
C
C
C
C
C
C
+
Такое соотношение получается, если в тождестве сложения разворачивать рекуррентность по слагаемому с наибольшим верхним 
индексом, пока его нижний индекс больше 0. Следующий численный пример иллюстрирует указанный процесс рекуррентных преобразований: 
C
C
C
C
C
C
C
C
C
C
=
+
=
+
+
=
+
+
+
=
2
2
1
2
1
1
2
1
1
1
4
3
3
2
2
3
1
1
2
3
C
C
C
C
C
C
C
C
C
=
=
+
+
+
+
=
+
+
+
 
2
1
1
1
1
1
1
1
1
0
0
1
2
3
0
1
2
3
                                
(
0)
.
Формула суммирования по нижнему индексу часто применяется 
для вычисления суммы степеней натуральных чисел. В частности, 
полагая m = 1, по этой формуле легко найти сумму n первых чисел 
натурального ряда: 
+
+ +
+
+
=
+
+
+
+
=
=
…
…
 
 
1
1
1
1
2
0
1
2
1
(
1)
0
1
2
.
2
n
n
n
n
n
C
C
C
C
C +
Еще один полезный вариант формулы суммирования можно 
получить, если разворачивать рекуррентность для тождества сложения по слагаемому с наименьшим верхним индексом: 
C
C
C
C
C
C
C
C
C
C
3
3
2
3
2
1
3
2
1
0
5
4
4
4
3
3
4
3
2
2
C
C
C
C
C −
=
+
=
+
+
=
+
+
+
=
=
+
+
+
+
=
 
3
2
1
0
1
4
3
2
1
1
                                                             
(
0).
В общем случае в результате таких преобразований получается 
сумма чисел сочетаний, оба индекса которых отличаются на единицу от соседних слагаемых, а разность индексов сохраняет постоянную величину (в рассмотренном примере она также равна 
единице). Таким образом получается формула суммирования по 
обоим индексам чисел сочетаний: 
 
10