Комбинаторика разбиений

Введение

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

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

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

Задачи

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

Задача 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},$$ в которой сначала выписаны все элементы первого типа, потом все элементы второго типа, ..., наконец, все элементы $$k$$ -го типа. Элементы первого типа можно переставлять друг с другом $$n_1$$! способами. Но так как все эти элементы одинаковы, то такие перестановки ничего не меняют. Точно так же ничего не меняют $$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! }},$$ где $$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$$ мест, которые могут занимать наши предметы. Каждой перестановке соответствует распределение номеров мест на $$k$$ классов. В первый класс попадают номера тех мест, на которые попали предметы первого типа, во второй - номера мест предметов второго типа и так далее. Тем самым устанавливается соответствие между перестановками с повторениями и раскладкой номеров мест по "ящикам". Понятно, что формулы решения задач оказались одинаковыми.

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

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

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

Каждый способ развешивания флагов можно осуществить в два этапа. На первом этапе мы переставляем всеми возможными способами данные $$n$$ флагов. Это можно сделать $$n$$! способами. Затем берем один из способов распределения $$n$$ одинаковых флагов по $$k$$ мачтам (число этих способов $$C_{n+k-1}^{k-1}$$ ). Пусть этот способ заключается в том, что на первую мачту надо повесить $$n_1$$ флагов, на вторую - $$n_2$$ флагов, ..., на $$k$$ -ю $$n_k$$ флагов, где $$n_1 + n_2 + \ldots + n_k = n.$$ Тогда берем первые $$n_1$$ флагов данной последовательности и развешиваем в полученном порядке на первой мачте; следующие $$n_2$$ флагов развешиваем на второй мачте и т.д. Ясно, что используя все перестановки $$n$$ флагов и все способы распределения $$n$$ одинаковых флагов по $$k$$ мачтам, получим все способы решения поставленной задачи. По правилу произведения получаем, что число способов развешивания флагов равно$$n!C_{n+k-1}^{k-1}=\frac{{(n+k-1)!}}{{(k-1)!}}=A_{n+k-1}^n.$$ Вообще, если имеется $$n$$ различных вещей, то число способов распределения этих вещей по $$k$$ различным ящикам равно $$A_{n+k-1}^n.$$

Разные статистики

Задачи о раскладке предметов по ящикам весьма важны для статистической физики. Эта наука изучает, как распределяются по своим свойствам физические частицы; например, какая часть молекул данного газа имеет при данной температуре ту или иную скорость. При этом множество всех возможных состояний распределяют на большое число $$k$$ маленьких ячеек (фазовых состояний), так что каждая из $$n$$ частиц попадет в одну из ячеек.

Вопрос о том, какой статистике подчиняются те или иные частицы, зависит от вида этих частиц. В классической статистической физике, созданной Максвеллом и Больцманом, частицы считаются различимыми друг от друга. Такой статистике подчиняются, например, молекулы газа. Известно, что $$n$$ различных частиц можно распределить по $$k$$ ячейкам $$k^n$$ способами. Если все эти $$k^n$$ способов при заданной энергии имеют равную вероятность, то говорят о статистике Максвелла-Больцмана.

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

Однако для многих частиц, например таких как электроны, протоны и нейтроны, не годится и статистика Бозе-Эйнштейна. Для них в каждой ячейке может находится не более одной частицы, причем различные распределения, удовлетворяющие указанному условию, имеют равную вероятность. В этом случае может быть $$C_k^n$$ различных распределений. Эта статистика называется статистикой Дирака-Ферми.

Деревья и перестановки из n элементов

С помощью леса можно представить перестановки из $$n$$ элементов множества $$M =\{a;b;c;d\}$$ (множество мы определяем так: множество - это неупорядоченная совокупность различных объектов или структура данных, используемая для представления множества). Подсчитаем, сколько можно получить перестановок. Для $$n$$ такой лес изображен на рис. 5.1.

Число сочетаний

Рассмотрим подмножества множества, состоящего из пяти элементов, и подсчитаем их число. При этом записывать подмножества будем не с помощью букв, как обычно, а в виде последовательностей длиной пять, составленных из нулей и единиц. Каждая из единиц указывает на наличие в подмножестве соответствующего элемента. Например, подмножества, содержащие один элемент, будут изображаться следующими последовательностями: 10000, 01000, 00100, 00010, 00001. Пустое подмножество $$\emptyset$$ будет соответствовать последовательности 00000. Подмножества, содержащие по два элемента из пяти, запишутся с помощью следующих последовательностей: 11000, 10100, 10010, 10001, 01100. 01010, 01001, 00110, 00101, 00011. Всего их $$C_5^2=10.$$

