Как найти количество возможных вариантов. Сочетания с повторениями элементов

На первом месте в ряду может стоять любой из N элементов, следовательно, получается N вариантов. На втором месте - любой, кроме того, который уже был использован для первого места. Следовательно, для каждого из N уже найденных вариантов есть (N - 1) вариантов второго места, и общее количество комбинаций становится N*(N - 1).
Это же можно повторить для остальных элементов ряда. Для самого последнего места остается только один вариант - последний оставшийся элемент. Для предпоследнего - два варианта, и так далее.
Следовательно, для ряда из N неповторяющихся элементов возможных перестановок равно произведению всех целых от 1 до N. Это произведение называется N и N! (читается «эн факториал»).

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

Чтобы найти количество размещений по M элементов из N, можно прибегнуть к такому же способу рассуждений, как и в случае с перестановками. На первом месте здесь по-прежнему может стоять N элементов, на втором (N - 1), и так далее. Но для последнего места количество возможных вариантов равняется не единице, а (N - M + 1), поскольку, когда размещение будет закончено, останется еще (N - M) неиспользованных элементов.
Таким образом, число размещений по M элементов из N равняется произведению всех целых чисел от (N - M + 1) до N, или, что то же самое, частному N!/(N - M)!.

Очевидно, что количество сочетаний по M элементов из N будет меньше количества размещений. Для каждого возможного сочетания есть M! возможных размещений, зависящих от порядка элементов этого сочетания. Следовательно, чтобы найти это количество, нужно разделить число размещений по M элементов из N на N!. Иными словами, количество сочетаний по M элементов из N равно N!/(M!*(N - M)!).

Источники:

• количество сочетаний

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

Вам понадобится

• калькулятор, компьютер

Инструкция

Чтобы посчитать факториал натурального числа перемножьте все , не превосходящие данное. Каждое число учитывается только один раз. В виде формулы это можно записать следующим образом:n! = 1*2*3*4*5*…*(n-2)*(n-1)*n, гдеn – натуральное число, факториал которого требуется посчитать.
0! принимается равным единице (0!=1).При возрастании аргумента значение факториала очень быстро увеличивается, поэтому обычный (бухгалтерский) уже для факториала 15-ти вместо результата может выдать об ошибке.

Чтобы посчитать факториал большого натурального числа, возьмите инженерный калькулятор. То есть, такой калькулятор на клавиатуре которого имеются обозначения математических функций (cos, sin, √). Наберите на калькуляторе исходное число, а затем нажмите кнопку вычисления факториала. Обычно такая кнопка как «n!» или аналогично (вместо «n» может стоять «N» или «х», но восклицательный знак «!» в обозначении факториала должен присутствовать в любом случае).
При больших значениях аргумента результаты вычислений начинают отображаться в «экспоненциальном» (показательном) виде. Так, например, факториал 50 будет представлен в форме: 3,0414093201713378043612608166065e+64 (или похожем). Чтобы получить результат вычислений в обычном виде, припишите к числу, показанному до символа «е», столько нулей, сколько указано после «е+» (если, конечно, хватит места).

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

Пример 1 Найдите все комбинации 3-х букв, взятых из набора в 5 букв {A, B, C, D, E}.

Решение Эти комбинации следующие:
{A, B, C}, {A, B, D},
{A, B, E}, {A, C, D},
{A, C, E}, {A, D, E},
{B, C, D}, {B, C, E},
{B, D, E}, {C, D, E}.
Существует 10 комбинаций из трех букв, выбранных из пяти букв.

Когда мы находим все комбинации из набора с 5 объектами, если мы берем 3 объекта за один раз, мы находим все 3-элементные подмножества. В таком случае порядок объектов не рассматривается. Тогда,
{A, C, B} называется одним и тем же набором как и {A, B, C}.

Подмножество
Множество A есть подмножеством B, и означает что A это подмножество и/или совпадает с B если каждый элемент A является элементом B.

Элементы подмножество не упорядочены. Когда рассматриваются комбинации, не рассматривается порядок!

Комбинация
Комбинация, содержащая k объектов является подмножеством, состоящим из k объектов.

Мы хотим записать формулу для вычисления число сочетаний из n объектов, если взято к объектов одновременно.

Обозначения комбинации
Число сочетаний из n объектов, если взято к объектов одновременно, обозначается n C k .

Мы называем n C k число сочетаний . Мы хотим записать общую формулу для n C k для любого k ≤ n. Во-первых, это верно, что n C n = 1, потому что множество с n элементами имеет только одно подмножестов с n элементами, есть само множество. Во-вторых, n C 1 = n, потому что множество с n элементами имеет только n подмножеств с 1 элементом в каждом. Наконец, n C 0 = 1, потому что множество с n элементами имеет только одно подмножество с 0 элементами, то есть пустое множество ∅. Чтобы рассмотреть другие сочетания, давайте вернемся к примеру 1 и сравним число комбинаций с числом перестановок.

Обратите внимание, что каждая комбинация из 3-х элементов имеет 6, или 3!, перестановок.
3! . 5 C 3 = 60 = 5 P 3 = 5 . 4 . 3,
so
.
В общем, число сочетаний из k элементов, выбранных из n объектов, n C k раз перестановок этих элементов k!, должно быть равно числу перестановок n элементов по k элементов:
k!. n C k = n P k
n C k = n P k /k!
n C k = (1/k!). n P k
n C k =

