8.7. Перестановки и сочетания с повторением

Идея перестановки с повторением может показаться бессмысленной, поскольку перестановки ассоциируются с перегруппировками, которые, похоже, не допус­кают повторений. Если допустить повторение, то необходимо пересмотреть наше представление о перестановке. Главным свойством перестановки является поря­док. Строка cab отличается от строки обе. Если опять рассмотреть задачу о номер­ных знаках автомобилей с тремя буквами, за которыми следуют три цифры, и не допускать повторений, то получим 26х25х24х 10x9x8 различных номерных зна­ков. Существует Р(25,3) способов выбора букв и Р(10,3) способов выбора цифр. Таким образом, существуют Р(25,3) х Р(10,3) различных номерных знаков. В этом и состоит обычное представление о перестановках. Заметим, что допуская повторение, мы не отказываемся от понятия порядка. Номерной знак ФПФ 199 отличается от номерного знака ПФФ919. Говоря о перестановках с повторением, имеется в виду, что этот порядок сохраняется. Вспомним, что если в номерном знаке разрешить повторения букв и цифр, то существуют 26 возможных способов выбора для каждой буквы и 10 возможных способов выбора для каждой цифры. Таким образом, если разрешить повторение, то будут существовать 26³ х 10³ воз­можных номерных знаков. В общем случае, если имеется к упорядоченных мест, для каждого из которых можно выбрать любой из п объектов, существуют n^к способов выбора объектов. Таким образом, число перестановок с повторением, когда к объектов выбираются из тг объектов, равно n^к. Наверное, идея повто­рения, использованная здесь, требует разъяснений. Один из способов трактовки повторения — это думать, что повторение предполагает возвращение объекта и повторное его использование. Другой способ трактовки данного типа повторения состоит в том, что имеется столь достаточное количество объектов каждого типа, которое нельзя исчерпать. Например, в случае с номерными знаками требует­ся теперь только три копии каждой буквы и каждой цифры. Приведенная ниже теорема сформулирована для такого представления о повторении.

ТЕОРЕМА 8.66. Пусть S — множество, содержащее n неразличимых объектов. Тогда количество различных перестановок, образованных выбором k элементов с повторением, равно n^к.

ПРИМЕР 8.67. Лототрон содержит 500 шаров с номерами. Из него выбирают шар, номер которого записывают. Шар возвращают в лототрон и процедура повторяет­ся. Так продолжается до тех пор, пока не наберется комбинация из пяти номеров.

Подсчитаем количество возможных комбинаций чисел. Для каждого из пяти чи­сел имеется 500 способов выбора. Следовательно, число различных комбинаций составляет 500⁵.

ПРИМЕР 8.68. Сколько существует индивидуальных номеров карточек социаль­ного страхования?

Поскольку номер следует выбирать из неотрицательных целых чисел, мень­ших десяти, то выбираются девять цифр, причем каждая выбирается из десяти цифр с повторением, поэтому имеются 10⁹ различных номеров карточек социаль­ного страхования.

Предположим, что комитет состоит из восьми человек. При принятии реше­ния они голосуют "за", “против" или воздерживаются от голосования. Сколько возможных исходов голосования по данному решению? Если интересует вопрос, кто и как голосовал, тогда речь идет о числе перестановок, когда для каждого голосующего имеются три варианта ответа, что дает З⁸ возможных исходов го­лосования. Допустим, что нас интересует только общий результат голосования. Таким образом, четыре голоса “за", три голоса “против" и один воздержавший­ся — это один из возможных исходов. Таким же возможным исходом является вариант: два голоса “за”, четыре голоса "против” и два воздержавшихся. Для удобства перечислим сначала голоса "за”, затем “против" и, наконец, голоса воз­державшихся. Таким образом, голосование можно изобразить, например, в виде ЗЗППВВВВ, где два голоса “за”, два “против” и четыре воздержавшихся. Далее можно строить разбиение голосов, например, ЗЗ|ПП|ВВВВ. Поскольку порядок расположения голосов понятен, можно перейти к записи хх|хх|хххх, изобража­ющей 33|ПП|ВВВВ. Таким образом, запись хх||хххххх будет представлять два голоса “за” и четыре воздержавшихся, а запись хххххххх|| будет соответство­вать голосованию “за" всех восьми членов комитета. Таким образом, установлено взаимно однозначное соответствие между возможными исходами голосования и различными способами размещения восьми знаков х и двух знаков |. Но это ни что иное, как количество способов выбора двух мест из десяти для размещения знака | или, что эквивалентно, количество способов выбора восьми мест из десяти для размещения знака х. Следовательно, существуют