Вообще, число сочетаний из $$n$$ элементов по $$m$$ равно числу всевозможных последовательностей из $$m$$ единиц и $$n - m$$ нулей.

Задачи на разбиение чисел

Теперь мы переходим к задачам, в которых все разделяемые предметы совершенно одинаковы. В этом случае можно говорить не о разделении предметов, а о разбиении натуральных чисел на слагаемые (которые, конечно, тоже должны быть натуральными числами).

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

Задача 4. Отправка бандероли.

За пересылку бандероли надо уплатить 18 рублей. Сколькими способами можно оплатить ее марками стоимостью 4, 6, и 10 рублей, если два способа, отличающиеся порядком марок, считаются различными (запас марок различного достоинства считаем неограниченным)?

Обозначим через $$f(N)$$ число способов, которыми можно наклеить марки в 4, 6 и 10 рублей так, чтобы общая стоимость этих марок равнялась $$N.$$ Тогда для $$f(N)$$ справедливо следующее соотношение:$$f(N) = f(N- 4) + f(N - 6) + f(N - 10).$$ Пусть имеется некоторый способ наклейки марок с общей стоимостью $$N,$$ и пусть последней наклеена марка стоимостью 4 рубля. Тогда все остальные марки стоят ( $$N - 4$$ ) рубля. Наоборот, присоединяя к любой комбинации марок общей стоимостью ( $$N - 4$$ ) рубля одну четырехрублевую марку, получаем комбинацию марок стоимостью $$N$$ рублей. При этом из разных комбинаций стоимостью ( $$N - 4$$ ) рублей получается разные комбинации стоимостью $$N$$ рублей. Итак, число искомых комбинаций, где последней наклеена марка стоимостью 4 рубля, равно $$f(N - 4).$$

Точно так же доказывается, что число комбинаций, оканчивающихся на шестирублевую марку, равно $$f(N - 6),$$ а на десятирублевую марку оканчиваются $$f(N - 10)$$ комбинацией. Поскольку любая комбинация оканчивается на марку одного из указанных типов, то по правилу суммы получаем соотношение 5.4.

Соотношение 5.4 позволяет свести задачу о наклеивании марок на сумму $$N$$ рублей к задачам о наклеивании марок на меньшие суммы. Но при малых значениях $$N$$ задачу легко решить непосредственно. Простой подсчет показывает, что$$f(0)=1,f(1)=f(2)=f(3)=0,f(4)=1,f(5) = 0,\\ f(6) = 1,f(7)=0,f(8)=1,f(9)=0.$$ Равенство $$f(0)=1$$ означает, что сумму в 0 рублей можно уплатить единственным образом: совсем не наклеивая марок. А сумму в 1,2,3,5,7 и 9 рублей вообще никак нельзя получить с помощью марок стоимостью 4, 6 и 10 рублей. Используя значения $$f(N)$$ для $$N = 0,1,2,3,4,5,6,7,8,9,$$ легко найти $$f(10):$$$$f(10)=f(6)+f(4)+f(0)=3.$$ После этого находим$$f(11)=f(7) + f(5) + f(1) = 0,$$ $$f(12)=f(8) + f(6) + f(2) = 2$$ и т.д. Наконец, получаем значение $$f(18)=8.$$ Таким образом, марки можно наклеить восемью способами. Эти способы таковы: $$10,4,4$$ ; $$4,10,4$$ ; $$4,4,10$$ ; $$6,4, 4,4$$ ; $$4,6,4,4$$ ; $$4,4,6,4$$ ; $$4,4,4,6$$ ; $$6,6,6.$$ Отметим, что значения $$f(N)$$ для $$N = 1,2,3,4,5,6,7,8,9$$ можно было получить иначе, не приводя непосредственно проверки. Дело в том, что при $$N < 0$$ имеем $$f(N) = 0,$$ поскольку отрицательную сумму нельзя уплатить, наклеивая неотрицательное количество марок. В то же время, как мы видели, $$f(0) = 1.$$ Поэтому $$f(1)=f(-3)+f(-5)+f(-9)=0.$$

