Комбинаторные алгоритмы для программистов



             

Задачи


Общая постановка этих задач:

Задач 1. Раскладка по ящикам

Даны

n
различных предметов и
k
ящиков. Надо положить в первый ящик
n_1
предметов, во второй -
n_2
предметов,..., в
k
-й -
n_k
предметов, где
n_1 + n_2 + \ldots + n_k = n
. Сколькими способами можно сделать такое распределение?

Число различных раскладок по ящикам равно

P(n_1,n_2,\ldots,n_k ) = \frac{{n!}}{{n_1 !n_2 !\ldots n_k }}.
Эту формулу можно получить при решении следующей, на первый взгляд, совсем непохожей задачи:

Задача 2. Перестановки с повторением.

Имеются предметы

k
различных типов. Сколько различных перестановок можно сделать из
n_1
предметов первого типа,
n_2
предметов второго типа, ...,
n_k
предметов
k
-го типа? Число элементов в каждой перестановке равно
n_1 + n_2 + \ldots + n_k = n
. Поэтому если бы все элементы были различны, то число перестановок равнялось бы
n!
. Но из-за того, что некоторые элементы совпадают, получится меньшее число перестановок. В самом деле, возьмем, например, перестановку
\frac{aa..a}{n_1}\frac{bb\ldots b}{n_2} \ldots \frac{xx\ldots x}{n_3},

(5.1)

в которой сначала выписаны все элементы первого типа, потом все элементы второго типа, ..., наконец, все элементы
k
-го типа. Элементы первого типа можно переставлять друг с другом
n!
способами. Но так как все эти элементы одинаковы, то такие перестановки ничего не меняют. Точно так же ничего не меняют
n_2 !
перестановок элементов второго типа, ...,
n_k !
перестановок элементов
k
-го типа.

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

n_1 !n_2 !\ldots n_k !
способами так, что она остается неизменной. То же самое верно и для любого другого расположения элементов. Поэтому множество всех
n!
перестановок распадается на части, состоящие из
n_1 !n_2 !\ldots n_k !
одинаковых перестановок каждая. Значит, число различных перестановок с повторениями, которые можно сделать из данных элементов, равно
P(n_1,n_2,\ldots,n_k ) = \frac{{n!}} {{n_1 !n_2 !\ldots n_k }},

(5.2)

где
n_1 + n_2 + \ldots + n_k = n
.

Пользуясь формулой 5.2, можно ответить на вопрос: сколько перестановок можно сделать из букв слова "Миссисипи"? Здесь у нас одна буква "м", четыре буквы "и", три буквы "с" и одна буква "п", а всего 9 букв. Значит, по формуле 5.2 число перестановок равно

P(4,3,1,1)=\frac{{9!}}{{4!\cdot 3!\cdot 1!\cdot 1!}}=2520.
Чтобы установить связь между этими задачами, занумеруем все
n
мест, которые могут занимать наши предметы.


Содержание  Назад  Вперед