63

Глава 3. Простейшие комбинаторные объекты (конструкции)

3.1. Определяющие требования (правила составления)

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

Такие ситуации, имеющие место в самых различных комбинаторных задачах, можно описать следующим образом: дана некоторая совокупность предметов), относящихся к n различным видам, т.е. определено n–элементное множество An предметов. Из этих предметов составляют (формируют) всевозможные k–расстановки (конструкции, комбинации, конфигурации) по k предметов в каждой; в зависимости от характерных (отличительных) свойств этих конструкций (к таким свойствам относятся прежде всего состав и порядок предметов в расстановке), правил их составления (выбора, формирования) получаются различные множества расстановок - комбинаторных объектов; необходимо найти общее число (мощность множества) расстановок.

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

1. Размещения без повторений (определяющие требования):

каждая комбинация (конструкция), формируемая из объектов заданного n-элементного множества A содержит k предметов разных видов (различных элементов множества A), т.е. в нее не могут входить предметы одного вида (например, одинаковые буквы алфавита, с помощью которого составляются слова-кортежи букв);

две комбинации (k–расстановки) считаются различными, если они отличаются либо составом, либо порядком входящих в них предметов (либо и составом, и порядком следования предметов одновременно).

Конструкции, удовлетворяющие сформулированным требованиям (свойствам), из которых вытекают и правила их составления (выбора), принято называть k–размещениями без повторений из элементов n видов (или просто размещениями из n по k ).

Так, если A – множество десятичных цифр A = { 0,1,2,3,4,5,6,7,8,9 }, то комбинации (расстановки) десятичных цифр 1234, 4321, 2453 представляют, очевидно, различные размещения без повторений из 10 по 4, чего нельзя сказать про комбинации 9759, 4664, 5551, каждая из которых содержит одинаковые (повторяющиеся) цифры (элементы множества А) и, как следствие, не удовлетворяет первому требованию.

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

. ( 3.1 )

Обоснование (интерпретация) равенства (3.1). Процесс составления k–размещений без повторений можно рассматривать как последовательный (пошаговый) выбор без возвращения k предметов из корзины (коробки), в которой сложены все n предметов разных видов:

на первом шаге выбирается первый предмет k–расстановки, что

можно осуществить n способами;

так как выбранный предмет обратно не возвращается, то на втором шаге выбирается любой предмет из (n–1)-го оставшихся, такой выбор можно осуществить (n–1)-м способом;

третий шаг сводится к произвольному выбору предмета из (n–2)-х оставшихся, на четвертом – из (n–3)-х оставшихся и т.д.;

на последнем k-м шаге выбор производится из (n – k + 1) оставшихся предметов и, таким образом, после k шагов в корзине остается (n–k) предметов.

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

Две типовые комбинаторные задачи, решение которых сводится к вычислению числа размещений без повторений, рассмотрены в примере 3.1.

2. Размещения с повторениями (определяющие требования):

в любую k–расстановку из n элементов множества A могут входить предметы одного вида (например, одинаковые буквы алфавита), т.е. элементы множества A в расстановке могут повторяться;

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

Расстановки, удовлетворяющие сформулированным требованиям (условиям), обычно называют k–размещениями с повторениями из элементов n видов (или просто размещениями с повторениями из n по k ).

Так, в примере с десятичными цифрами (см. выше ) последние три комбинации 9759, 4664, 5551 представляют размещения с повторениями из 10 по 4.

Общее число различных расстановок (число размещений с повторениями из n элементов по k ), которое обозначим через , можно найти (вычислить) с помощью равенства (формулы)

. ( 3.2 )

Обоснование (интерпретация) равенства ( 3.2 ). Задача нахождения величины эквивалентна задаче нахождения мощности декартовой степени .

Действительно, если предметы различных видов интерпретировать как буквы алфавита а составляемые из этих предметов k–расстановки – как различные слова-кортежи длиной k, то в соответствии с принципом взаимно однозначного соответствия между словами и кортежами декартовой степени, обоснованность применения которого в данном случае очевидна, искомое число размещений с повторениями из n по k будет совпадать с мощностью декартовой степени, т.е. удовлетворять (3.2).

Процесс составления k–размещений с повторениями можно также (как это было сделано для размещений без повторений) интерпретировать как последовательный (пошаговый) выбор с возвращением k предметов из корзины (коробки), содержащей все n предметов разных видов. Данный процесс (по сравнению с процессом составления размещений без повторений) отличается тем, что выбираемый произвольным образом на каждом i-м (i = 1,2,...,k ) шаге предмет возвращается обратно, т.е. условия выбора не меняются (число предметов в корзине остается постоянным).

Следовательно, выбор предмета на любом текущем шаге можно осуществить n способами, что подтверждает правомерность равенства

( 3.2 ) для общего числа размещений с повторениями (см. пример 3.2).

3. Перестановки без повторений (определяющие требования):

каждая расстановка содержит все n предметов разных видов (все элементы множества A), т.е. расстановки имеют одинаковый состав элементов и фактически являются n–расстановками;

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

Расстановки, удовлетворяющие сформулированным требованиям (свойствам), называются перестановками без повторений (или просто перестановками) из n элементов (предметов).

Как следует из требований, перестановки являются частным случаем размещений без повторений из n элементов по k, когда в размещения входят все элементы, т.е. когда k = n. Если обозначить общее число перестановок через , то в соответствии с выражением (3.1) это число будет удовлетворять равенству

Таким образом, нахождение общего числа перестановок из n элементов (предметов, объектов) сводится к перемножению всех натуральных чисел от 1 до n. Это произведение, как правило, обозначают n! (читается “n-факториал” ). Итак,

