50Задачи

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

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

Даны   различных предметов и   ящиков. Надо положить в первый ящик   предметов, во второй -   предметов,..., в   -й -  предметов, где   Сколькими способами можно сделать такое распределение?

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

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

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

Имеются предметы   различных типов. Сколько различных перестановок можно сделать из   предметов первого типа,  предметов второго типа, ...,   предметов   -го типа? Число элементов в каждой перестановке равно   . Поэтому если бы все элементы были различны, то число перестановок равнялось бы  ! . Но из-за того, что некоторые элементы совпадают, получится меньшее число перестановок. В самом деле, возьмем, например, перестановку

(5.1)

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

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

(5.2)

где 

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

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

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

Задача 3. Флаги на мачтах.

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

Каждый способ развешивания флагов можно осуществить в два этапа. На первом этапе мы переставляем всеми возможными способами данные  флагов. Это можно сделать  ! способами. Затем берем один из способов распределения   одинаковых флагов по   мачтам (число этих способов   ). Пусть этот способ заключается в том, что на первую мачту надо повесить   флагов, на вторую -   флагов, ..., на   -ю   флагов, где   Тогда берем первые   флагов данной последовательности и развешиваем в полученном порядке на первой мачте; следующие   флагов развешиваем на второй мачте и т.д. Ясно, что используя все перестановки   флагов и все способы распределения   одинаковых флагов по   мачтам, получим все способы решения поставленной задачи. По правилу произведения получаем, что число способов развешивания флагов равно

(5.3)

Вообще, если имеется   различных вещей, то число способов распределения этих вещей по   различным ящикам равно