1.5. Перестановки

При составлении размещений без повторений из п по k мы получали расстановки, отличающиеся друг от друга либо составом, либо порядком элементов. Но если брать расстановки, которые включают все п элементов, то они могут отличаться друг от друга лишь порядком входящих в них элементов. Такие расстановки называются перестановками из п элементов, а их число обозначается Рп. Следовательно, число перестановок равно Р„ =А" = п\.

Перестановки я = (п, л2,...,я„) элементов 1, 2,..., п записываютив

{Л "1и Л

матричной форме п =, где верхняя строка —это по-

V4 Щ )

рядковые номера 1.2,..., п позиций элементов в перестановке; нижняя строка — тотже набор чисел 1,2,..., я, взятых в каком-либо порядке; — номер элементаместе перестановки. Порядок столбцов в перестановках, записанных в матричной не является существенным, так как в этом случае номер позиции каждого элемента в перестановке указывается явно в верхней строке. Например, перестановка (3,2,4,1) из четырех элементов

(12 3 4) Г3 1 4 2Л (2 14 3

может быть записана как

Задача о ладьях. Сколькими способами можно расположить на шахматной доске 8 ладей, чтобы они «не били» друг друга?

Решение. Условие «не могли бить» означает, что на каждой горизонтали и вертикали может стоять лишь одна ладья. Ввиду этого, каждому расположению ладей на доске соответствует переста-

( 1 2 8 *i т-*

новка я =. Верхняя строка перестановки — это но-

Vli "-2 llsj

мера горизонталей, нижняя — вертикалей, пересечение которых

определяет положение ладей на доске. Следовательно, число расстановок равно числу перестановок = 8! из 8 элементов.

1.6. Сочетания

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

ментов. Общее число сочетаний обозначают через С* или [Н

W

Определим это число. Составим все сочетания из п по к. Затем переставим в каждом сочетании элементы всеми возможными способами. Теперь мы получили расстановки, отличающиеся либо составом, либо порядком, т.е. это все размещения без повторений из п по к. Их число равно Af. Учитывая, что каждое сочетание дает размещений, то по правилу произведения можно записать

С* x£!=4f. Тогда С* =Яили С* =—~ , ч-. и

кк\{п-к)\

Задача о прямоугольниках. Сколько различных прямоугольников можно вырезать из клеток доски, размер которой т х л?

Решение. Прямоугольник однозначно определяется положением его сторон. Горизонтальные стороны могут занимать любое из т + 1 положения. Тогда число способов их выбора равно С*+1. Вертикальные стороны можно выбрать С„2+1 способами. По правилу прямого произведения заключаем, что количество прямоугольников равно CfnA -С,;+1.

1.7. Сочетания с повторениями

Имеются предметы п различных видов. Число элементов каждого вида неограниченно. Сколько существует расстановок длины к, если не принимать во внимание порядок элементов? Такие расстановки называют сочетаниями с повторениями, количество и обозначение которых следующее С„* =C£lk l =Ck v Выведем

данную формулу.

Пусть a, b,c,..., d— это исходные различные типы элементов, количество которых п. Рассмотрим произвольное сочетание с повторениями cbbcaccda...ddaccbbb из данных типов элементов. Так как порядок элементов в сочетаниях не учитывается, то расстановку можно записать и так: аа...а \ ЪЪ...Ъ \ сс...с \... \ dd...d, где элементы каждого из типов упорядочены и завершаются вертика-

Сочетания с повторениями

13

льной чертой, за исключением последней серии элементов. Длина такой расстановки с учетом вертикальных линий составляет k + (п — \] =п + к— 1, где к — количество элементов в расстановке; п — 1 — число вертикальных линий. Очевидно, что любую такую расстановку можно задать выбором из п + к — 1 места п — 1 место для положений вертикальных линий. Это можно сделать СЙы способами. Промежуточные места между линиями заполняются соответствующими типами элементов.

Задача. Трое ребят собрали в саду 63 яблока. Сколькими способами они могут их разделить между собой?

Решение. Поставим в соответствие каждому делению яблок между ребятами сочетание с повторениями следующим способом. Типами элементов в нашем случае будут ребята. Таким образом, имеем три типа элементов а,Ь, с (п = 3), из которых предстоит составить все различные расстановки длины к = 63. Наличие в расстановке какого-либо из элементов а, Ъ, с отвечает принадлежности данного яблока соответствующему мальчику. Порядок элементов в такой расстановке не играет роли. При делении яблок между ребятами не важно, какое из них попадет тому или иному мальчику/Гогда число способов разделить яблоки между ребятами равно С363 = с£63 ! =С32+63 1=2080.

Задача. Найти количество целочисленных решений системы

ху +х2+... +хп=к, k>Q,Xj>0,i= 1, 2,...,п;п >1.

Решение. Рассмотрим следующую интерпретацию решения уравнения. Каждое значение х, = 1,г-н 1, + ... + представим как сумму единиц, количество которых Индекс у 1, отмечает ее принадлежность к разложению числа Таким образом, мы ввели п типов различных элементовзначение каждого из них равно единице. Теперь любое решение исходного уравнения можно представить как сумму, составленную из к произвольных единиц множества {li, l2,-, U- Суммируя подобные единицы с одинаковыми индексами, можно составить соответствующие слагаемые решения исходного уравнения. Данное соответствие является взаимно однозначным, откуда и следует, что число решений системы равно числу сочетаний с повторениями

Тк (~>п-\ —Г

*-л -Si+it-J -4i+A-r