19. Размещения, перестановки, сочетания с повторениями. Формула включения – исключения

Размещения с повторениями

Определение. Отображение множества k первых натуральных чисел 1,2,\ldots,k в данное множество \{ a_1,a_2,\ldots,a_n\}, называется размещением с повторениями, составленным из данных n элементов по k.

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

Два размещения с повторениями одинаковы тогда и только тогда, когда на одинаковых местах находятся одни и те же элементы.

Если в размещении с повторениями некоторый элемент ставится в соответствие p различным натуральным числам, т.е., иначе говоря, данный элемент занимает p различных мест, то говорят, что этот элемент повторяется в размещении p раз.

Пример. Всевозможные размещения с повторениями из трех элементов a,b,c по 2:

aa,ab,ac,ba,bb,bc,ca,cb,cc.

Теорема. Число всевозможных размещений с повторениями из n элементов по k равно

n^k.

Доказательство. По индукции. При k=1 теорема верна, так как сами элементы a_1,a_2,\ldots,a_n составляют всевозможные размещения элементов по одному, то число этих размещений равно n=n^k.

Предположим, что число размещений с повторениями из n элементов по k равно n^k. Составим из данных n элементов всевозможные размещения с повторениями по k+1 элементу. Во всяком размещении с повторениями по k+1 элементу

a_{i_{1}},a_{i_{2}},\dots,a_{i_{k}},a_{i_{k+1}}

первые k элементов

a_{i_{1}},a_{i_{2}},\dots,a_{i_{k}}

образуют некоторое размещение с повторениями из n по k элементов. В качестве последнего k+1-го элемента a_{i_{k+1}} может быть взят любой из n элементов. При различных выборах a_{i_{k+1}} получаются различные размещения. Кроме того, два различные размещения k-го порядка дают два различные размещения k+1-го порядка.

Таким образом, число всех размещений k+1-го порядка равно

n^kn=n^{k+1}.

Задача. Имеется n различных книг, каждая в p экземплярах. Сколькими способами может быть сделан выбор книг из числа данных?

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

Всякое размещение с повторениями, в котором элемент a_1 повторяется k_1 раз, элемент a_2 повторяется k_2 раз и т.д. элемент a_n повторяется k_n раз, где k_1, k_2, \ldots, k_n — данные числа, называется перестановкой с повторениями порядка

m=k_1+k_2+\dots+k_n,

в которой данные элементы a_1,\ldots,a_n повторяются соответственно k_1, \dots, k_n раз.

Теорема. Число различных перестановок с повторениями из элементов \{ a_1,a_2,\ldots,a_n\}, в которых элементы a_1,\ldots,a_n повторяются соответственно k_1,\ldots,k_n раз, равно

\displaystyle {(k_1+k_2+\dots+k_n)!\over k_1!k_2!\dots k_n!}.

Доказательство. Если мы будем считать все k_1+k_2+\ldots+k_n элементов перестановки с повторениями различными, то всего различных вариантов перестановок k_1+k_2+\ldots+k_n элементов — (k_1+k_2+\ldots+k_n)!. Однако среди этих перестановок не все различны. В самом деле, все элементы a_1 мы можем переставлять местами друг с другом, и от этого перестановка не изменится. Точно так же, можем переставлять элементы a_2, a_3, \ldots, a_n. Таким образом, всякая перестановка может быть записана k_1!k_2!\ldots k_n! способами. Следовательно, число различных перестановок с повторениями равно

\displaystyle {(k_1+k_2+\dots+k_n)!\over k_1!k_2!\dots k_n!}.

Задача. Дано p+q+r различных предметов. Сколькими способами можно разбить эти предметы на 3 группы так, чтобы первая группа содержала p предметов, вторая q предметов, а третья r предметов?

\displaystyle\left({(p+q+r)!\over p!q!r!}\right).

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

Определение. Если каждому элементу некоторого конечного множества поставлено в соответствие целое неотрицательное число — кратность данного элемента, то говорят, что задано сочетание с повторениями. Сумма k кратностей всех элементов называется порядком сочетания.

Всякое сочетание с повторениями k-го порядка, составленное из множества, содержащего n элементов, называется также сочетанием с повторением из n элементов по k.

Если k_1,k_2,\ldots,k_n — кратности элементов a_1,a_2,\ldots,a_n, то по определению k_1+k_2+\ldots+k_n есть порядок сочетания

\overbrace{a_1a_1a_1\ldots a_1}^{k_1\mbox{ \rm раз}}<br />
\overbrace{a_2a_2a_2\ldots a_2}^{k_2\mbox{ \rm раз}}\ldots<br />
\overbrace{a_na_na_n\ldots a_n}^{k_n\mbox{ \rm раз}}

Теорема. Число сочетаний с повторениями из n элементов по k выражается формулой

\tilde{\sf C}_n^k={(n+k-1)!\over k!(n-1)!}={\sf C}_{n+k-1}^k.

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

