Приближалась зима, и Хома с Сусликом решили запастись горохом. Весь день они бегали в амбар и таскали по несколько стручков: Хома по четыре, а Суслик по два. К вечеру они пересчитали все стручки, что они натаскали, и задумались, как теперь этот горох делить. Хома утверждал, что если он за раз тащил в два раза больше, чем Суслик, то и гороха ему должно достаться в два раза больше. Суслик на это резонно возражал, что, во-первых, скорость у Хомы заметно меньше, чем у Суслика, а, во-вторых, кто его знает, может Хома всего раз-два сбегал, а остальное время бездельничал…

Помогите друзьям хоть немного разобраться в этой сложной ситуации. Определите все возможные варианты того, сколько стручков притащил Суслик, а сколько Хома.

Входные данные

В первой строке натуральное четное число M – количество украденных стручков, 2 ≤ M ≤ 1000.

Выходные данные

Все возможные сочетания количеств стручков, принесенных Сусликом и Хомой по одному сочетанию в строке. Каждое сочетание представляет собой два целых неотрицательных числа через пробел: первое число – количество стручков, принесенных Сусликом, второе – принесенных Хомой. Сочетания упорядочить по убыванию первого числа.

Тесты

Входные данные	Выходные данные
6	\\ 6 \; 0 \\ 2 \; 4
11	\\ 11\;0 \\ 7\;4 \\ 3\;8
18	\\ 18\;0 \\ 14\;4 \\ 10\;8 \\ 6\;12 \\ 2\;16

Код программы

#include using namespace std ; int main () { int a , b = 0 ; cin >> a ; while (a >= 0 ) { cout << a << " " << b << "\n" ; a -= 4 ; b += 4 ; return 0 ;

Решение задачи

Пусть a — количество стручков, принесенных Хомой и b — количество стручков, принесенных Сусликом. Так как по условию задачи Хома таскал только по четыре стручка, мы будем считать a = a-4 и b = b + 4, чтобы таким образом перебрать все возможные сочетания количеств стручков, принесенных Сусликом и Хомой. Также воспользуемся циклом while , который будет повторять действие, описанное выше, до тех пор, пока a \geq 0. В ответе выводим все возможные сочетания количеств стручков, принесенных друзьями по одному в строке, упорядоченные по убыванию первого числа.

Рассмотрим задачу подсчета числа выборок из данного множества в общем виде. Пусть имеется некоторое множество N , состоящее из n элементов. Любое подмножество, состоящее из m элементов можно рассматривать без учета их порядка, так и с его учетом, т.е. при изменении порядка переходим к другой m – выборке.

Сформулируем следующие определения:

Размещения без повторения

Размещением без повторения из n элементов по m N , содержащее m различных элементов .

Из определения следует, что два размещения отличаются друг от друга, как элементами, так и их порядком, даже если элементы одинаковы.

Теорема 3 . Число размещений без повторения равно произведению m сомножителей, наибольшим из которых является число n . Записывают:

Перестановки без повторений

Перестановками из n элементов называются различные упорядочения множества N .

Из этого определения следует, что две перестановки отличаются только порядком элементов и их можно рассматривать как частный случай размещений.

Теорема 4 . Число различных перестановок без повторений вычисляется по формуле

Сочетания без повторений

Сочетанием без повторения из n элементов по m называется любое неупорядоченное подмножество множества N , содержащее m различных элементов.

Из определения следует, что два сочетания различаются только элементами, порядок не важен.

Теорема 5 . Число сочетаний без повторений вычисляют по одной из следующих формул:

Пример 1 . В комнате 5 стульев. Сколькими способами можно разместить на них

а) 7 человек; б) 5 человек; в) 3 человека?

Решение: а) Прежде всего надо выбрать 5 человек из 7 для посадки на стулья. Это можно сделать
способом. С каждым выбором конкретной пятерки можно произвести
перестановок местами. Согласно теореме умножения искомое число способов посадки равно.

Замечание: Задачу можно решать, используя только теорему произведения, рассуждая следующим образом: для посадки на 1-й стул имеется 7 вариантов, на 2-й стул-6 вариантов, на 3-й -5, на 4-й -4 и на 5-й -3. Тогда число способов посадки 7 человек на 5 стульев равно . Решения обоими способами согласуются, так как

б) Решение очевидно -

в) - число выборов занимаемых стульев.

- число размещений трех человек на трех выбранных стульях.

Общее число выборов равно .

Не трудно проверить формулы
;

;

Число всех подмножеств множества, состоящего из n элементов.

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

Размещением с повторением из n элементов по m называется всякое упорядоченное подмножество множества N , состоящее из m элементов так, что любой элемент ожжет входить в это подмножество от 1 до m раз, либо вообще в нем отсутствовать .

Число размещений с повторением обозначают и вычисляют по формуле, представляющей собой следствие из теоремы умножения:

Пример 2 . Пусть дано множество из трех букв N = {a, b, c}. Назовем словом любой набор из букв, входящих в это множество. Найдем количество слов длиной 2, которые можно составить из этих букв:
.

Замечание: Очевидно, размещения с повторением можно рассматривать и при
.

Пример 3 . Требуется из букв {a, b}, составить всевозможные слова длиной 3. Сколькими способами это можно сделать?

Ответ :

