В комбинаторике изучают вопросы о том, сколько комбинаций определенного типа можно составить из данных предметов (элементов).
Рождение комбинаторики как раздела связано с трудами Б. Паскаля и П. Ферма по теории азартных игр. Большой вклад в развитие комбинаторных методов внесли Г.В. Лейбниц, Я. Бернулли и Л. Эйлер.
Французский философ, писатель, математик и физик Блез Паскаль (1623–1662) рано проявил свои выдающиеся математические способности. Круг математических интересов Паскаля был весьма разнообразен. Паскаль доказал одну
из основных теорем проективной геометрии (теорема Паскаля), сконструировал суммирующую машину (арифмометр Паскаля), дал способ вычисления биномиальных коэффициентов (треугольник Паскаля), впервые точно определил и применил для доказательства метод математической индукции, сделал существенный шаг в развитии анализа бесконечно малых, сыграл важную роль в зарождении теории вероятности. В гидростатике Паскаль установил ее основной закон (закон Паскаля). “Письма к провинциалу” Паскаля явились шедевром французской классической прозы.
Готфрид Вильгельм Лейбниц (1646–1716) — немецкий философ, математик, физик и изобретатель, юрист, историк, языковед. В математике наряду с И. Ньютоном разработал дифференциальное и интегральное исчисление. Важный вклад внес в комбинаторику. С его именем, в частности, связаны теоретико-числовые задачи.
Готфрид Вильгельм Лейбниц имел мало внушительную внешность и поэтому производил впечатление довольно невзрачного человека. Однажды в Париже он зашел в книжную лавку в надежде приобрести книгу своего знакомого философа. На вопрос посетителя об этой книге книготорговец, осмотрев его с головы до ног, насмешливо бросил: “Зачем она вам? Неужели вы способны читать такие книги?” Не успел ученый ответить, как в лавку вошел сам автор книги со словами: “Великому Лейбницу привет и уважение!” Продавец никак не мог взять втолк, что перед ним действительно знаменитый Лейбниц, книги которого пользовались большим спросом среди ученых.
В дальнейшем важную роль будет играть следующая
Лемма. Пусть в множестве элементов, а в множестве — элементов. Тогда число всех различных пар , где будет равно .
Доказательство. Действительно, с одним элементом из множества мы можем составить таких различных пар, а всего в множестве элементов.
Размещения, перестановки, сочетания
Пусть у нас есть множество из трех элементов . Какими способами мы можем выбрать из этих элементов два? .
Определение. Размещениями множества из различных элементов по элементов называются комбинации, которые составлены из данных элементов по > элементов и отличаются либо самими элементами, либо порядком элементов.
Число всех размещений множества из элементов по элементов обозначается через (от начальной буквы французского слова “arrangement”, что означает размещение), где и .
Теорема. Число размещений множества из элементов по элементов равно
Доказательство. Пусть у нас есть элементы . Пусть — возможные размещения. Будем строить эти размещения последовательно. Сначала определим — первый элемент размещения. Из данной совокупности элементов его можно выбрать различными способами. После выбора первого элемента для второго элемента остается способов выбора и т.д. Так как каждый такой выбор дает новое размещение, то все эти выборы можно свободно комбинировать между собой. Поэтому имеем:
Пример. Сколькими способами можно составить флаг, состоящий из трех горизонтальных полос различных цветов, если имеется материал пяти цветов?
Решение. Искомое число трехполосных флагов:
Определение. Перестановкой множества из элементов называется расположение элементов в определенном порядке.
Так, все различные перестановки множества из трех элементов — это
Число всех перестановок из элементов обозначается (от начальной буквы французского слова “permutation”, что значит “перестановка”, “перемещение”). Следовательно, число всех различных перестановок вычисляется по формуле
Пример. Сколькими способами можно расставить ладей на шахматной доске так, чтобы они не били друг друга?
Решение. Искомое число расстановки ладей
По определению!
Определение. Сочетаниями из различных элементов по элементов называются комбинации, которые составлены из данных элементов по элементов и отличаются хотя бы одним элементом (иначе говоря, -элементные подмножества данного множества из элементов).
Как видим, в сочетаниях в отличие от размещений не учитывается порядок элементов. Число всех сочетаний из элементов по элементов в каждом обозначается (от начальной буквы французского слова “combinasion”, что значит “сочетание”).
Числа
Все сочетания из множества по два — .
Свойства чисел {\sf C}_n^k
Действительно, каждому -элементному подмножеству данного -элементного множества соответствует одно и только одно -элементное подмножество того же множества.
Действительно, мы можем выбирать подмножества из элементов следующим образом: фиксируем один элемент; число -элементных подмножеств, содержащих этот элемент, равно ; число -элементных подмножеств, не содержащих этот элемент, равно .
Треугольник Паскаля
В этом треугольнике крайние числа в каждой строке равны 1, а каждое не крайнее число равно сумме двух чисел предыдущей строки, стоящих над ним. Таким образом, этот треугольник позволяет вычислять числа .
Теорема.
Доказательство.
Рассмотрим множество из элементов и решим двумя способами следующую задачу: сколько можно составить последовательностей из элементов данного
множества, в каждой из которых никакой элемент не встречается дважды?
1 способ. Выбираем первый член последовательности, затем второй, третий и т.д. член
2 способ. Выберем сначала элементов из данного множества, а затем расположим их в некотором порядке
Домножим числитель и знаменатель этой дроби на :
Пример. Сколькими способами можно в игре “Спортлото” выбрать 5 номеров из 36?
Искомое число способов
Задачи.
1.
Номера машин состоят из 3 букв русского алфавита (33 буквы) и 4 цифр. Сколько существует различных номеров автомашин?
2.
На рояле 88 клавиш. Сколькими способами можно извлечь последовательно 6 звуков?
3.
Сколько есть шестизначных чисел, делящихся на 5?
4.
Сколькими способами можно разложить 7 разных монет в три кармана?
5.
Сколько можно составить пятизначных чисел, в десятичной записи которых хотя бы один раз встречается цифра 5?
6.
Сколькими способами можно усадить 20 человек за круглым столом, считая способы одинаковыми, если их можно получить один из другого движением по кругу?
7.
Сколько есть пятизначных чисел, делящихся на 5, в записи которых нет одинаковых цифр?
8.
На клетчатой бумаге со стороной клетки 1 см нарисована окружность радиуса 100 см, не проходящая через вершины клеток и не касающаяся сторон клеток. Сколько клеток может пересекать эта окружность?
9.
Сколькими способами можно расставить в ряд числа так, чтобы числа стояли рядом и притом шли в порядке возрастания?
10.
Сколько пятизначных чисел можно составить из цифр , если каждую цифру можно использовать только один раз?
11.
Из слова РОТ перестановкой букв можно получить еще такие слова: ТОР, ОРТ, ОТР, ТРО, РТО. Их называют анаграммами. Сколько анаграмм можно составить из слова ЛОГАРИФМ?
12.
Назовем разбиением
натурального числа представление его в виде суммы натуральных чисел. Вот, например, все разбиения числа :
Разбиения считаются разными, если они отличаются либо числами, либо порядком слагаемых.
Сколько существует различных разбиений числа на слагаемых?
13.
Сколько существует трехзначных чисел с невозрастающим порядком цифр?
14.
Сколько существует четырехзначных чисел с невозрастающим порядком цифр?
15.
Сколькими способами можно рассадить в ряд 17 человек, чтобы и оказались рядом?
16.
девочек и мальчиков рассаживаются произвольным образом в ряду из мест. Сколькими способами можно их рассадить так, чтобы никакие две девочки не сидели рядом?
17.
девочек и мальчиков рассаживаются произвольным образом в ряду из мест. Сколькими способами можно их рассадить так, чтобы все девочки сидели рядом?
Рассмотрим задачу подсчета числа выборок из данного множества в общем виде. Пусть имеется некоторое множество 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. Чтобы в материале было легче ориентироваться, добавлю содержание данной темы: В этой теме рассмотрим основные понятия комбинаторики: перестановки, сочетания и размещения. Выясним их суть и формулы, по которым можно найти их количество. Для работы нам понадобятся кое-какие вспомогательные сведения. Начнём с такого фундаментального математического понятия как множество. Подробно понятие множества было раскрыто в теме "Понятие множества. Способы задания множеств" . Очень краткий рассказ про множества
: показать\скрыть Если вкратце: множеством именуют некую совокупность объектов. Записывают множества в фигурных скобках. Порядок записи элементов роли не играет; повторения элементов не допускаются. Например, множество цифр числа 11115555999 будет таким: $\{1,5,9 \}$. Множество согласных букв в слове "тигрёнок" таково: $\{т, г, р, н, к\}$. Запись $5\in A$ означает, что элемент 5 принадлежит множеству $A=\{1,5,9 \}$. Количество элементов в конечном множестве называют мощностью
этого множества и обозначают $|A|$. Например, для множества $A=\{1,5,9 \}$, содержащего 3 элемента, имеем: $|A|=3$. Рассмотрим некое непустое конечное множество $U$, мощность которого равна $n$, $|U|=n$ (т.е. в множестве $U$ имеется $n$ элементов). Введём такое понятие, как выборка
(некоторые авторы именуют её кортежем). Под выборкой объема $k$ из $n$ элементов (сокращённо $(n,k)$-выборкой) будем понимать набор элементов $(a_1, a_2,\ldots, a_k)$, где $a_i\in U$. Выборка называется упорядоченной, если в ней задан порядок следования элементов. Две упорядоченные выборки, различающиеся лишь порядком элементов, являются различными. Если порядок следования элементов выборки не является существенным, то выборку именуют неупорядоченной. Заметьте, что в определении выборки ничего не сказано про повторения элементов. В отличие от элементов множеств, элементы выборки могут повторяться. Для примера рассмотрим множество $U=\{a,b,c,d,e\}$. Множество $U$ содержит 5 элементов, т.е. $|U|=5$. Выборка без повторений может быть такой: $(a,b,c)$. Данная выборка содержит 3 элемента, т.е. объём этой выборки равен 3. Иными словами, это $(5,3)$-выборка. Выборка с повторениями может быть такой: $(a,a,a,a,a,c,c,d)$. Она содержит 8 элементов, т.е. объём её равен 8. Иными словами, это $(5,8)$-выборка. Рассмотрим ещё две $(5,3)$-выборки: $(a,b,b)$ и $(b,a,b)$. Если мы полагаем наши выборки неупорядоченными, то выборка $(a,b,b)$ равна выборке $(b,a,b)$, т.е. $(a,b,b)=(b,a,b)$. Если мы полагаем наши выборки упорядоченными, то $(a,b,b)\neq(b,a,b)$. Рассмотрим ещё один пример, немного менее абстрактный:) Предположим, в корзине лежат шесть конфет, причём все они различны. Если первой конфете поставить в соответствие цифру 1, второй конфете - цифру 2 и так далее, то с конфетами в корзине можно сопоставить такое множество: $U=\{1,2,3,4,5,6\}$. Представьте, что мы наугад запускаем руку в корзинку с целью вытащить три конфеты. Вытащенные конфеты - это и есть выборка. Так как мы вытаскиваем 3 конфеты из 6, то получаем (6,3)-выборку. Порядок расположения конфет в ладони совершенно несущественен, поэтому эта выборка является неупорядоченной. Ну, и так как все конфеты различны, то выборка без повторений. Итак, в данной ситуации говорим о неупорядоченной (6,3)-выборке без повторений. Теперь подойдём с иной стороны. Представим себе, что мы находимся на фабрике по производству конфет, и на этой фабрике производятся конфеты четырёх сортов. Множество $U$ в этой ситуации таково: $U=\{1,2,3,4 \}$ (каждая цифра отвечает за свой сорт конфет). Теперь вообразим, что все конфеты ссыпаются в единый жёлоб, около которого мы и стоим. И, подставив ладони, из этого потока отбираем 20 конфет. Конфеты в горсти – это и есть выборка. Играет ли роль порядок расположения конфет в горсти? Естественно, нет, поэтому выборка неупорядоченная. Всего 4 сорта конфет, а мы отбираем двадцать штук из общего потока - повторения сортов неизбежны. При этом выборки могут быть самыми различными: у нас даже могут оказаться все конфеты одного сорта. Следовательно, в этой ситуации мы имеем дело с неупорядоченной (4,20)-выборкой с повторениями. Рассмотрим ещё пару примеров. Пусть на кубиках написаны различные 7 букв: к, о, н, ф, е, т, а. Эти буквы образуют множество $U=\{к,о,н,ф,е,т,а\}$. Допустим, из данных кубиков мы хотим составить "слова" из 5 букв. Буквы этих слов (к примеру, «конфе», «тенко» и так далее) образуют (7,5)-выборки: $(к,о,н,ф,е)$, $(т,е,н,к,о)$ и т.д. Очевидно, что порядок следования букв в такой выборке важен. Например, слова «нокфт» и «кфтон» различны (хотя состоят из одних и тех же букв), ибо в них не совпадает порядок букв. Повторений букв в таких «словах» нет, ибо в наличии только семь кубиков. Итак, набор букв каждого слова представляет собой упорядоченную (7,5)-выборку без повторений. Еще один пример: мы составляем всевозможные восьмизначные числа из четырёх цифр 1, 5, 7, 8. Например, 11111111, 15518877, 88881111 и так далее. Множество $U$ таково: $U=\{1,5,7,8\}$. Цифры каждого составленного числа образуют (4,8)-выборку. Порядок следования цифр в числе важен, т.е. выборка упорядоченная. Повторения допускаются, поэтому здесь мы имеем дело с упорядоченной (4,8)-выборкой с повторениями. Размещение без повторений из $n$ элементов по $k$ - упорядоченная $(n,k)$-выборка без повторений. Так как элементы в рассматриваемой выборке повторяться не могут, то мы не можем отобрать в выборку больше элементов, чем есть в исходном множестве. Следовательно, для таких выборок верно неравенство: $n≥ k$. Количество размещений без повторений из $n$ элементов по $k$ определяется следующей формулой:
\begin{equation}A_{n}^{k}=\frac{n!}{(n-k)!}
\end{equation}
Что обозначает знак "!"?
: показать\скрыть Запись "n!" (читается "эн факториал") обозначает произведение всех чисел от 1 до n, т.е.
$$
n!=1\cdot2\cdot 3\cdot \ldots\cdot n
$$
По определению полагается, что $0!=1!=1$. Для примера найдём 5!:
$$
5!=1\cdot 2\cdot 3\cdot 4\cdot 5=120.
$$ Пример №1 Алфавит состоит из множества символов $E=\{+,*,0,1,f\}$. Определим количество таких трёхсимвольных слов в этом алфавите, которые не содержат повторяющихся букв. Под трёхсимвольными словами будем понимать выражения вида "+*0" или "0f1". В множестве $E$ пять элементов, поэтому буквы трехсимвольных слов образуют (5,3)-выборки. Первый вопрос: эти выборки упорядочены или нет? Слова, которые отличаются лишь порядком букв, полагаются различными, поэтому порядок элементов в выборке важен. Значит, выборка является упорядоченной. Второй вопрос: допускаются повторения или нет? Ответ на этот вопрос даёт условие: слова не должны содержать повторяющихся букв. Подводим итоги: буквы каждого слова, удовлетворяющего условию задачи, образуют упорядоченную (5,3)-выборку без повторений. Иными словами, буквы каждого слова образуют размещение без повторений из 5 элементов по 3. Вот примеры таких размещений:
$$
(+,*,f), \; (*,+,f), \; (1,+,0)
$$
Нас же интересует общее количество этих размещений. Согласно формуле (1) количество размещений без повторений из 5 элементов по 3 будет таким:
$$
A_{5}^{3}=\frac{5!}{(5-3)!}=\frac{5!}{2!}=60.
$$
Т.е. можно составить 60 трёхсимвольных слов, буквы которых не будут повторяться. Ответ
: 60. Размещение с повторениями из $n$ элементов по $k$ - упорядоченная $(n,k)$-выборка с повторениями. Количество размещений с повторениями из $n$ элементов по $k$ определяется следующей формулой:
\begin{equation}\bar{A}_{n}^{k}=n^k
\end{equation}
Пример №2 Сколько пятизначных чисел можно составить из множества цифр $\{5,7,2\}$? Из данного набора цифр можно составить пятизначные числа 55555, 75222 и так далее. Цифры каждого такого числа образуют (3,5)-выборку: $(5,5,5,5,5)$, $(7,5,2,2,2)$. Зададимся вопросом: что это за выборки? Во-первых, цифры в числах могут повторяться, поэтому мы имеем дело с выборками с повторениями. Во-вторых, порядок расположения цифр в числе важен. Например, 27755 и 77255 - разные числа. Следовательно, мы имеем дело с упорядоченными (3,5)-выборками с повторениями. Общее количество таких выборок (т.е. общее количество искомых пятизначных чисел) найдём с помощью формулы (2):
$$
\bar{A}_{3}^{5}=3^5=243.
$$
Следовательно, из заданных цифр можно составить 243 пятизначных числа. Ответ
: 243. Перестановка без повторений из $n$ элементов - упорядоченная $(n,n)$-выборка без повторений. По сути, перестановка без повторений есть частный случай размещения без повторений, когда объём выборки равен мощности исходного множества. Количество перестановок без повторений из $n$ элементов определяется следующей формулой:
\begin{equation}P_{n}=n!
\end{equation}
Эту формулу, кстати, легко получить, если учесть, что $P_n=A_{n}^{n}$. Тогда получим:
$$
P_n=A_{n}^{n}=\frac{n!}{(n-n)!}=\frac{n!}{0!}=\frac{n!}{1}=n!
$$
Пример №3 В морозилке лежат пять порций мороженого от различных фирм. Сколькими способами можно выбрать порядок их съедения? Пусть первому мороженому соответствует цифра 1, второму - цифра 2 и так далее. Мы получим множество $U=\{1,2,3,4,5\}$, которое будет представлять содержимое морозилки. Порядок съедения может быть таким: $(2,1,3,5,4)$ или таким: $(5,4,3,1,2)$. Каждый подобный набор есть (5,5)-выборка. Она будет упорядоченной и без повторений. Иными словами, каждая такая выборка есть перестановка из 5 элементов исходного множества. Согласно формуле (3) общее количество этих перестановок таково:
$$
P_5=5!=120.
$$
Следовательно, существует 120 порядков выбора очередности съедения. Ответ
: 120. Перестановка с повторениями – упорядоченная $(n,k)$-выборка с повторениями, в которой элемент $a_1$ повторяется $k_1$ раз, $a_2$ повторяется $k_2$ раза так далее, до последнего элемента $a_r$, который повторяется $k_r$ раз. При этом $k_1+k_2+\ldots+k_r=k$. Общее количество перестановок с повторениями определяется формулой:
\begin{equation}P_{k}(k_1,k_2,\ldots,k_r)=\frac{k!}{k_1!\cdot k_2!\cdot \ldots \cdot k_r!}
\end{equation}
Пример №4 Слова составляются на основе алфавита $U=\{a,b,d\}$. Сколько различных слов из семи символов может быть составлено, если в этих словах буква "a" должна повторяться 2 раза; буква "b" - 1 раз, а буква "d" - 4 раза? Вот примеры искомых слов: "aabdddd", "daddabd" и так далее. Буквы каждого слова образуют (3,7)-выборку с повторениями: $(a,a,b,d,d,d,d)$, $(d,a,d,d,a,b,d)$ и т.д. Каждая такая выборка состоит из двух элементов "a", одного элемента "b" и четырёх элементов "d". Иными словами, $k_1=2$, $k_2=1$, $k_3=4$. Общее количество повторений всех символов, естественно, равно объёму выборки, т.е. $k=k_1+k_2+k_3=7$. Подставляя эти данные в формулу (4), будем иметь:
$$
P_7(2,1,4)=\frac{7!}{2!\cdot 1!\cdot 4!}=105.
$$
Следовательно, общее количество искомых слов равно 105. Ответ
: 105. Сочетание без повторений из $n$ элементов по $k$ – неупорядоченная $(n,k)$-выборка без повторений. Общее количество сочетаний без повторений из $n$ элементов по $k$ определяется формулой:
\begin{equation}C_{n}^{k}=\frac{n!}{(n-k)!\cdot k!}
\end{equation}
Пример №5 В корзине размещены карточки, на которых написаны целые числа от 1 до 10. Из корзины вынимают 4 карточки и суммируют числа, написанные на них. Сколько различных наборов карточек можно вытащить из корзины? Итак, в данной задаче исходное множество таково: $U=\{1,2,3,4,5,6,7,8,9,10\}$. Из этого множества мы выбираем четыре элемента (т.е., четыре карточки из корзины). Номера вытащенных элементов образуют (10,4)-выборку. Повторения в этой выборке не допускаются, так как номера всех карточек различны. Вопрос вот в чём: порядок выбора карточек играет роль или нет? Т.е., к примеру, равны ли выборки $(1,2,7,10)$ и $(10,2,1,7)$ или не равны? Тут нужно обратиться к условию задачи. Карточки вынимаются для того, чтобы потом найти сумму элементов. А это значит, что порядок карточек не важен, так как от перемены мест слагаемых сумма не изменится. Например, выборке $(1,2,7,10)$ и выборке $(10,2,1,7)$ будет соответствовать одно и то же число $1+2+7+10=10+2+1+7=20$. Вывод: из условия задачи следует, что мы имеем дело с неупорядоченными выборками. Т.е. нам нужно найти общее количество неупорядоченных (10,4)-выборок без повторений. Иными словами, нам нужно найти количество сочетаний из 10 элементов по 4. Используем для этого формулу (5):
$$
C_{10}^{4}=\frac{10!}{(10-4)!\cdot 4!}=\frac{10!}{6!\cdot 4!}=210.
$$
Следовательно, общее количество искомых наборов равно 210. Ответ
: 210. Сочетание с повторениями из $n$ элементов по $k$ – неупорядоченная $(n,k)$-выборка с повторениями. Общее количество сочетаний с повторениями из $n$ элементов по $k$ определяется формулой:
\begin{equation}\bar{C}_{n}^{k}=\frac{(n+k-1)!}{(n-1)!\cdot k!}
\end{equation}
Пример №6 Представьте себе, что мы находимся на конфетном заводе, - прямо возле конвейера, по которому движутся конфеты четырёх сортов. Мы запускаем руки в этот поток и вытаскиваем двадцать штук. Сколько всего различных "конфетных комбинаций" может оказаться в горсти? Если принять, что первому сорту соответствует число 1, второму сорту - число 2 и так далее, то исходное множество в нашей задаче таково: $U=\{1,2,3,4\}$. Из этого множества мы выбираем 20 элементов (т.е., те самые 20 конфет с конвейера). Пригоршня конфет образует (4,20)-выборку. Естественно, повторения сортов будут. Вопрос в том, играет роль порядок расположения элементов в выборке или нет? Из условия задачи следует, что порядок расположения элементов роли не играет. Нам нет разницы, будут ли в горсти располагаться сначала 15 леденцов, а потом 4 шоколадных конфеты, или сначала 4 шоколадных конфеты, а уж потом 15 леденцов. Итак, мы имеем дело с неупорядоченной (4,20) выборкой с повторениями. Чтобы найти общее количество этих выборок используем формулу (6):
$$
\bar{C}_{4}^{20}=\frac{(4+20-1)!}{(4-1)!\cdot 20!}=\frac{23!}{3!\cdot 20!}=1771.
$$
Следовательно, общее количество искомых комбинаций равно 1771. Введение. Множества и выборки.
Размещения без повторений из $n$ элементов по $k$
Размещения с повторениями из $n$ элементов по $k$
Перестановки без повторений из $n$ элементов
Перестановки с повторениями
Сочетания без повторений из $n$ элементов по $k$
Сочетания с повторениями из $n$ элементов по $k$