Решение. Положим пирожные в коробку, а чтобы они не перепутались, разделим их картонными разделителями. Нужно 3 разделителя. Обозначения: 0 (картонки-разделители) и 1 — пирожные. Примерная покупка: 1110101101 — три наполеона, 1 эклер, 2 песочных и 1 картошка.

Итак два класса объектов 1 (7 штук) и 0 (3 штуки) — покупка — 10 объектов.

Два способа рассуждения:

(1) задача сводится к выбору мест для 7 пирожных (или для 3 разделителей) среди 10 объектов.

(2) другой способ рассуждения (эквивалентный). Надо разбить 10 мест на две группы: для 7 пирожных и 3 разделителей.

В чем особенность: объекты повторяются, причем один эклер на вкус неотличим от другого. Отсюда название: сочетания с повторениями. Можно представлять себе, что пирожные непрерывно пекут, так что они не переводятся, сколько ни ешь. Это совсем другая ситуация, чем в обычных сочетаниях!!!

Пусть заданы два числа: k — число выбираемых элементов, и n — число типов элементов, из которых производится выбор. Число \tilde{\sf C}_n^k k сочетаний с повторениями из элементов n типов равно числу способов выбора мест для собственно выбираемых элементов различных классов, или, что то же: для разделителей между ними.

Итак, основная формула:

<br />
\tilde{\sf C}_n^k={\sf C}_{n+k-1}^{k}={\sf C}_{n+k-1}^{k}.<br />

Задача. Имеется n одинаковых предметов. Сколькими способами можно распределить эти предметы между p лицами?

Сочетания с повторениями с дополнительными условиями

Сколько существует сочетания с повторениями таких, что в них обязательно входят элементы r фиксированных типов?

Сразу возьмем по одному элементу указанного типа, и тогда уже сразу окажутся заняты r мест. Остальные k-r мест можно заполнять элементами прежних n типов.

В частности, пусть число типов n<k — числа выбранных элементов. Сколько существует сочетаний с повторениями, так что представлены хотя бы по одному все типы элементов?

Пример. r шаров размещаются по n ящикам. Сколько существует способов разместить их так, что пустых ящиков нет?

Решение. Пусть нолики — шарики, а единички — стенки ящиков (потребуется n+1 единичек). Две единички сразу кладем по краям.

Теперь положим между ними шарики-нолики, а далее нужно заполнить некоторые промежутки между ними так, чтобы между любыми двумя ноликами находилась не более одной единички. Значит, из r-1 промежутков между шариками нужно
выбрать места для n+1-2=n-1 единичек. Всего таких способов {\sf C}_{r-1}^{n-1}.

Метод координат. Подсчет числа путей

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

Поскольку на перекресток k на уровне n (считая сверху и принимая верхний уровень за нулевой) ведет {\sf C}_n^k путей (число способов выбрать k движений направо вниз из общего числа n движений вниз), то свойство суммирования путей на перекрестке можно записать как

<br />
{\sf C}_n^k={\sf C}_{n-1}^{k-1}+{\sf C}_{n-1}^k.<br />

По прежнему остается справедливым свойство симметрии {\sf C}_n^k={\sf C}_n^{n-k}.

Формула включения — исключения

Определение. Число элементов множества A называется мощностью множества A и обозначается |A|.

Теорема. Пусть даны множества A_1,A_2,\ldots,A_n. Тогда количество элементов в объединении этих множеств можно найти по формуле:

<br />
\begin{array}{l}<br />
|A_1\cup A_2\cup\ldots\cup A_n|=|A_1|+\ldots+|A_n|-\\<br />
-|A_1\cap A_2|-|A_1\cap A_3|-\ldots-|A_{n-1}\cap A_n|+\\<br />
+|A_1\cap A_2\cap A_3|+\ldots+|A_{n-2}\cap A_{n-1}\cap A_n|+(-1)^{n-1} |A_1\cap A_2\ldots\cap A_n|<br />
\end{array}<br />

Доказательство проводится по индукции. Пусть n=2. Нужно доказать формулу

<br />
|A_1\cup A_2|=|A_1|+|A_2|-|A_1\cap A_2|.<br />

Действительно, множество A_1\cup A_2 состоит из всех элементов множества A_1 и тех элементов множества A_2, которые не содержатся в множестве A_1. Тогда, сложив количества элементов во множествах A_1 и A_2, мы два
раза посчитаем количество элементов, общих для множеств A_1 и A_2.

Предположим, что формула включения — исключения справедлива для n-1 множеств.
Докажем ее для n множеств. Множество A_1\cup A_2\cup\ldots\cup A_n можно представить в виде

<br />
A_1\cup A_2\cup\ldots\cup A_n=(A_1\cup\ldots\cup A_{n-1})\cup A_n.<br />