Сочетанием называется неупорядоченная выборка элементов конечного множества с фиксированным числом и без повторений элементов. Различные сочетания должны отличаться хотя бы одним элементом, а порядок расположения элементов не имеет значения. Например, из множества всех гласных латинских букв {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 элементов применяется следующая функциональная, индексная или векторная (Аппеля) символика:

Независимо от формы обозначения, число сочетаний из n элементов по m элементов можно определить по следующим мультипликативной и факториальной формулам:

Несложно проверить, что результат вычислений по этим формулам совпадает с результатами рассмотренного выше примера с сочетаниями гласных латинских буквам. В частности, при n=5 и m=3 вычисления по этим формулам дадут следующий результат:

В общем случае формулы числа сочетаний имеют комбинаторный смысл и справедливы при любых целочисленных значениях n и m, таких, что n > m > 0. Если m > n и m < 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:

Кроме того, полезно помнить следующие граничные числа сочетаний, которые легко проверить непосредственной подстановкой в мультипликативную и факториальную формулы:

Следует также отметить, что мультипликативная формула остается справедливой даже когда n является действительным числом, при по-прежнему целом значении m. Однако тогда результат вычисления по ней, сохраняя формальную справедливость, теряет комбинаторный смысл.

ТОЖДЕСТВА СОЧЕТАНИЙ

Практическое использование мультипликативной и факториальной формул для определения числа сочетаний при произвольных значениях n и m оказывается мало продуктивно из-за экспоненциального роста факториальных произведений их числителя и знаменателя. Даже при сравнительно небольших величинах n и m эти произведения часто превосходят возможности представления целых чисел в современных вычислительных и программных системах. При этом их величины оказываются значительно больше результирующего значения числа сочетаний, которое может быть сравнительно невелико. Например, число сочетаний из n=10 по m=8 элементов равно всего 45. Однако чтобы найти это значение по факториальной формуле нужно сначала вычислить значительно большие величины 10! в числителе и 8! в знаменателе:

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

Наконец, сохранение неизменным нижнего индекса обеспечивает следующее рекуррентное соотношение, которое легко получается из факториальной формулы числа сочетаний:

После элементарных преобразований три полученные рекуррентные соотношения можно представить в следующих видах:

Если теперь сложить левые и правые части 2-х первых формул и сократить результат на n, то получится важное рекуррентное соотношение, которое называется тождеством сложения чисел сочетаний:

Тождество сложения предоставляет основное рекуррентное правило для эффективного определения числа сочетаний при больших значениях n и m, так как оно позволяет заменить операции умножения в факториальных произведениях более простыми операциями сложения, причем для меньших чисел сочетаний. В частности, используя тождество сложения, теперь несложно определить число сочетаний из n=10 по m=8 элементов, которое рассматривалось выше, выполнив следующую последовательность рекуррентных преобразований:

Кроме того, из тождества сложения можно вывести несколько полезных соотношений для вычисления конечных сумм, в частности, формулу суммирования по нижнему индексу, которая имеет следующий вид:

Такое соотношение получается, если в тождестве сложения разворачивать рекуррентность по слагаемому с наибольшим верхним индексом, пока его нижний индекс больше 0. Следующий численный пример иллюстрирует указанный процесс рекуррентных преобразований:

Формула суммирования по нижнему индексу часто применяется для вычисления суммы степеней натуральных чисел. В частности, полагая m=1, по этой формуле легко найти сумму n первых чисел натурального ряда:

Еще один полезный вариант формулы суммирования можно получить, если разворачивать рекуррентность тождества сложения по слагаемому с наименьшим верхним индексом. Следующий численный пример иллюстрирует этот вариант рекуррентных преобразований:

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

Кроме рассмотренных выше рекуррентных соотношений и формул суммирования в комбинаторном анализе получено много других полезных тождеств для чисел сочетаний. Наиболее важным среди них является тождество симметрии , которое имеет следующий вид:

В справедливости тождества симметрии можно убедиться на следующем примере, сопоставив числа сочетаний из 5-ти элементов по 2 и по (5 2)=3:

Тождество симметрии имеет очевидный комбинаторный смысл, так как, определяя количество вариантов выбора m элементов из n элементов, оно одновременно устанавливает число сочетаний из остальных (nm) невыбранных элементов. Указанная симметрия немедленно получается взаимной заменой m на (nm) в факториальной формуле числа сочетаний:

Числа и тождества сочетаний широко применяются в различных областях современной вычислительной математики. Однако наиболее популярное их применение связано с биномом Ньютона и треугольником Паскаля.

БИНОМ НЬЮТОНА

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

В общем случае для произвольной степени n бинома искомое представление в форме многочлена предоставляет биномиальная теорема Ньютона, которая декларирует выполнение следующего равенства:

Это равенство обычно называют биномом Ньютона. Многочлен в его правой части образует сумма произведений n слагаемых X и Y бинома левой части, а коэффициенты перед ними называются биномиальными и равны числам сочетаний с индексами, которые получаются по их степеням. Учитывая особую популярность формулы бинома Ньютона в комбинаторном анализе, термины биномиальный коэффициент и число сочетаний принято считать синонимами.

Очевидно, формулы квадрата и куба суммы являются частными случаями биномиальной теоремы при n=2 и n=3, соответственно. Для обработки более высоких степеней (n>3) следует использовать формулу бинома Ньютона. Ее применение для бинома четвертой степени (n=4) демонстрирует следующий пример:

Следует отметить, что биномиальная формула была известна еще до Ньютона средневековым математикам арабского Востока и Западной Европы. Поэтому ее общепринятое название не является исторически справедливым. Заслуга Ньютона в том, что он обобщил эту формулу на случай произвольного вещественного показателя r, который может принимать любые положительные или отрицательные рациональные и иррациональные значения. В общем случае такая формула бинома Ньютона имеет бесконечную сумму в правой части и ее принято записывать следующим образом:

Например, при положительном дробном значении показателя степени r=1/2 с учетом значений биномиальных коэффициентов получается следующее разложение:

В общем случае формула бинома Ньютона при любом показателе является частным вариантом формулы Маклорена, которая дает разложение произвольной функции в степенной ряд. Ньютон показал, что при |z| < 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0 . Если теперь положить Z=X/Y и умножить левую и правую части на Yn, то получится вариант формулы бинома Ньютона, рассмотренный выше.

Несмотря на свою универсальность, биномиальная теорема сохраняет комбинаторный смысл только при целых неотрицательных степенях бинома. В этом случае с ее помощью можно доказать несколько полезных тождеств для биномиальных коэффициентов. В частности, выше были рассмотрены формулы суммирования чисел сочетаний по нижнему индексу и по обоим индексам. Недостающее тождество суммирования по верхнему индексу легко получить из формулы бинома Ньютона, положив в ней X = Y = 1 или Z = 1:

Еще одно полезное тождество устанавливает равенство сумм биномиальных коэффициентов с четными и нечетными номерами. Оно немедленно получается из формулы бинома Ньютона, если X = 1и Y = 1 или Z = 1:

Наконец, из обоих рассмотренных тождеств получается тождество суммы биномиальных коэффициентов только с четными или только с нечетными номерами:

На основе рассмотренных тождества и рекуррентного правила вынесения индексов из-под знака числа сочетаний можно получить целый ряд интересных соотношений. Например, если в формуле суммирования по верхнему индексу везде заменить n на (n1) и вынести индексы в каждом слагаемом, то получится следующее соотношение:

Используя аналогичную технику в формуле суммы биномиальных коэффициентов с четными и нечетными номерами, можно доказать справедливость, например, следующего соотношения:

Еще одно полезное тождество позволяет легко вычислить сумму произведений симметрично расположенных биномиальных коэффициентов двух биномов произвольных степеней n и k по следующей формуле Коши:

Справедливость этой формулы вытекает из необходимого равенства коэффициентов при любой степени m переменной Z в левой и правой части следующего тождественного соотношения:

В частном случае, когда n=k=m при учете тождества симметрии получается более популярная формула суммы квадратов биномиальных коэффициентов:

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

ТРЕУГОЛЬНИК ПАСКАЛЯ

Арифметический треугольник Паскаля образует бесконечная числовая таблица, составленная из биномиальных коэффициентов. Ее строки упорядочены по степеням биномов сверху вниз. В каждой строке биномиальные коэффициенты расположены по возрастанию верхних индексов соответствующих чисел сочетаний слева направо. Треугольник Паскаля принято записывать либо в равнобедренной, либо в прямоугольной форме.

Более наглядным и распространенным является равнобедренный формат, где биномиальные коэффициенты, располагаясь в шахматном порядке, образуют бесконечный равнобедренный треугольник. Его начальный фрагмент для биномов до 4-й степени (n=4) имеет следующий вид:

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

Однако для изучения различных свойств треугольника Паскаля удобнее применять формально более строгий прямоугольный формат. В этом формате его задает нижне-треугольная матрица биномиальных коэффициентов, где они образуют бесконечный прямоугольный треугольник. Начальный фрагмент прямоугольного треугольника Паскаля для биномов до 9-й степени (n=9) имеет следующий вид:

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

Начиная анализ горизонталей прямоугольного треугольника Паскаля, несложно заметить, что сумма элементов любой строки с номером n равна 2 n в соответствии с формулой суммирования биномиальных по верхнему индексу. Из этого следует, что сумма элементов над любой из горизонталей с номером n равна (2 n 1). Этот результат становится вполне очевидным, если значение суммы элементов каждой горизонтали записать в двоичной системе счисления. Например, для n=4 такое сложение можно записать следующим образом:

Вот еще пара интересных свойств горизонталей, которые также связаны со степенью двойки. Оказывается, что если номер горизонтали является степенью двойки (n=2 k), то все ее внутренние элементы (кроме крайних единиц) являются четными числами. Наоборот, все числа горизонтали будут нечетными, если ее номер на единицу меньше степени двойки (n=2 k 1). В справедливости этих свойств можно убедиться проверкой четности внутренних биномиальных коэффициентов, например, в горизонталях n=4 и n=3 или n=8 и n=7.

Пусть теперь номер строки прямоугольного треугольника Паскаля есть простое число p. Тогда все ее внутренние биномиальные коэффициенты делятся на p. Это свойство несложно проверить для малых значений простых номеров горизонталей. Например, все внутренние биномиальные коэффициенты пятой горизонтали (5, 10 и 5), очевидно, делятся на 5. Чтобы доказать справедливость этого результата для любого простого номера горизонтали p, нужно записать мультипликативную формулу ее биномиальных коэффициентов следующим образом:

Поскольку p есть простое число и, следовательно, не делится на m!, то произведение остальных сомножителей числителя этой формулы обязано делиться на m!, чтобы гарантировать целое значение биномиального коэффициента. Отсюда следует, что отношение в квадратных скобках является натуральным числом N и искомый результат становится очевидным:

Используя этот результат, можно установить, что номера всех горизонталей треугольника Паскаля, внутренние элементы которых делятся на заданное простое число p, являются степенью p , то есть имеют вид n=p k . В частности, если p=3, то простое число p делит не только все внутренние элементы строки 3, как было установлено выше, но, например, 9-й горизонтали (9, 36, 84 и 126). С другой стороны, в треугольнике Паскаля нельзя найти горизонталь, все внутренние элементы которой делятся на составное число. В противном случае номер такой горизонтали обязан быть одновременно степенью простых делителей составного числа, на которое делятся все ее внутренние элементы, но это по очевидным причинам невозможно.

Рассмотренные соображения позволяют сформулировать следующий общий признак делимости горизонтальных элементов треугольника Паскаля. Наибольший общий делитель (НОД) всех внутренних элементов любой горизонтали треугольника Паскаля с номером n равен простому числу p, если n=pk или 1 во всех остальных случаях:

НОД(Cmn) = { } для любых 0 < m < n .

В заключение анализа горизонталей стоит рассмотреть еще одно любопытное свойство, которым обладают образующие их ряды биномиальных коэффициентов. Если биномиальные коэффициенты любой горизонтали с номером n умножить на последовательные степени числа 10, а затем сложить все эти произведения, то получится 11 n . Формальным обоснованием этого результата является подстановка значений X=10 и Y=1 (или Z=1) в формулу бинома Ньютона. Следующий численный пример иллюстрирует выполнение этого свойства при n=5:

Анализ свойств вертикалей прямоугольного треугольника Паскаля можно начать с изучения индивидуальных особенностей составляющих их элементов. Формально каждую вертикаль m образует следующая бесконечная последовательность биномиальных коэффициентов с постоянным верхним индексом (m) и инкрементом нижнего индекса:

Очевидно, при m=0 получается последовательность единиц, а при m=1 образуется ряд натуральных чисел. При m=2 вертикаль составляют треугольные числа. Каждое треугольное число можно изобразить на плоскости в виде равностороннего треугольника, который заполняют произвольные объекты (ядра), расположенные в шахматном порядке. При этом значение каждого треугольного числа T k определяет количество изображающих ядер, а индекс показывает, сколько рядов ядер нужно для его представления. Например, 4 начальных треугольных числа представляют следующие конфигурации из соответствующего числа ядерных символов "@":

Следует отметить, что аналогичным образом можно ввести в рассмотрение квадратные числа S k , которые получаются возведением в квадрат натуральных чисел и, вообще, многоугольные фигурные числа, образованные регулярным заполнением правильных многоугольников. В частности, 4 начальных квадратных числа можно изобразить следующим образом:

Возвращаясь к анализу вертикалей треугольника Паскаля, можно отметить, что следующую вертикаль при m=3 заполняют тетраэдальные (пирамидальные) числа. Каждое такое число P k задает количество ядер, которое можно расположить в форме тетраэдра, а индекс определяет, сколько горизонтальных треугольных слоев из рядов ядер требуется для его изображения в трехмерном пространстве. При этом все горизонтальные слои должны представляться как последовательные треугольные числа. Элементы следующих вертикалей треугольника Паскаля при m>3 образуют ряды гипертетраэдальных чисел, которые не имеют наглядной геометрической интерпретации на плоскости или в трехмерном пространстве, но формально соответствуют многомерным аналогам треугольных и тетраэдальных чисел.

Хотя вертикальные числовые ряды треугольника Паскаля имеют рассмотренные индивидуальные фигурные особенности, но для них можно одинаковым образом вычислять частичные суммы значений начальных элементов, используя формулу суммирования чисел сочетаний по нижнему индексу. В треугольнике Паскаля эта формула имеет следующую геометрическую интерпретацию. Сумма значений n верхних биномиальных коэффициентов любой вертикали равна значению элемента следующей вертикали, который расположен на одну строку ниже. Этот результат также соответствует геометрической структуре треугольных, тетраэдальных и гипертетраэдальных чисел, поскольку представление каждого такого числа состоит из ядерных слоев, которые изображают числа более низкого порядка. В частности, n-е треугольное число T n можно получить, суммируя все натуральные числа, изображающие его линейные слои:

Аналогичным образом несложно найти тетраэдальное число P n , вычислив следующую сумму n первых треугольных чисел, которые составляют его горизонтальные ядерные слои:

Помимо горизонталей и вертикалей в прямоугольном треугольнике Паскаля можно проследить диагональные ряды элементов, изучение свойств которых также представляет определенный интерес. При этом обычно различают нисходящие и восходящие диагонали. Нисходящие диагонали параллельны гипотенузе прямоугольного треугольника Паскаля. Их образуют ряды биномиальных коэффициентов с инкрементом обоих индексов. В силу тождества симметрии нисходящие диагонали совпадают по значениям своих элементов с соответствующими вертикальными рядами треугольника Паскаля и поэтому повторяют все их свойства, рассмотренные выше. Указанное соответствие можно проследить по совпадению значений элементов нисходящей диагонали и вертикали с любым номером n, если не учитывать вертикальные нули:

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

В общем случае на восходящей диагонали с номером n стоят следующие биномиальные коэффициенты, сумма индексов каждого из которых равна (n1):

В силу тождества сложения для чисел сочетаний каждый диагональный элемент равен сумме двух соответствующих по индексам элементов из двух предыдущих восходящих диагоналей. Это позволяет строить каждую следующую восходящую диагональ попарным суммированием соседних горизонтальных элементов из двух предыдущих диагоналей, бесконечно расширяя треугольник Паскаля по диагонали. Следующий фрагмент треугольника Паскаля иллюстрирует построение восходящей диагонали с номером 8 по диагоналям с номерами 6 и 7:

При таком способе построения сумма элементов любой восходящей диагонали, начиная с 3-й, будет равна сумме элементов двух предыдущих восходящих диагоналей, а первые 2 диагонали состоят только из одного элемента, значение которого равно 1. Результаты соответствующих вычислений образуют следующий числовой ряд, по которому можно проверить справедливость рассмотренного свойства восходящих диагоналей прямоугольного треугольника Паскаля:

Анализируя эти числа, можно заметить, что по аналогичному закону образуется хорошо известная последовательность чисел Фибоначчи, где каждое очередное число равно сумме двух предыдущих, а два первых числа равны 1:

Таким образом, можно сделать следующий важный вывод: диагональные суммы элементов треугольника Паскаля составляют последовательность Фибоначчи. Это свойство позволяет установить еще одну интересную особенность треугольника Паскаля. Раскрывая рекурсивно формулу Фибоначчи, несложно доказать, что сумма первых n чисел Фибоначчи равна (F n+2 1).

Поэтому сумма биномиальных коэффициентов, которые заполняют верхние n диагоналей, также равна (F n+2 1). Отсюда следует, что сумма n первых диагоналей треугольника Паскаля на 1 меньше суммы биномиальных коэффициентов, которые стоят на его диагонали с номером (n+2).

В заключение следует отметить, что рассмотренные свойства горизонталей, вертикалей и диагоналей треугольника Паскаля далеко не исчерпывают огромное разнообразие возможностей, которые связывают воедино различные математические аспекты, на первый взгляд не имеющие ничего общего. Столь необычные свойства позволяют считать треугольник Паскаля одной из наиболее совершенных числовых систем, все возможности которой невозможно перечислить и трудно переоценить.

Алгоритм вычисления числа сочетаний с использованием треугольника Паскаля представлен ниже:

Private Function SochTT (ByVal n As Integer, ByVal k As Integer) As Double Dim i As Integer Dim j As Integer Dim TT () As Double ReDim TT (n, k) For i = 0 To n TT (0, i) = 1 TT (i, i) = 1 Next For i = 2 To n For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Next Next SochTT = TT (n, k) End Function

Если Вам нужно вычислять число сочетаний много раз, то, возможно, будет удобнее один раз построить треугольник Паскаля, а затем получать из массива данные.

Dim TT () As Double Private Sub CreateTT () ReDim TT (0, 0) BuildTT 0, 0 End Sub Private Function SochTT (ByVal n As Integer, ByVal k As Integer) As Double If n > Ubound (TT) Then BuildTT Ubound (TT) + 1, n SochTT = TT (n, k) End Function Private Sub TerminateTT () ReDim TT (0, 0) End Sub Private Sub BuildTT (ByVal start As Integer, ByVal end As Integer) Dim i As Integer Dim j As Integer ReDim Preserve TT (end, end) For i = start To end TT (0, i) = 1 TT (i, i) = 1 Next If end < 2 Then Exit Sub If start < 2 Then start = 2 For i = start To end For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Next Next End Sub

Сначала нужно вызвать процедуру CreateTT. Затем Вы можете получать число сочетаний с помощью функции SochTT. Когда треугольник станет Вам не нужен, вызовите процедуру TerminateTT. В вышеуказанном коде при вызове функции SochTT, если треугольник ещё не достроен до необходимого уровня, то он достраивается с помощью процедуры BuildTT. Затем функция получает нужный элемент массива TT и возвращает его.

Dim X () As Integer Dim Counter () As Integer Dim K As Integer Dim N As Integer Public Sub Soch() Dim i As Integer N = CInt(InputBox("Введите N")) K = CInt(InputBox("Введите K")) K = K + 1 ReDim X(N) For i = 1 To N X(i) = i Next txtOut.Text = "" ReDim Counter(K) Counter(0) = 1 SochGenerate 1 End Sub Private Sub SochGenerate(ByVal c As Integer) Dim i As Integer Dim j As Integer Dim n1 As Integer Dim Out() As Integer Dim X1() As Integer If c = K Then ReDim Out(K) X1 = X For i = 1 To K - 1 n1 = 0 For j = 1 To N If X1(j) <> 0 Then n1 = n1 + 1 If n1 = Counter(i) Then Out(i) = X1(j) X1(j) = 0 Exit For End If Next txtOut.Text = txtOut.Text & CStr(Out(i)) Next txtOut.Text = txtOut.Text & vbCrLf Else For Counter(c) = Counter(c - 1) To N - c + 1 SochGenerate c + 1 Next End If End Sub

ПЕРЕЧИСЛЕНИЕ СОЧЕТАНИЙ НАТУРАЛЬНЫХ ЧИСЕЛ

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

Для формального описания этого алгоритма удобно считать, что основное множество, все сочетания по m элементов которого необходимо перечислить, образуют последовательные натуральные числа от 1 до n. Тогда любое сочетание из m

В результате упорядочивания значение в каждой позиции такого вектора сочетаний естественно оказывается ограниченным по величине сверху и снизу следующим образом:

Лексиграфический алгоритм последовательно формирует такие векторы сочетаний, начиная с лексиграфически наименьшего вектора, где во всех позициях стоят следующие минимально возможные значения элементов, равные их индексам:

Каждый очередной вектор сочетания формируется из текущего после просмотра его элементов слева направо с целью найти самый правый элемент, который еще не достиг своего предельного значения:

Значение такого элемента следует увеличить на 1. Каждому элементу справа от него нужно присвоить наименьшее возможное значение, которое на 1 больше, чем у соседа слева. После указанных изменений очередной вектор сочетаний будет иметь следующий элементный состав:

Таким образом, очередной вектор сочетания будет лексиграфически больше предыдущего, так как значения их начальных (j1) элементов равны по величине, а значение элемента в позиции j на 1 больше, чем у предыдущего. Указанное отношение возрастающего лексиграфического порядка гарантированно выполняется на всех итерациях алгоритма. В результате образуется возрастающая лексиграфическая последовательность, которую завершает лексиграфически наибольший вектор сочетания, где элементы во всех позициях имеют следующие максимальные значения:

Рассмотренный лексиграфический алгоритм иллюстрирует следующий пример, где нужно перечислить в возрастающем лексиграфическом порядке все 15 сочетаний из n=6 первых натуральных чисел по m=4 числа, то есть все возможные 4-х элементные подмножества основного образующего множества {1, 2, 3, 4, 5, 6} из 6-ти элементов. Результаты вычислений представлены в следующей таблице:

В этом примере наибольшие допустимые значения чисел в позициях векторов сочетаний равны, соответственно, 3, 4, 5 и 6. Для удобства интерпретации результатов в каждом векторе сочетаний подчеркиванием выделен крайний правый элемент, который еще не достиг своего максимального значения. Числовые индексы векторов сочетаний определяют их номера в лексиграфическом порядке. В общем случае лексиграфический номер N любого сочетания из n элементов по m можно вычислить по следующей формуле, где из косметических соображений для обозначения чисел сочетаний использована символика Аппеля:

В частности, следующие вычисления по этой формуле номера сочетания (1, 3, 4, 6) из n=6 элементов по m=4 в лексиграфическом порядке дадут результат N=8, который соответствует примеру, рассмотренному выше:

В общем случае, используя тождество для суммы чисел сочетаний по обоим индексам, можно показать, номер лексиграфически наименьшего сочетания (1, … i, … m) при вычислении его по данной формуле всегда будет равен 1:

Очевидно также, что номер лексиграфически наибольшего сочетания (m, … nm+i, …n) при вычислении его по данной формуле будет равен числу сочетаний из n элементов по m:

Формулу вычислений лексиграфических номеров сочетаний можно использовать для решения обратной задачи, где требуется определить вектор сочетания по его номеру в лексиграфическом порядке. Для решения такой обратной задачи ее нужно записать в виде уравнения, где все неизвестные значения элементов вектора искомого сочетания (C 1 , … C i , … C m) сосредоточены в числах сочетаний его правой части, а в левой части записана известная разность L числа сочетаний из n элементов по m и номера искомого сочетания N:

Решение этого уравнения обеспечивает следующий "жадный" алгоритм, на итерациях которого производится последовательный выбор значений элементов вектора искомого сочетания. На начальной итерации выбирается минимально возможное (в пределах своих ограничений) значение C 1 , при котором первое слагаемое правой части будет иметь максимальное значение, не превосходящее L:

Теперь левую часть L следует уменьшить на первое число сочетаний в правой части при выбранном значении C 1 , и аналогичным образом определить значение C 2 на второй итерации:

Аналогичным образом следует выполнить все последующие итерации, чтобы выбрать значения всех остальных элементов C i искомого сочетания, вплоть до последнего элемента C m:

По очевидным причинам значение последнего элемента C m можно определить исходя уже из равенства его числа сочетаний остаточному значению левой части L:

Следует отметить, что значение последнего элемента сочетания C m можно найти еще более просто, без перебора его возможных значений:

Выполнение итераций рассмотренного алгоритма иллюстрирует следующий пример, где нужно определить сочетания с номером N=8 в лексиграфическом порядке, если n=6 и m=4:

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

Теперь приведем алгоритм генерации сочетаний в лексикографическом порядке:

2 for i:= 1 to k do A[i] := i;

5 begin write(A, …, A[k]);

6 if A[k] = n then p:= p 1 else p:= k;

8 for i:= k downto p do A[i] := A[p] + i p + 1

СОЧЕТАНИЯ С ПОВТОРЕНИЯМИ ЭЛЕМЕНТОВ

В отличие от классического сочетания, где все элементы различны, сочетание с повторениями образует неупорядоченная выборка элементов конечного множества, где любой элемент может появляться неопределенно часто и присутствовать необязательно в единственном экземпляре. При этом количество повторений элементов обычно ограничено только длиной сочетания, а различными считаются сочетания, которые отличаются хотя бы одним элементом. Например, выбирая по 4 необязательно различные цифры из набора 1, 2 и 3 можно составить следующие 15 сочетаний с повторениями:

1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.

В общем случае сочетания с повторениями могут быть образованы выборкой из n элементов произвольных типов. Однако им всегда можно сопоставить последовательные натуральные числа от 1 до n. Тогда любое сочетание из m необязательно различных чисел этого диапазона можно записать в векторной форме, располагая их в неубывающем порядке слева направо:

Естественно, при такой форме записи любые соседние элементы могут быть равны вследствие возможности неограниченных повторений. Однако каждому вектору сочетания с повторениями из n элементов по m можно поставить в соответствие вектор сочетания из (n+m−1) элементов по m, который конструируется следующим образом:

Ясно, что при любых значениях элементов вектора f элементы вектора C будут гарантированно различны и строго упорядочены по возрастанию своих значений из диапазона от 1 до (n+m1):

Наличие взаимно однозначного соответствия между элементами векторов сочетаний f и C позволяет предложить следующий простой метод систематического перечисления сочетаний с повторениями из n элементов по m. Нужно только перечислить, например, в лексиграфическом порядке все C сочетания из (n+m1) элементов по m, последовательно преобразуя элементы каждого из них в соответствующие элементы сочетаний с повторениями f по следующей формуле:

В результате образуется последовательность векторов сочетаний с повторениями элементов, которые расположены в порядке, порождаемом перечислением соответствующих сочетаний без повторений элементов. В частности, для того, чтобы получить представленную выше последовательность сочетаний из 3-х цифр 1, 2 и 3 с повторениями по 4 цифры, требуется перечислить в лексиграфическом порядке все сочетания без повторений из 6-ти цифр 1,2,3,4,5 и 6 по 4 цифры, преобразуя их указанным образом. В следующем примере показано такое преобразование сочетание (1,3,4,6) с лексиграфическим номером 8:

Рассмотренное взаимно однозначное соответствие между сочетаниями с повторениями и без повторений элементов означает, что их множества равномощны. Поэтому в общем случае число сочетаний с повторениями из n элементов по m равно числу сочетаний без повторений из (n+m1) элементов по m. Используя одинаковую символику для обозначения чисел сочетаний с повторениями f и без повторений C, это равенство можно записать следующим образом:

Несложно проверить, что для рассмотренного выше примера, где n=3 и m=4, число сочетаний с повторения будет равно 15, что совпадает с результатом их непосредственного перечисления:

Следует отметить, что в отличие от классического варианта, значения параметров сочетания с повторениями n и m непосредственно не связаны между собой, поэтому f(n,m)>0 при любой комбинации их положительных значений. Соответствующие граничные условия определяются из равенства между значениями (n+m1) и (n1) или (n+m1) и m:

Также должно быть вполне очевидно, что если m равно 1, то никакие повторения элементов невозможны и, следовательно, при любом положительном значении n>0 будет справедливо следующее равенство:

Кроме того, для чисел сочетаний с повторениями при любых положительных значениях n и m справедливо следующее рекуррентное соотношение, которое похоже на тождество сложения для чисел сочетаний без повторений элементов:

Собственно, оно и превращается в указанное тождество сложения при формальной подстановке соответствующих чисел сочетаний без повторений в его левую и правую части:

Рассмотренное рекуррентное соотношение можно использовать для эффективного определения чисел сочетаний с повторениями, когда важно исключить трудоемкие операции вычисления факториальных произведений и заменить их более простыми операциями сложения. При этом для вычисления значения f(n,m) нужно только применять данное рекуррентное соотношение до получения суммы слагаемых вида f(1,m) и f(i,1), где i принимает значениями в диапазоне от n до 1. По определению величины таких слагаемых равны 1 и i, соответственно. Следующий пример иллюстрирует использование данной техники преобразований для случая n=3 и m=4:

ПЕРЕЧИСЛЕНИЕ БИНАРНЫХ СОЧЕТАНИЙ

При аппаратной реализации сочетаний или при программировании на языке ассемблера важно иметь возможность обработки записей сочетаний в двоичном формате. В этом случае любое сочетание из n элементов по m следует задавать в форме n-разрядного двоичного числа (B n ,…B j ,…B 1), где m единичных разрядов обозначают элементы сочетания, а остальные (nm) разрядов имеют нулевые значения. Очевидно, что при такой форме записи различные сочетания должны отличаться расположением единичных разрядов и существует всего C(n,m) способов расположить m единиц или (nm) нулей в n-разрядном двоичном наборе. Например, в следующей таблице перечислены все 6 таких бинарных сочетаний, которые обеспечивают запись 4-х разрядными двоичными числами всех сочетаний из 4-х элементов произвольного множества {E 1 ,E 2 ,E 3 ,E 4 } по 2:

В общем случае задача перечисления таких бинарных сочетаний сводится к систематическому перебору всех n-разрядных двоичных наборов с различным расположением m единичных и (nm) нулевых разрядов. В наиболее простой форме такой перебор реализуют различные методы транспозиции смежных разрядов со сдвигом (транспозитивно-сдвиговые алгоритмы). Это итерационные алгоритмы, а их названия отражают характер операций, выполняемых на каждом шаге. Итерационные процедуры транспозитивно-сдвиговых алгоритмов формируют последовательности бинарных сочетаний, которые начинаются двоичным набором, где все единицы сосредоточены в младших разрядах (справа), и завершаются, когда все единицы будут находиться в старших разрядах (слева):

Совпадая по начальным и конечным сочетаниям, эти последовательности отличаются порядком перечисления промежуточных двоичных наборов. Однако во всех случаях каждое следующее бинарное сочетание формируется по предыдущему в результате выполнения соответствующих операций транспозиции и сдвига. При этом различные транспозитивно-сдвиговые алгоритмы отличаются способом выбора пары разрядов для транспозиции и группы разрядов для сдвига. Эта специфика рассмотрена ниже для алгоритмов транспозиции с левым и правым сдвигом.

В алгоритме транспозиции с левым сдвигом на каждом шаге очередное бинарное сочетание получается из текущего заменой крайней левой пары разрядов 01 на 10 (транспозиция) и смещением группы лидирующих единичных разрядов, если таковые имеются, вплотную к паре 10, полученной после транспозиции (сдвиг). Если при этом в текущем бинарном сочетании нет единиц в старших разрядах, то сдвиг не производится, даже когда лидирующая единица получается после транспозиции на данном шаге. Сдвиг также не производится, когда в старших разрядах перед парой 10, полученной после транспозиции нет нулей. Рассмотренные действия иллюстрирует следующий пример выполнения двух последовательных итераций данного алгоритма, где на одной итерации (15) производится только транспозиция (T"), а на другой итерации (16) транспозицию дополняет сдвиг (T"+S"):

В алгоритме транспозиции с правым сдвигом на каждом шаге выполняются концептуально аналогичные действия. Только транспозиция обеспечивает замену крайней правой разрядов 01 на 10 (вместо крайней левой), а затем производится сдвиг всех единиц справа от нее в младшие разряды. Как и раньше сдвиг производится только при наличии единиц, которые могут быть смещены вправо. Рассмотренные действия иллюстрирует следующий пример выполнения двух последовательных итераций данного алгоритма, где на одной итерации (3) производится только транспозиция (T"), а на другой итерации (4) транспозицию дополняет сдвиг (T"+S"):

Следует отметить, что итерации обоих алгоритмов можно записать в аддитивной форме, если интерпретировать бинарные сочетания как целые числа в системе счисления по основанию 2. В частности, для алгоритма транспозиции с правым сдвигом каждое очередное бинарное сочетание (B" n ,…B" j ,…B" 1), можно всегда получить из текущего сочетания (B n ,…B j ,…B 1), выполнив операции сложения целых чисел по следующей аддитивной формуле:

В этой аддитивной формуле, показатели степеней двоек f и t обозначают, соответственно, число нулевых младших разрядов текущего бинарного сочетания и количество единиц, стоящих подряд слева от них. Например, для 4-го бинарного сочетания (001110) из n=6 разрядов f =1 и t =3. Следовательно, вычисление очередного бинарного сочетания по аддитивной формуле на итерации 5 даст следующий результат, эквивалентный выполнению операций транспозиции и сдвига:

Для сравнительного анализа рассмотренных алгоритмов транспозиции с левым и правым сдвигом целесообразно сопоставить последовательности бинарных сочетаний, которые они порождают на своих итерациях. В следующей таблице показаны две такие последовательности бинарных сочетаний из 4-х элементов по 2, которые получены алгоритмами с левым (TSL) и правым (TSR) сдвигом, соответственно:

Сравнивая эти 2 последовательности, можно заметить, что они являются обратно-зеркальными. Это означает, что любые два бинарных сочетания, которые расположены в них на одинаковом расстоянии от взаимно-противоположных концов своих последовательностей, являются зеркальным отображением друг друга, то есть совпадают при изменении на обратную индексации разрядов в любом из них. Например, второе от начала последовательности TSL бинарное сочетание (0101) является зеркальным отображением бинарного сочетания (1010), которое находится на втором месте от конца последовательности TSR. В общем случае любое бинарное сочетание с номером i одной последовательности является зеркальным отображение бинарного сочетания с номером (ni+1) другой последовательности. Такое соотношение этих последовательностей является следствием симметричного характера операций транспозиции и сдвига в двух рассмотренных алгоритмах перечисления бинарных сочетаний.

Следует отметить, что двоичный формат можно применить также для записи сочетаний с повторениями элементов. Для этого нужно установить взаимно однозначное соответствие между сочетаниями с повторениями и бинарными сочетаниями, которые конструируются следующим образом. Пусть имеется произвольное сочетание с повторениями, которое получено выбором m необязательно различных элементов из n элементов образующего множества. Для установления искомого соответствие нужно сначала присоединить к сочетанию все элементы образующего множества (cat), а затем отсортировать полученную конкатенацию (sort), чтобы все одинаковые элементы оказались рядом. В результате получится последовательность из (n+m) элементов, где n групп одинаковых элементов. Между элементами в ней будет всего (n+m1) промежутков, среди которых будет (n1) промежутков между группами одинаковых элементов и m промежутков между элементами внутри групп. Для наглядности в указанных промежутках можно разместить символы "|" и "", соответственно. Если теперь сопоставить 1 промежуткам между группами (|) и 0 всем остальным промежуткам (), то получится бинарное сочетание. Его образует двоичный набор из (n+m1) разрядов, где (n1) единичных и m нулевых разрядов, расположение которых однозначно соответствует исходному сочетанию с повторениями из элементов n по m. Рассмотренную технику преобразований иллюстрирует следующий пример построения бинарного сочетания (1001101) по сочетанию с повторениями (BBD), элементы которого выбраны из образующего множества первых пяти латинских букв:

В общем случае количество таких двоичных наборов определяет число способов расположить (n1) единиц (или m нулей) в (n+m1) двоичных разрядах. Это значение, очевидно, равно числу сочетаний из (n+m1) по (n1) или по m, то есть C(n+m1,n1) или C(n+m1,m), которое равно числу сочетаний с повторениями f(n,m)из n элементов по m. Таким образом, имея взаимно однозначное соответствие между сочетаниями с повторениями и бинарными сочетаниями правомерно свести перечисление сочетаний с повторениями к перебору бинарных сочетаний, например, по алгоритмам транспозиции с левым или правым сдвигом. После этого нужно только восстановить искомые сочетания с повторениями по полученным бинарным сочетаниям. Это всегда можно сделать, применив следующий восстановительный прием.

Пусть основное множество, из элементов которого образуются сочетания с повторениями по m необязательно различных элементов, упорядочено произвольным образом так, что каждый его элемент имеет определенный порядковый номер от 1 до n. Пусть также реализовано перечисление бинарных сочетаний из (n+m1) двоичных разрядов, где (n1) единичных и m нулевых разрядов. Каждое полученное бинарное сочетание можно дополнить слева фиктивным единичным разрядом, и пронумеровать все единичные разряды слева направо целыми числами от 1 до n. Тогда число нулей, стоящих подряд после каждой i-й единицы бинарного сочетания, будет равно количеству экземпляров i-го элемента основного множества в соответствующем сочетании с повторениями. Рассмотренный прием иллюстрирует следующий пример, где по бинарному сочетанию (1001101) восстанавливается сочетание с повторениями BBD, элементы которого выбраны из образующего множества первых пяти латинских букв, записанных в алфавитном порядке, а надчеркивание обозначает элементы, отсутствующие в этом сочетании:

Выполняя аналогичные действия в условиях данного примера, можно перечислить все 35 бинарных сочетаний, которые образуют 7-ми разрядные двоичные наборы, где 4 единицы и 3 нуля, и восстановить соответствующие им сочетания с повторениями из 5-ти элементов по 3.

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

Пример

// Сочетания по 3 из 52 for (int i1 = 0; i1 < 50; ++i1) for (int i2 = i1+1; i2 < 51; ++i2) for (int i3 = i2+1; i3 < 52; ++i3) // ...

Индекс сочетания

Каждому сочетанию, перестановке, размещению и другим комбинаторным объектам можно сопоставить индекс - это номер, в котором он появляется при переборе данным алгоритмом.

Здесь мы рассмотрим более сложную задачу, решения которой в рунете я не нашел (впрочем, приведу одну ссылку , но та формула явно неверная) - исходя из самого сочетания (в данном случае набора трех чисел) найти его индекс.

Есть вариант перебора «в лоб». Включаем счетчик сочетаний, берем алгоритм выше и пока не дойдем до нужного варианта перебираем все подряд. Такой вариант имеет очень большую временную сложность, поэтому такой вариант отбросим.
Положим, на входе имеются числа i1, i2, i3. Нам, прежде всего, нужно их упорядочить в порядке возрастания (обратите внимание, что сам алгоритм генерации, приведенный выше, выдает их всегда в упорядоченном виде, хотя само понятие «сочетание» подразумевает произвольный порядок).

Положим, для определенности, после упорядочивания i1 = 3, i2 = 7, i3 = 12.
Это значит, мы «прошли» все сочетания, где i1 было равным 0, 1 и 2.
Для i1 = 0 мы прошли C(2, 51) сочетаний, поскольку индексы i1, i2 пробегают все сочетания по 2 из 51 числа.
Для i1 = 1 мы прошли C(2, 50) сочетаний.
Для i1 = 2 мы прошли C(2, 49) сочетаний.
Итого мы прошли СУММА {от n = 0 по n = i1-1) C(2, 51-n}.
При i1 = 3 рассмотрим уже те сочетания, которые мы прошли, бегая по индексу i2 (а он у нас начинается с i2 = i1+1 = 4).
При i2 = 4 прошли C(1, 47) сочетаний, при i2 = 5 прошли C(1, 46) сочетаний, при i2 = 6 прошли C(1, 45) сочетаний.
По полной аналогии, при i2 = 7 рассматриваем сочетания, которые пробежал индекс i3.
Получаем общую формулу:
Искомый индекс сочетания = СУММА {от n = 0 по i1-1} C(2, 51-n) + СУММА {от n = i1+1 по i2-1} C(1, 51-n) + СУММА {от n = i2+1 по i3-1} C (0, 51-n).

Индекс разбиения на подмножества

В комбинаторике есть и более сложный объект - разбиение на подмножества. К примеру, разбиение 52-элементного множества на три подмножества, состоящие соответственно, скажем, из 2, 3 и 47 элементов, где порядок элементов внутри каждого подмножества неважен. (Кстати сказать, сочетание по 2 из 52 - это просто частный случай разбиения на два подмножества из 2 и 50 элементов соответственно).

Типовой алгоритм генерации заключается в том, что мы генерируем сочетания по 2 из 52, и для каждого такого сочетания во вложенном цикле генерируем сочетания по 3 из 50, причем проверяем, чтобы индексы (i3, i4, i5) во вложенном сочетании не совпадали с индексами (i1, i2) во внешнем сочетании:

Код на C++

// ВНЕШНЕЕ СОЧЕТАНИЕ for (int i1 = 0; i1 < 51; ++i1) for (int i2 = i1+1; i2 < 52; ++i2) // ВНУТРЕННЕЕ СОЧЕТАНИЕ for (int i3 = 0; i3 < 50; ++i3) if (i3 != i1 && i3 != i2) for (int i4 = i3+1; i4 < 51; ++i4) if (i4 != i1 && i4 != i2) for (int i5 = i4+1; i5 < 52; ++i5) if (i5 != i1 && i5 != i2) // ...

Опять же, каждое такое разбиение имеет свой индекс.
Оказывается, наш алгоритм нахождения индекса сочетания можно модифицировать для нахождения индекса разбиения.
Надо обратить внимание, что индексы во «внешнем сочетании» i1, i2 нам нужно упорядочивать между собой, а индексы i3, i4, i5 - между собой, но независимо от первых двух.
Также следует учесть, что во «вложенном сочетании» по сути мы работаем с 50-элементным множеством, но индексы i3, i4, i5 нужно определенным образом «сдвинуть», чтобы они менялись не от 0 до 51, а от 0 до 49:

Код на C++

if (i3 >= i1) --i3; if (i3 >= i2) --i2; // аналогично для i4, i5

(так сказать, мы вырезаем из нашего 52-элементного множества индексы i1, i2 и потом сдвигаем оставшееся множество, чтобы закрыть дырки, при этом сдвигаются индексы i3-i5).
Следует учесть при этом, что внутри каждого «внешнего» сочетания у нас сидит ровно C(3, 50) «вложенных» сочетаний.
Тогда алгоритм сведется к следующему:
ИНДЕКС_СОЧЕТАНИЯ (i1, i2 из 52) * ЧИСЛО_СОЧЕТАНИЙ_ПО_3_ИЗ_50 + ИНДЕКС_СОЧЕТАНИЯ (i3, i4, i5 из 50 после сдвига индексов).

Приведение алгоритмов к константной сложности

Сразу должен обратить внимание, что в формуле возникает «ошибка», если например, i1 = 0 (мы считаем сумму для n = от 0 до -1) или i2 = 1 (считаем сумму от 1 до 0). На самом деле в таких случаях соответствующую сумму следует принимать равной нулю, и результат получится корректным.
Также должен обратить внимание на временнУю сложность наших алгоритмов: они имеют линейную сложность при условии, что C вы считаете за константное время. Это уже намного лучше, чем перебор «в лоб».
Но на самом деле (в нашем случае 52) ничего не мешает свести алгоритм к константной сложности. Для этого применим знания математики и аналитически посчитаем все суммы.
Например, число сочетаний C(2, K), если «раскрыть» его в виде формулы K! / ((K-2)! * 2!), приводится к многочлену 2-й степени. А поскольку он у нас под знаком суммы, то можно применить формулы суммы N-х степеней чисел натурального ряда (см. Википедию) и получить один-единственный многочлен 3-й степени. Который, очевидно, имеет константную временную сложность. (Причем «ошибка», которую я привел в начале подзаголовка, никак себя не проявляет, формула остается корректной).
Повторюсь, это для фиксированной размерности базового множества . Впрочем, уверен, с помощью метапрограммирования можно «научить» компилятор, чтобы он делал эту работу за вас.

Пример кода для индекса разбиения на 2, 3, 47

int get_split_2_3_47_index(int i1, int i2, int i3, int i4, int i5) { // Индекс сочетания по 2 из 52, умноженный на C(3, 50) int offset = ((52*51 - (51-i1)*(52-i1)) / 2 + (i2 - i1 - 1)) * 19600; // "Переиндексируем" внутреннюю группу так, чтобы была нумерация 0...49 if (i3 >= i1) --i3; if (i3 >= i2) --i3; if (i4 >= i1) --i4; if (i4 >= i2) --i4; if (i5 >= i1) --i5; if (i5 >= i2) --i5; // Теперь прибавим индекс сочетания по 3 // 0: // СУММА для n = 0 по i3-1 СОЧЕТАНИЙ (2, 49-n) // = СУММА для m = 50-i3 по 49 (m * (m-1) / 2) offset += (19600 - (((49-i3)*(50-i3)*(99-2*i3)) / 6 - ((49-i3)*(50-i3)) / 2) / 2); // 1: // СУММА для n = i3+1 по i4-1 СОЧЕТАНИЙ (1, 49-n) offset += (((48-i3)*(49-i3) - (49-i4)*(50-i4)) / 2); // 2: // СУММА для n = i4+1 по i5-1 (1) offset += (i5 - i4 - 1); return offset; }

Послесловие

Мне в своем симуляторе покера (Texas Hold"em) захотелось заранее рассчитать и хранить вероятности выигрыша для всех возможных сочетаний из моих ручных карт (2 штуки) и всех карт флопа (3 карты на столе). Это соответствует разбиению 52-множества на 2, 3, 47 подмножества.
Рассчитал и сохранил.
Но когда пришло время прочитать данные из файла для конкретной комбинации, уж очень мне не хотелось что-то там долго вычислять или производить поиск в гигабайтном файле. Теперь я просто определяю смещение в файле и считываю непосредственно то, что мне надо.

Вообще, комбинаторные алгоритмы я бы разбил на такие классы:

• Генерация комбинаторных объектов в едином цикле (тут все просто, примеры я привел);
• Переход к следующему (или предыдущему) комбинаторному объекту, зная предыдущий (своего рода forward/backward iterator, выражаясь в терминах C++) - тут можно отметить учебное пособие Т. И. Федоряевой, где приводится алгоритм константной временной сложности для перестановок, да и другие примеры в рунете можно найти, но только для перестановок - а было бы интересно увидеть аналогичные алгоритмы и для других комбинаторных объектов;
• Нахождение индекса объекта. Тут примеров совсем нет, исключая пособие Федоряевой, причем линейной сложности и только для перестановки;
• Нахождение объекта по индексу.

Было бы интересно получить справочник по комбинаторным алгоритмам для всех комбинаторных объектов, включая, перестановки, сочетания, размещения, разбиения на подмножества, сочетания с повторениями, размещения с повторениями.