Точно так же получаем значение $$f(2)=0,f(3)=0,$$ а для $$N = 4$$ имеем $$f(4)=f(0)+f(-2)+f(-6)=1.$$

Задача 5.Общая задача о наклейке марок.

Разобранная задача является частным случаем следующей общей задачи: Имеются марки достоинством в $$n_1,n_2,\ldots,n_k.$$ Сколькими способами можно оплатить с их помощью сумму в $$N$$ рублей, если два способа, отличающиеся порядком, считаются различными? Все числа $$n_1,n_2 ,\ldots,n_k$$ различны, а запас марок неограничен. Здесь на первом месте мы будем указывать число слагаемых, на втором – разбиваемое число и на последнем - ограничения на величину слагаемых.

В этом случае число $$f(N)$$ способов удовлетворяет соотношению$$f(N) = f(N - n_1 ) + f(N - n_2 ) + \ldots + f(N - n_k).$$ При этом $$f(N) = 0,$$ если $$f(0)=1$$ и $$N < 0.$$ С помощью соотношения 5.5 можно найти $$f(N)$$ для любого $$N,$$ последовательно вычисляя $$f(1),f(2),\ldots,f(N-1).$$

Рассмотрим частный случай этой задачи, когда $$n_1= 1,n_2 = 2,\ldots ,$$ $$n_k = k.$$ Мы получаем всевозможные разбиения числа $$N$$ на слагаемые $$1,2,\ldots,k,$$ причем разбиения, отличающиеся порядком слагаемых, считаются различными. Обозначим число этих разбиений через $$\varphi(k;N).$$ ( На первом месте мы будем указывать число слагаемых, на втором - разбиваемое число и на последнем – ограничения на величину слагаемых.) Из соотношения 5.5 следует, что$$\varphi(k;N-1)+\varphi(k;N-2)+\ldots+\varphi(k;N-k).$$ При этом $$\varphi (k;0) = 1$$ и $$\varphi(k;N)= 0,$$ если $$N <0.$$ Вычисление $$\varphi (N;k)$$ можно упростить, если заметить, что$$\varphi (N-1;k)=\varphi(N-2;k)+\varphi(N-k-1;k),$$ и потому$$\varphi(N;k)=2\varphi(N-1;k)-\varphi (N - k - 1;k).$$ Ясно, что слагаемые не могут быть больше $$N.$$ Поэтому $$\varphi(N,N)$$ равно числу всех разбиений на $$N$$ на натуральные слагаемые (включая и "разбиение" $$N = N.$$ Если число слагаемых равно $$s,$$ то получаем $$C_{N - 1}^{s - 1}$$ разбиений. Поэтому$$\varphi(N,N)=C_{N-1}^0+C_{N-1}^1+\ldots+C_{N-1}^{N-1}=2^{N-1}.$$ Итак, мы доказали, что натуральное число $$N$$ можно разбить на слагаемые $$2^{N - 1}$$ способами. Напомним, что при этом учитывается порядок слагаемых.Например, число 5 можно разбить на слагаемые $$2^{5 - 1} = 16$$ способами.

Комбинаторные задачи теории информации

Информация - сведения, неизвестные до их получения, или данные, или значения, приписанные данным.

Теория информации - математическая дисциплина, изучающая количественные свойства информации.

Задачу, похожую на только что решенную, приходится решать в теории информации. Предположим, что сообщение передается с помощью сигналов нескольких типов. Длительность передачи сигнала первого типа равна $$t_1,$$ второго типа - $$t_2,\ldots,k$$ -го типа - $$t_k$$ единиц времени.

Задача 6. Сколько различных сообщений можно передать с помощью этих сигналов за $$T$$ единиц времени? При этом учитываются лишь "максимальные" сообщения, то есть сообщения, к которым нельзя присоединить ни одного сигнала, не выйдя за рамки отведенного для передачи времени.

Обозначим число сообщений, которые можно передать за время $$T$$ через $$f(T).$$ Рассуждая точно так же, как и в задаче о марках, получаем, что $$f(T)$$ удовлетворяет соотношению$$f(T)=f(T-t_1)+\ldots+f(T-t_k).$$ При этом снова $$f(T) = 0,$$ если $$T < 0$$ и $$f(0) = 1$$$.