способов разместить х и |. А значит, существуют

возможных исходов голосования.

Предположим, что п объектов выбираются из к типов объектов с неограни­ченным повторением. Пусть а_i — объект типа i, тогда n₁a₁+n₂a₂+n₃a₃+…+n_ka_k где n_i ≥ 0 для всех i, a n₁ + n₂ + n₃ + n_k = n представляет выбор n объектов типа i. Как и прежде, это можно записать в виде

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

Заметим, что разделителей | на один меньше количества типов. Таким обра­зом, имеем n объектов плюс k — 1 разделителей, образующих n + k — 1 мест для размещения х или |. Каждое расположение знаков х и | дает новый способ вы­бора n объектов из k типов объектов с неограниченным повторением. Поскольку существует С(n + k - 1, n) = С(n + k - 1, k - 1) способов выбора места для знака х или, что эквивалентно, для знака |, то существуют

различных способов выбора n из k типов объектов с неограниченным повто­рением. Такие выборки будем называть сочетаниями из k объектов по n с повторением. Получаем следующую теорему.

ТЕОРЕМА 8.69. Количество различных сочетаний из к объектов по п равно ПРИМЕР 8.70. Если в булочной продается 10 различных видов пончиков, то сколькими способами можно выбрать дюжину пончиков? Поскольку 12 пончи­ков выбираются из 10 различных типов с повторением, то имеются

различных способов выбрать дюжину пончиков.

ПРИМЕР 8.71. Сколько решений имеет уравнение

где каждое n, — неотрицательное целое число? Это эквивалентно вопросу о том, сколько существует различных выборок вида

где имеется n, объектов типа а, и

но количество таких выборок — это количество различных сочетаний из 5 эле­ментов по 25 с повторениями. Итак, существуют

различных решений уравнения

Было показано, что число различных сочетаний из k объектов по n объектов с повторением равно

Если необходимо выбрать хотя бы по одному объекту каждого типа, то имеются п-к выборов из к различных объектов. Следовательно, имеем С(n – k + k - 1,k - 1) или С(n — 1 ,k— 1) способов выбора.

ТЕОРЕМА 8.72. Количество различных сочетаний из к объектов по n объектов с повторением, когда необходимо выбрать хотя бы по одному объекту каждого типа, равно

ПРИМЕР 8.73. Если в булочной продается 10 различных видов пончиков, то сколькими способами можно выбрать две дюжины пончиков, если необходимо выбрать хотя бы по одному пончику каждого вида? Если бы не было послед­него ограничения, то для выбора двух дюжин пончиков из 10 различных видов существовало бы

различных способов. Однако, учитывая ограничение, можно выбрать только 24 - 10 = 14 пончиков из 10 различных видов, что дает

различных вариантов выбора.

ПРИМЕР 8.74. Найдем количество различных целочисленных решений уравнения

если n₁ ≥ 1. n₂ ≥ 1 n₃ ≥ 2 n₄ ≥ 2 и n₅ ≥ 2. Представим эту задачу, как подсчет количества выборок вида

причем следует выбрать, по крайней мере, одно а₁ одно а₂, два а₃, два а₄ и два а₅. Это оставляет для выбора только 25 - 8 = 17 элементов из пяти типов, что дает