Комбинации k объектов из n объектов
Общее число комбинаций к элементов из n объектов обозначается n C k , определяется
(1) n C k = ,
или
(2) n C k =

Другой тип обозначения для n C k это биноминальный коэффициент . Причина для такой терминологии будет понятна ниже.

Биноминальный коэффициент

Пример 2 Вычислите , используя формулы (1) и (2).

Решение
a) Согласно (1),
.
b) Согласно (2),

Имейте в виду, что не означает n/k.

Пример 3 Вычислите и .

Решение Мы используем формулу (1) для первого выражения и формулу (2) для второго. Тогда
,
используя (1), и
,
испоьлзуя формулу (2).

Обратите внимание, что
,
и используя результат примера 2 дает нам
.
Отсюда вытекает, что число 5-ти элементного подмножества из множества 7 элементов то же самое, что и число 2-элементного подмножества множества из 7 элементов. Когда 5 элементов выбираются из набора, они не включают в себя 2 элемента. Чтобы увидеть это, рассмотрим множество {A, B, C, D, E, F, G}:


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

Подмножества размера k и размера
и n C k = n C n-k
Число подмножеств размера к множества с n объектами такое же, как и число подмножеств размера n - к. Число сочетаний k объектов из множества n объектов, такое же как и число сочетаний из n объектов, взятых одновременно.

Теперь мы будем решать задачи с комбинациями.

Пример 4 Мичиганская лотерея. Проводящаяся в штате Мичиган два раза в неделю лотерея WINFALL имеет джек-пот, который, по крайней мере, равен 2 млн. долларов США. За один доллар игрок может зачеркнуть любые 6 чисел от 1 до 49. Если эти числа совпадают с теми, которые выпадают при проведении лотереи, игрок выигрывает. (

Число сочетаний

Сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений .

Явные формулы

Число сочетаний из n по k равно биномиальному коэффициенту

При фиксированном значении n производящей функцией чисел сочетаний с повторениями из n по k является:

Двумерной производящей функцией чисел сочетаний с повторениями является:

Ссылки

• Р. Стенли Перечислительная комбинаторика. - М.: Мир, 1990.
• Вычисление числа сочетаний онлайн

Wikimedia Foundation . 2010 .

Смотреть что такое "Число сочетаний" в других словарях:

70 семьдесят 67 · 68 · 69 · 70 · 71 · 72 · 73 40 · 50 · 60 · 70 · 80 · 90 · 100 Факторизация: 2×5×7 Римская запись: LXX Двоичное: 100 0110 … Википедия

Световое число, условное число, однозначно выражающее внеш. условия при фотосъёмке (обычно яркость объекта съёмки и светочувствительность применяемого фотоматериала). Любому значению Э. ч. можно подобрать неск. сочетаний диафрагменное число… … Большой энциклопедический политехнический словарь

Форма числа, выделяющая два предмета как по отношению к единичному предмету, так и по отношению к множеству предметов. В современном русском языке эта форма не существует, но остатки ее влияния сохранились. Так, сочетания два стола (ср. мн. ч.… … Словарь лингвистических терминов

Комбинаторная математика, комбинаторика, раздел математики, посвященный решению задач выбора и расположения элементов нек рого, обычно конечного, множества в соответствии с заданными правилами. Каждое такое правило определяет способ построения… … Математическая энциклопедия

В комбинаторике сочетанием из по называется набор элементов, выбранных из данного множества, содержащего различных элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания… … Википедия

Занимается изучением событий, наступление которых достоверно неизвестно. Она позволяет судить о разумности ожидания наступления одних событий по сравнению с другими, хотя приписывание численных значений вероятностям событий часто бывает излишним… … Энциклопедия Кольера

1) то же, что математический Комбинаторный анализ. 2) Раздел элементарной математики, связанный с изучением количества комбинаций, подчинённых тем или иным условиям, которые можно составить из заданного конечного множества объектов… … Большая советская энциклопедия

- (греч. paradoxos неожиданный, странный) в широком смысле: утверждение, резко расходящееся с общепринятым, устоявшимся мнением, отрицание того, что представляется «безусловно правильным»; в более узком смысле два противоположных утверждения, для… … Философская энциклопедия

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

Математическая теория, занимающаяся определением числа различных способов распределения данных предметов в известном порядке; имеет особенно важное значение в теории уравнений и в теории вероятностей. Простейшие задачи этого рода заключаются в… … Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона

Книги

• Число судьбы. Гороскоп совместимости. Желания. Страсти. Фантазии (количество томов: 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$. Количество размещений без повторений из $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)$-выборка с повторениями.

Количество размещений с повторениями из $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)$-выборка без повторений.

По сути, перестановка без повторений есть частный случай размещения без повторений, когда объём выборки равен мощности исходного множества. Количество перестановок без повторений из $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)$-выборка без повторений.

Общее количество сочетаний без повторений из $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)$-выборка с повторениями.

Общее количество сочетаний с повторениями из $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.