Материал: Дискретная математика теория и практика

3.{a, a}, {a, b}, {a, c}, {b, b}, {b, c}, {c, c} – (3,2)-сочетания с повторениями;

4.{a, b}, {a, c}, {b, c} – (3,2)-сочетания.

Число (n, k)-размещений с повторениями обозначается через A kn , а без

повторений – Аnk . Число перестановок без повторений из n элементов обозначается через Pn, то есть Pn = Аnn . Число (n, k)-сочетаний с повторениями обозначаем через С kn , а без повторений – Сnk .

Утверждение 2.1. А kn = nk .

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

Соглашение. В дальнейшем для общности формул условимся считать,

что 0! = 1.

= 0 при k > n.

Доказательство. Случай k > n очевиден. Рассмотрим случай, когда k ≤ n. Каждое (n, k)-размещение без повторений является кортежем длины k, координаты которого попарно различны и выбираются из множества мощности n. Тогда первая координата кортежа может быть выбрана n способами, после каждого выбора первой координаты вторая координата может быть выбрана n − 1 способами и так далее. Соответственно, после каждого выбора первой и так далее (k − 1)-й координаты кортежа k-я координата может быть выбрана n − (k − 1) = n – k + 1 способами. Следовательно, по обобщенному правилу произведения, получаем требуемую формулу.

Доказательство. Случай k > n очевиден. Рассмотрим случай, когда k ≤ n. Каждое (n, k)-сочетание можно упорядочить k! способами. Объединение получаемых таким образом попарно непересекающихся множеств (n, k)-размещений для всех возможных (n, k)-сочетаний, очевидно, даст все (n, k)-размещения. То-

Доказательство. Каждому (n, k)-сочетанию с повторениями В, составленному из элементов множества X = {x1, …, xn}, поставим в соответствие кор-

27

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

{1, 2, …, n + k –1} (множества всех номеров координат в кортежах), то есть

(4, 8)-сочетание с повторениями. Тогда α(В) = (0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0). Об-

ратно, если α(В) = (1, 0, 0, 1, 0, 0, 0, 1, 0), то однозначно получаем, что

В = {2, 2, 3, 3, 3, 4}.

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

2.1–2.4 остаются справедливыми.

Выше мы определили понятие перестановки без повторений из n элементов. Понятие перестановки с повторениями рассматривается в случае, когда имеется n элементов, которые можно разбить на k групп, так что элементы, входящие в одну группу, неразличимы между собой и отличны от элементов, входящих в другие группы. Пусть число элементов в каждой группе равно соответственно n1, n2, ..., nk, то есть n1 + n2 + … + nk = n.

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

Если число элементов в каждой группе равно соответственно n1, n2, ..., nk, то есть n1 + n2 + … + nk = n, то число всех перестановок с повторениями из n

28

Доказательство. Согласно правилу произведения число перемещений

Рассмотренный в параграфах 2.1 и 2.2 теоретический материал можно представить в виде схемы, использование которой может быть полезно при решении задач (рис. 2.1).

(n, k)-выборка

Рис. 2.1. Схема определения вида комбинаторной конфигурации

2.3. Примеры решения задач

29

Пример 2.4. Бросают две игральные кости (с шестью гранями каждая). Сколькими способами они могут упасть так, что либо на каждой грани выпадет четное число очков, либо на каждой грани выпадет нечетное число очков?

Решение. Пусть А – число способов выпадения на каждой кости четного числа очков, В – число способов выпадения на каждой кости нечетного числа очков. Тогда по правилу суммы, искомое число равно А + В. Пусть С – число способов выпадения четного числа очков на первой кости, а D – число способов выпадения четного числа очков на второй кости. Ясно, что С = D = 3, а по правилу произведения А = С D = 9. Аналогично, В = 9, а искомое число

равно 18. Пример 2.5. Сколькими способами три награды (за первое, второе и

третье места) могут быть распределены между 10 участниками соревнований? Решение. Требуется найти число способов, сколькими из 10 человек мож-

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

10 участниками соревнований А103 = 720 способами.

Пример 2.6. Имеется 10 различных книг. Сколькими способами их можно расставить на полке?

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

перестановок без повторений из 10 элементов. Получаем: Аnn = P10 = 10! =

=3 628 000 способов.

Пример 2.7. Сколько двузначных чисел можно составить, используя цифры 7, 4 и 5?

Решение. Порядок следования цифр в числе важен. Например, 47 и 74 – две различные выборки, удовлетворяющие условию задачи. Кроме этого, комбинация, например, 77 также является одним из решений. Значит, речь идет о размещениях с повторениями из трех по два. Следовательно, количество чисел равно А 32 = 32 = 9.

Пример 2.8. Сколькими способами можно вытянуть 5 карт трефовой масти из стандартной колоды, содержащей 52 карты?

Решение. Всего в колоде 13 карт трефовой масти. Из этих 13 карт надо выбрать 5, причем без повторений и учета порядка следования карт в выборке. Разные варианты должны отличаться по составу. Следовательно, требуется

найти число всех (13,5)-сочетаний: С135 = 13! =1287. 5! 8!

Пример 2.9. В магазине продается 4 сорта пирожных: бизе, эклеры, песочные, наполеоны. Сколькими способами можно выбрать 7 пирожных?

30

Решение. Каждая покупка – это выборка из 4 элементов по 7, причем с повторениями, так как 4 < 7. Порядок следования сорта пирожных внутри выборки не важен. Следовательно, число таких покупок равно числу всех (4, 7)-

Пример 2.10. У врача 3 таблетки одного лекарства, 2 таблетки – другого и 4 таблетки – третьего. Сколькими способами он может распределить прием имеющихся таблеток по одной в день?

Решение. Общее число таблеток 3 + 2 + 4 = 9 равно числу дней приема лекарств, то есть все таблетки входят в выборку, но присутствуют повторяющиеся неразличимые элементы – таблетки одного лекарства. Решение задачи сводится к нахождению числа всех перестановок с повторениями из 9 элемен-

2.4. Бином Ньютона

Исторически название бином Ньютона несправедливо, поскольку формулу (а + b)n знали еще среднеазиатские математики, начиная с Хайяма (Омар

Хайям (около 1048 – 1131) – персидский поэт, математик и философ), а в Европе до Ньютона (Исаак Ньютон (1643 – 1727) – английский физик, астроном и математик) еe знал Паскаль (Блез Паскаль (1623 – 1662) – французский математик). Однако заслуга Ньютона заключается в том, что он обобщил эту формулу для нецелого показателя n (см. замечание 2.2).

Для натурального показателя n формула бинома Ньютона имеет вид:

k =0

Доказательство. Для доказательства формулы (9) применим метод математической индукции.

1.База индукции. Пусть n = 1. Тогда (а + b)1 = С10 а0b1 + С11а1b0 = а + b.

2.Индуктивное предположение. Предположим, что формула (9) верна

для n – 1.

3. Индукционный переход. Докажем справедливость формулы (9) для n. В данном случае получаем

31