( 3.3 )

Для расчета факториала по формуле (3.3) можно также использовать следующее очевидное рекуррентное соотношение

справедливое при n > 1. Для того чтобы это соотношение выполнялось при n = 1, полагают 0! = 1.

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

.

В примере 3.3, посвященном перестановкам без повторений, разобрана хорошо известная (классическая) задача о ладьях [1] и ее обобщение (распространение) на задачу о полном разложении (развертывании) определителя n-го порядка.

4. Перестановки с повторениями (определяющие требования) :

каждая расстановка содержит все n различных предметов (элементов множества A ), т.е. расстановки имеют одинаковый состав элементов и являются n–расстановками;

любой предмет, входящий в расстановку, обладает одним из k уникальных свойств (принадлежит одному из k типов предметов);

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

Расстановки, удовлетворяющие сформулированным требованиям, называются перестановками с повторениями из n элементов (предметов).

Общее число различных перестановок, которое обычно обозначают

Р ( m,l,…,s ), может быть найдено с помощью равенства

( 3.4 )

где n! - число n–расстановок, составляемых без учета принадлежности

предметов разным типам (число перестановок без повторений);

- число предметов 1-го типа;

- число предметов 2-го типа;

……………………………………….

- число предметов k-го типа.

Основное отличие перестановок с повторениями от других комбинаторных объектов заключается в том, что n-элементное множество A различных предметов, из которого составляются расстановки, представляет собой некоторое разбиение на классы; при этом предметы, входящие в каждый конкретный класс, считаются однотипными, т.е. с точки зрения свойства (признака), которым они обладают, предметы совпадают (равны).

Обоснование (интерпретация) формулы (3.4). Для решения задачи нахождения искомого числа перестановок запишем одну из них, например, перестановку П вида

П = aa…a bb…b … hh…h , ( 3.5 )

в которой сначала выписаны (обозначенные буквой a) все m элементов (предметов) 1-го типа, затем (обозначенные буквой b) все l элементов 2-го типа и т.д., наконец (обозначенные буквой h ) все s элементов k-го типа.

Записанная перестановка П отражает один из возможных вариантов расположения входящих в нее элементов.

Ясно, что элементы 1-го типа можно переставлять друг с другом m! способами. Такие перестановки ничего не меняют, т.е. вид (3.5) перестановки П остается старым. Точно так же ничего не меняют l! перестановок элементов 2-го типа, ... , s! перестановок элементов k-го типа.

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

Таким образом, полное множество всевозможных перестановок из n элементов, мощность которого равна n!, распадается на непересекающиеся подмножества (классы), при этом каждое из подмножеств соответствует одному из вариантов расположения элементов в перестановке П и состоит из N одинаковых перестановок, не меняющих этот вариант.

Количество подмножеств (разных вариантов) будет, очевидно, совпадать с искомым числом перестановок с повторениями и равно , что подтверждает справедливость формулы (3.4). Одна из комбинаторных задач, сводящаяся к подсчету числа перестановок с повторениями рассмотрена в примере 3.4.

5. Сочетания (определяющие требования) :

каждая расстановка из n элементов множества A содержит k предметов разных видов (различных элементов множества A ), т.е. в нее не могут входить предметы одного вида (например, одинаковые буквы алфавита);

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

Расстановки, удовлетворяющие сформулированным требованиям (условиям), называются k–сочетаниями из элементов n видов (или просто сочетаниями из n по k ).

Общее число различных расстановок (число сочетаний из n элементов по k) будет равно

. (3.6 )

Обоснование (интерпретация)  равенства (3.6). Сравнение свойств (правил составления) сочетаний и размещений (без повторений) показывает: k–сочетания отличаются от k–размещений только тем, что в сочетаниях порядок предметов несущественен, т.е. все размещения, имеющие одинаковый состав и разный порядок элементов, определяют одно сочетание.

Так как число k–размещений с одним и тем же составом элементов равно k!, т.е. совпадает с числом перестановок из k элементов, то для общего числа k–сочетаний будет справедливо (связывающее с числом k–размещений без повторений) выражение

. ( 3.7 )

В этом легко убедиться, если умножить числитель и знаменатель в (3.7) на (n-k)!). В результате получим равенство (3.6).

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

Общая формулировка задачи на извлечение предметов:

Пусть имеется k ящиков ( урн ), в которых содержатся n предметов, причем в первом ящике находится m однородных предметов, во втором - l предметов,..., в k-м - s предметов. По схеме случайного выбора из ящиков извлекаются предметы: m’ (m' < m) предметов из первого ящика, l’ (l' < l) предметов из второго ящика, ... , s’ (s' < s) предметов из k-го (последнего) ящика. Требуется найти число различных способов извлечения (отбора) n' = m' + l' + ... + s' предметов из ящиков.

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

. ( 3.8 )

С точки зрения последовательности действий, процесс решения конкретной комбинаторной задачи разделяется на два этапа:

1) проводится анализ комбинаторной ситуации и оценивается возможность ее сведения к задаче на извлечение предметов из урн (ящиков); в ходе анализа определяются количество и состав классов, на которые необходимо разбить исходное множество предметов (если таковое возможно);

2) учитывая выбранное (построенное) разбиение и применяя к нему формулу (3.8), находим искомое число способов выбора (извлечения) предметов из классов (ящиков, урн).

Пример 3.5 служит хорошей иллюстрацией двух наиболее характерных особенностей практического применения формулы (3.8).

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

(3.8), либо некоторую сумму аналогичных произведений.

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

В разобранном примере встречаются как один вариант (пункт а), так и два варианта (пункт б).

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

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