Сколькими способами можно сделать такое

Общая постановка этих задач:
Задач 1. Раскладка по ящикам
Даны

различных предметов и

ящиков. Надо положить в первый ящик

предметов, во второй -

предметов,..., в

-й -

предметов, где

. Сколькими способами можно сделать такое распределение?
Число различных раскладок по ящикам равно

Эту формулу можно получить при решении следующей, на первый взгляд, совсем непохожей задачи:
Задача 2. Перестановки с повторением.
Имеются предметы

различных типов. Сколько различных перестановок можно сделать из

предметов первого типа,

предметов второго типа, ...,

предметов

-го типа? Число элементов в каждой перестановке равно

. Поэтому если бы все элементы были различны, то число перестановок равнялось бы

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

(5.1)

в которой сначала выписаны все элементы первого типа, потом все элементы второго типа, ..., наконец, все элементы

-го типа. Элементы первого типа можно переставлять друг с другом

способами. Но так как все эти элементы одинаковы, то такие перестановки ничего не меняют. Точно так же ничего не меняют

перестановок элементов второго типа, ...,

перестановок элементов

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

способами так, что она остается неизменной. То же самое верно и для любого другого расположения элементов. Поэтому множество всех

перестановок распадается на части, состоящие из

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

(5.2)

где

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

Чтобы установить связь между этими задачами, занумеруем все

мест, которые могут занимать наши предметы.
Каждой перестановке соответствует распределение номеров мест на

классов. В первый класс попадают номера тех мест, на которые попали предметы первого типа, во второй - номера мест предметов второго типа и так далее. Тем самым устанавливается соответствие между перестановками с повторениями и раскладкой номеров мест по "ящикам". Понятно, что формулы решения задач оказались одинаковыми.
В рассмотренных задачах мы не учитывали порядок, в котором расположены элементы каждой части. В некоторых задачах этот порядок надо учитывать.
Задача 3. Флаги на мачтах.
Имеется

различных сигнальных флагов и

мачт, на которые их вывешивают. Значение сигнала зависит от того, в каком порядке развешены флаги. Сколькими способами можно развесить флаги, если все флаги должны быть использованы, но некоторые из мачт могут оказаться пустыми?
Каждый способ развешивания флагов можно осуществить в два этапа. На первом этапе мы переставляем всеми возможными способами данные

флагов. Это можно сделать

способами. Затем берем один из способов распределения

одинаковых флагов по

мачтам (число этих способов