Тогда получаем (первое равенство по формуле включения — исключения для двух множеств):
<br />
\begin{array}{l}<br />
|A_1\cup A_2\cup\ldots\cup A_n|=|A_1\cup\ldots\cup<br />
A_{n-1}|+|A_n|-|(A_1\cup\ldots\cup A_{n-1})\cap A_n|=\\<br />
=|A_1|+\ldots+|A_{n-1}|-|A_1\cap A_2|-|A_1\cap A_3|-\ldots-|A_{n-2}\cap A_{n-1}|+\\<br />
+|A_1\cap A_2\cap A_3|+\ldots+|A_{n-3}\cap A_{n-2}\cap A_{n-1}|+(-1)^{n-2} |A_1\cap A_2\ldots\cap A_{n-1}|+\\<br />
+|A_n|-|(A_1\cup\ldots\cup A_{n-1})\cap A_n|.<br />
\end{array}<br />

Используя формулу

<br />
(A_1\cup A_2\cup\ldots\cup A_{n-1})\cap A_n=(A_1\cap A_n)\cup(A_2\cap A_n)\cup   \ldots\cup(A_{n-1}\cap A_n),</p>
<p>

и формулу включения — исключения для n-1 множеств, получаем

<br />
\begin{array}{l}<br />
|(A_1\cup\ldots\cup A_{n-1})\cap A_n|<br />
=|A_1\cap A_n|+|A_2\cap A_n|+\ldots+|A_{n-1}\cap A_n|-\\<br />
-|A_1\cap A_2\cap A_n|-\ldots-|A_{n-2}\cap A_{n-1}\cap A_n|<br />
+(-1)^{n-2}|A_1\cap\ldots\cap A_n|.<br />
\end{array}<br />
В эту формулу  подставляем выражение, полученное ранее, и теорема доказана.

Задачи.

1. Есть три билета в различные театры. Сколькими способами они могут быть распределены между 25 школьниками, если каждый школьник может получить только один билет?
2. Есть три билета на КВН 1 апреля. Сколькими способами они могут быть распределены между 25 школьниками (более одного билета в руки не давать!!!)?
3. Телефонный номер состоит из 7 цифр. Насколько легче угадать правильный номер, если знать, что все его цифры различны?

4. В буфете продаются 5 сортов пирожков: с яблоками, с капустой, картошкой, мясом и грибами (цена всех пирожков одинакова). Скольким числом способов можно сделать покупку из 10 пирожков?

5. (Продолжение). Скольким числом способов можно сделать покупку так, чтобы попробовать пирожков всех видов?

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

7. Скольким числом способов можно вывести на арену цирка 5 львов и 4 тигра так, чтобы никакие два тигра не шли друг за другом (оказавшись рядом, они начинают драться)?

8. За круглым столом короля Артура сидят 12 рыцарей. Из них каждый враждует со своими соседями. Для участия в спецоперации по освобождению заколдованной принцессы нужно выбрать 5 рыцарей, но при этом нельзя посылать вместе рыцарей, враждующих друг с другом. Скольким числом способов это можно сделать?

9. Докажите формулу

<br />
\sum_{i=0}^p({\sf C}_p^i)^2={\sf C}_{2p}^p.<br />

10. Докажите, что число различных решений уравнения

x_1+x_2+\ldots+x_m=n

в неотрицательных целых числах равно {\sf C}_{m+n-1}^{m-1}.

11. Докажите, что число различных решений уравнения
x_1+x_2+\ldots+x_m=n
в натуральных числах равно {\sf C}_{n-1}^{m-1}.

12. Сколькими способами можно разложить 15 одинаковых шаров по 5 различным ящикам так, чтобы оказалось не более двух пустых ящиков?

13. Сколькими способами можно разложить 20 одинаковых шаров по 5 различным ящикам так, чтобы в каждом ящике оказалось не менее двух шаров?

14. Сколькими способами можно разложить 20 одинаковых шаров по 6 различным ящикам так, чтобы в каждом ящике оказалось не более 5 шаров?

15. Докажите, что число таких перестановок (a_1,a_2,\ldots,a_n) чисел 1,2,\ldots,n, которые удовлетворяют условию a_k\ne k при всех k, равно

\displaystyle n!\sum_{k=0}^n\frac{(-1)^k}{k!}.

Комментариев: 5

  1. 1 Число ``счастливых’’ билетов | Математика, которая мне нравится:

    [...] Далее нам понадобится число способов представления целого неотрицательного числа в виде суммы трех целых неотрицательных слагаемых. Это можно сделать способами. Действительно, число способов равно числу сочетаний с повторениями из по (или иначе, разбиваем единиц на три группы — три слагаемых, в качестве разделителей используем нули, всего элемента, из которых нужно выбрать нуля, см. сочетания с повторениями). [...]

  2. 2 лариса:

    спасибо за понятное объяснение вывода формулы сочетания с повторениями, разделители для пирожных – это здорово!!!

    [Ответить]

  3. 3 Елизавета Александровна Калинина:

    Это спасибо не мне, а Н.Я. Виленкину, А.Н. Виленкину, П.А. Виленкину и книге “Комбинаторика” :) (объяснение оттуда).

    [Ответить]

  4. 5 SPSS:

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

    [Ответить]

Оставьте свой отзыв

Добавить изображение