ЧИСЛО СОЧЕТАНИЙ

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


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

ТРЕУГОЛЬНИК ПАСКАЛЯ
В 1653 году Блез Паскаль опубликовал "Трактат об арифметическом треугольнике". Этот треугольник был известен ещё в Древней Индии (X век). В XVI веке он был вновь открыт Штифелем.

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

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

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

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


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

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

.

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

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

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

.

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

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

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

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

.

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

.

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

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

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

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

.

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

.

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

.

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


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


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

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

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

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 

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

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 и возвращает его.

Допустим, нам нужно вывести в TextBox все сочетания из N по K. Создадим для этого рекурсивный алгоритм, который будет выглядеть так:
Пример 3

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<n чисел этого диапазона можно записать в векторной форме, располагая их в порядке возрастания значений слева направо:

.

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


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

.

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


Значение такого элемента следует увеличить на 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:

.

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


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


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


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


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

.

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


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


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

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

Пример 4
1 begin
2 for i := 1 to k do A[i] := i;
3 p := k;
4 while p 1 do
5 begin write(A[1], …, A[k]);
6 if A[k] = n then p := p 1 else p := k;
7 if p 1 then
8 for i := k downto p do A[i] := A[p] + i p + 1
9 end
10 end

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

В отличие от классического сочетания, где все элементы различны, сочетание с повторениями образует неупорядоченная выборка элементов конечного множества, где любой элемент может появляться неопределенно часто и присутствовать необязательно в единственном экземпляре. При этом количество повторений элементов обычно ограничено только длиной сочетания, а различными считаются сочетания, которые отличаются хотя бы одним элементом. Например, выбирая по 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-разрядного двоичного числа (Bn,…Bj,…B1), где m единичных разрядов обозначают элементы сочетания, а остальные (nm) разрядов имеют нулевые значения. Очевидно, что при такой форме записи различные сочетания должны отличаться расположением единичных разрядов и существует всего C(n,m) способов расположить m единиц или (nm) нулей в n-разрядном двоичном наборе. Например, в следующей таблице перечислены все 6 таких бинарных сочетаний, которые обеспечивают запись 4-х разрядными двоичными числами всех сочетаний из 4-х элементов произвольного множества {E1,E2,E3,E4} по 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), можно всегда получить из текущего сочетания (Bn,…Bj,…B1), выполнив операции сложения целых чисел по следующей аддитивной формуле:


В этой аддитивной формуле, показатели степеней двоек 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.