Размещение частиц по ячейкам

Основы комбинаторного анализа

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

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

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

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

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

Изложение методов комбинаторного анализа можно вести, отталкиваясь от различных первичных понятий. Здесь можно выделить несколько наиболее принятых подходов. Первый из них исходит из того, что комбинаторика занимается расчетом различного рода выборок или расположений в определённом порядке каких-либо элементов, предметов, объектов.

Другой подход под комбинаторикой понимает изучение распределений (размещений) объектов некоторой совокупности по ячейкам (ящикам, урнам и т.п.). Иными словами, считается, что комбинаторика занимается расчетом числа способов (вариантов) размещения частиц (шаров, предметов) с определенными свойствами (например, различимые частицы, неразличимые частицы) по ячейкам с определёнными свойствами (например, ячейки разного цвета) при определённых способах размещения этих частиц по ячейкам (например, в одной ячейке не может находиться более одной частицы и др.).

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

Представление о методах комбинаторного анализа может быть дано различным образом в зависимости от реализации указанных выше подходов.

Выборки и разбиения

Рассмотрим множество или, как говорят, генеральную совокупность из n элементов a₁,a₂,...,a_n. Произвольное упорядоченное множество (a_i1,a_i2,...,a_ir) из r элементов, входящих в генеральную совокупность, будем называть выборкой объема r из этой совокупности (множества).

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

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

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

Предварительно могут быть сформулированы два вспомогательных утверждения.

Утверждение 1.

Из m элементов a₁, a₂, ..., a_m и n элементов b₁, b₂, ..., b_n можно образовать mn различных пар (a_i,b_j), содержащих по одному элементу из каждого множества.

Данное утверждение становится очевидным, если составить прямоугольную таблицу, содержащую m строк и n столбцов так, чтобы пара (a_i,b_j) стояла на пересечении i-ой строки и j-ro столбца.

Пример. Карты для игры в бридж. Элементы первого множества составляют четыре масти, элементы второго множества составляют 13 возможных значений карт (от двойки до туза). Существуй 4 · 13 комбинаций масти и значений. Поэтому число карт в колоде для игры в бридж должно быть равно 52.

Утверждение 2.

Дано r групп элементов: n₁ элементов первой группы a₁, a₂,..., a_n1; n₂ элементов второй группы b₁, b₂,..., b_n2; n_r элементов r-ой группы x₁, x₂, ..., x_nr. Можно образовать n₁·n₂· ··· ·n_r различных комбинаций (a_j1, a_j2,..., a_jr), содержащих по одному элементу из каждой группы.

Пример. Сложная классификация. Пусть люди классифицируются по полу, семейному положению и профессии. Если рассматривается 10 возможных профессий, то получим 2·2·10=40 различных классов.

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

Подсчитаем теперь число возможных различных выборок при выборе с возвращением. Применим утверждение 2 при n₁=n₂=...=n_r=n, получим, что это число равно U(n,r) = n^r.

Пример. Число различных способов перфорации r-позиционной телетайпной ленты равно 2^r. На ленте любая из r позиций замещается одним из двух "элементов" - перфорацией (пробитым отверстием) или отсутствием его.

Пример. С помощью восьми байтового представления можно "закодировать" 2⁸=256 символов.

В случае выборки без возвращения необходимо применить утверждение 2 при n₁ = n, n₂ = n - 1, n₃ = n - 2, ..., n_r = n – r +1. В результате получаем, что число возможных различных выборок без возвращения равно n(n - l)(n - 2) · · · (n – r +1). Так как подобное произведение встречается довольно часто, то для него существуют специальные обозначения:

Рассмотрим частный случай, когда объем выборки r совпадает с объемом генеральной совокупности n, n = r. В этом случае множество выборок без возвращения совпадает с множеством способов упорядочения (перестановок) этих элементов. Отсюда следует, что n элементов a₁,a₂,...,a_n можно упорядочить (n)_n = n(n-1)·... ·2·1 различными способами.

Итак, получен следующий результат. Число различных перестановок из n элементов равно (n)_n. Для (n)_n есть специальное обозначение (n)_n = n(n-1)·... ·2·1= n!

Обозначение n! читается как n-факториал. По определению 0! = 1.

Пример.

1! = 1,

2! = 2·1 = 2,

3! = 3·2·1 = 6,

4! = 4·3·2·1 = 24.

Пример. Дни рождения. Дни рождения r людей образуют выборку объема r из генеральной совокупности всех дней в году. Не все годы имеют одинаковую длину, и известно, что рождаемость в течение года не вполне постоянна. Пренебрегая этим, будем считать, что в году число дней постоянно и равно N=365. Подсчитаем общее число распределений дней рождения r человек. Очевидно, это есть выборка с возвращением объема r из N элементов, число таких выборок, как установлено выше, равно N^r. Подсчитаем теперь число распределений дней рождения r человек при условии, что все эти r человек родились в разные дни. Очевидно, это есть число выборок объема r из N элементов без возвращения и поэтому оно равно (N)_r. Так для примера r = 23 будем иметь (N)r = (365)₂₃ = 365· 364· 363· ··· ·343 = 36523.

До сих пор при получении выборок учитывался порядок расположения элементов в выборке. Иными словами, выборки считались различными, если они отличались не только составом элементов, входящих в выборку, но и порядком расположения этих элементов. Например, выборки объема r = 4 различны как в случае (2,3,5,1), (2,3,5,4), так и в случае (2,3,1,5), (2,3,5,1).

Если не учитывать порядок элементов в выборках, то две выборки будут считаться различными только в случае, если в одной из них содержится хотя бы один элемент, не содержащийся в другой. Теперь выборки (2,3,1,5) и (2,3,5,1) одинаковые и обе они одинаковы с выборкой (1,2,3,5). В числовых выборках без учета порядка входящих в них элементов принято располагать элементы в порядке возрастания.

Подсчитаем число выборок объема r из n элементов, в которых не учитывается порядок расположения элементов выборки. Очевидно, что из одной выборки объема r без учета порядка (неупорядоченной выборки) можно получить r! упорядоченных выборок. Поэтому, если обозначить через х число неупорядоченных выборок, число упорядоченных выборок будет равно х·r! С другой стороны нам уже известно, что количество упорядоченных выборок объема r из n элементов равно (n)_r, откуда следует:

В отечественной литературе количество неупорядоченных выборок объема r из n элементов обозначается символом . В зарубежной литературе принято обозначение . Таким образом:

Числа называются биномиальными коэффициентами. Сами неупорядоченные выборки объема r из n элементов носят название сочетаний из n элементов по r.

Пример. Сочетания из 5-ти элементов {1, 2, 3, 4, 5} по 2.

12 13 14 15

23 24 25

34 35

45.

Их количество равно:

Для обозначения количества упорядоченных выборок объема r из n элементов используется термин - размещения из n элементов по r и ранее введенный символ:

Таким образом, из n элементов можно получить упорядоченных выборок без возвращения по r элементов в каждой. С другой стороны из n элементов можно способами выделить группу в r элементов без учета этих элементов.

Выбор без учета порядка r элементов из совокупности в n элементов эквивалентен выбору (без учета порядка) оставшихся (n–r) элементов. Поэтому очевидно, что имеет место соотношение:

.

Это соотношение подтверждается и равенством:

Пример. Бридж и покер. При игре в бридж каждый из 4-х игроков получает 13 карт из колоды в 52 карты. При игре в покер каждый игрок получает 5 карт. Так как порядок карт на руках несущественен, то количество способов получения каждым из игроков карт при игре в бридж равно:

а при игре в покер:

Рассмотрим теперь состав выборки объема r из числовой генеральной совокупности из n элементов с возвращением. Пусть, например, n =2, r =3, все n^r = 2³ = 8 выборок представлены ниже:

111, 112, 121, 211, 222, 221, 212, 122.

Разобьем эти восемь выборок на следующие классы:

{111}, {222}, {112, 121, 211}, {122, 212, 221}.

Общее, что объединяет выборки в каждом классе, это постоянный состав - постоянное количество элементов разного вида, в первом классе r₁ = 3, r₂ = 0 (три единицы, ноль двоек), во втором классе r₁ = 0, r₂ = 3 (ноль единиц, три двойки) , в третьем классе r₁ = 2, r₂ = 1 (две единицы, одна двойка), в четвертом классе r₁ = l, r₂ = 2 (одна единица, две двойки), при этом r₁ + r₂ = r во всех классах (суммарное количество различных элементов в каждом классе постоянно и равно трем).

В общем случае произвольных n и r все выборки n^r объема r из n элементов с возвращением также можно разбить на классы (множества) с фиксированным составом:

(r₁ , r₂ ,..., r_n ), причем r₁ + r₂ +...+ r_n = r . Поставим вопрос, сколько имеется выборок в классе с фиксированным составом n, r₁ , r₂ ,..., r_n.

Обозначим это число С_r(r₁, r₂ ,..., r_n).

Рассмотрим одну из выборок с составом (r₁, r₂ ,..., r_n), заменим в ней все одинаковые элементы разными. Тогда количество выборок, которые может быть получено из рассматриваемой выборки равно r₁!·r₂!·...·r_n!.

Действительно, переставляя теперь всеми возможными способами элементы, ставшие разными, мы получаем новые выборки, число которых определяется числом всевозможных перестановок r₁!·r₂!·...·r_n!. Проделаем эту операцию для каждой из выборок С_r(r₁, r₂ ,..., r_n).

Очевидно, таким образом мы получим все перестановки из r элементов, их всего r!. Итак, имеем соотношение для вычисления С_r(r₁, r₂ ,...,r_n) · r₁!·r₂!·...·r_n! = r!, откуда получаем искомую формулу

Пример. Количество различных последовательностей букв, которые можно составить из 12 букв (4 буквы «а», 4 буквы «б», 2 буквы «в», 2 буквы «г») равно С₁₂(4,4,2,2) = 207900.

Рассмотрим теперь вопрос, на сколько же таких классов разбиваются все n^r выборок. Любой набор r₁, r₂ ,..., r_n удовлетворяет условиям r₁ + r₂ +...+ r_n = r и0 < r_i , .

Поэтому число классов равно числу решений в целых неотрицательных числах уравнения: x₁ + x₂ +...+ x_n = r.

Рассматриваемые нами n^r выборок являются упорядоченными выборками объема r из n элементов с возвращением.

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

В рассмотренном выше примере n = 2, r = 3, чтобы получить все неупорядоченные выборки, мы можем получить все 2³ = 8 упорядоченных выборок, а затем каждую из них реупорядочить (т.е. расставить элементы в порядке возрастания) и затем взять только различные выборки. При этом очевидно, что реупорядочивать можно только выборки, состоящие из различных элементов; реупорядоченные выборки нашего примера представлены ниже:

{1,1,1}, {2,2,2}, {1,1,2}, {1,2,2}. Мы видим, что таких неупорядоченных выборок столько же, сколько введенных нами классов выборок с фиксированным составом.

Неупорядоченные выборки объема r из n различных элементов с возвращениями носят специальное название сочетания с повторением. Число сочетаний из n элементов по r с повторениями обозначается . Таким образом, равно числу классов с постоянным составом (r₁, r₂ ,..., r_n) и равно числу решений приведенного выше уравнения.

Попробуем найти число сочетаний с повторениями , используя построение соответствия между множеством сочетаний с повторениями и множеством обычных сочетаний с различными значениями параметров n, r.

Рассмотрим любое из r - сочетаний с повторениями из n элементов, пусть оно имеет вид (α₁, α₂ ,..., α_r), в этом сочетании вследствие возможности повторений некоторые рядом стоящие элементы могут быть одинаковыми. Поэтому построим из последовательности элементов (α₁, α₂ ,..., α_r) последовательность элементов (d₁, d₂ ,..., d_r) с помощью соотношений

d₁ = α₁ + 0, d₂ = α₂ + 1, ... d_i = α_i + i - l,... d_r = α_r + r - l.

Очевидно, при любых элементах α_i элементы d_i всегда различны и последовательности из элементов α_i и d_i находятся во взаимнооднозначном соответствии. Но количество последовательностей из элементов {d_i, } легко считается: оно равно обычному (без повторений) числу сочетаний по r из элементов с номерами от 1 до n + r - 1, т.е. . Итак

Например, 4 -м сочетаниям с повторениями из 2 -х элементов

111, 112, 122, 222 соответствуют 4 сочетания из элементов d_i

123, 124, 134, 234.

Покажем теперь, что действительно число сочетаний с повторениями является числом решений уравнения

x₁ + x₂ +...+ x_n = r.

Пусть имеем целые неотрицательные числа r₁, r₂ ,..., r_n, такие, что r₁ + r₂ +...+ r_n = r, тогда можем составить сочетание из n элементов по r , взяв r₁ элементов первого типа, r₂ элементов второго типа, r_n - n-ого типа. Наоборот, имея сочетание из n элементов по r , получим решение уравнения r₁ + r₂ +...+ r_n = r (r₁ - число элементов первого типа, r₂ -второго типа,..., r_n - n-го типа) в целых неотрицательных числах. Следовательно, между множеством всех сочетаний из n элементов по r с повторениями и множеством всех целых неотрицательных решений уравнения

r₁ + r₂ +...+ r_n = r установлено взаимно однозначное соответствие. Поэтому число решений этого уравнения равно:

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

Зашифруем каждую покупку с помощью нулей и единиц. А именно, сначала напишем столько единиц, сколько куплено наполеонов. Потом, чтобы отделить наполеоны от эклеров, напишем нуль, а затем - столько единиц, сколько куплено эклеров. Далее снова напишем нуль, если не было куплено ни одного эклера, то в записи появятся два следующие друг за другом нуля. Далее напишем столько единиц, сколько куплено песочных пирожных, снова напишем нуль, и, наконец, напишем столько единиц, сколько куплено слоеных пирожных. Например, если куплено 5 наполеонов, 2 эклера, 2 песочных и 1 слоеное, то получим такую запись: 1111101101101. Ясно, что разным покупкам соответствуют разные комбинации из 10 единиц и 3 нулей. Обратно, каждой комбинации 10 единиц и 3 нулей соответствует какая-то покупка. Таким образом, число различных покупок равно числу перестановок из 10 единиц и 3 нулей, которое равно

.

Этот пример показывает, что сочетаниям с повторениями можно дать такое толкование. Имеются предметы n различных типов, число комбинаций из r предметов, которых можно сделать из них, если не принимать во внимание порядок предметов в комбинации, и есть число сочетаний с повторениями из n типов предметов по r предметов, подсчитываемое по формуле:

.

Одновременно число сочетаний с повторениями как число решений уравнения

x₁ + x₂ +...+ x_n = r

можно интерпретировать как число разделений r одинаковых предметов на n групп или как число разделений r одинаковых предметов между n лицами.

Пример. Трое ребят собрали 40 яблок. Сколькими способами они могут их разделить?

Здесь r = 40, n = 3.

.

Рассмотрим теперь связь между выборками объема r из n элементов с возвращением и неупорядоченными выборками без возвращения.

Выборка объема r с возвращением состоит из n подвыборок объемами r₁, r₂ ,..., r_n такими, что r₁ + r₂ +...+ r_n = r, при этом подвыборка r_k , 1≤ к ≤ n, состоит из одинаковых элементов, а следовательно изменение порядка элементов в каждой такой подвыборке не меняет её. Отсюда следует, что такую выборку можно рассматривать также как выборку объема r без возвращения, но неупорядоченную. Все вместе это означает, что выборка объема r из n элементов с возвращением с составом r₁, r₂ ,..., r_n таким, что r₁ + r₂ +...+ r_n = r, может быть получена путем извлечения неупорядоченной выборки объема r₁ из r элементов, затем извлечением неупорядоченной выборки объема r₂ из оставшихся r - r₁ элементов и так далее до последней неупорядоченной выборки объема r_n из оставшихся r - r₁ - r₂ -...- r_n-1 элементов. Поэтому должно иметь место соотношение

Таким образом установлено, что выборок объема r из n элементов с возвращением всего n^r, каждая такая выборка может быть разложена на подвыборки с фиксированным составом r₁, r₂ ,..., r_n так, что r₁ + r₂ +...+ r_n = r, 0≤ r_k , , число подвыборок с таким составом равно:

Число же выборок с различным составом определяется как число решений уравнения r₁ + r₂ +...+ r_n = r в целых неотрицательных числах 0 ≤ r_k, , равное:

.

Из всего сказанного следует, что должно иметь место соотношение:

,

где суммирование производится по всем вариантам r₁, r₂ ,..., r_n таким, что r₁ + r₂ +...+ r_n = r, 0≤ r_k , .

Пример. Пусть n=2, r=3, все n^r = 2³ = 8 выборок были рассмотрены выше, они таковы

{111}, {222}, {112, 121, 211}, {122, 212, 221}. Приведенная выше формула в данном случае приобретает вид:

Коэффициенты называются полиномиальными коэффициентами. Биномиальные коэффициенты являются частньм случаем полиномиальных коэффициентов при n = 2. Для биномиальных коэффициентов имеет место соотношение:

.

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

Полученные результаты могут быть переформулированы в терминах разбиения или разделения n предметов на группы.

Общее число способов, которыми n предметов могут быть разделены на k групп, равно U(k,n) = kⁿ.

В частности, n различных предметов можно разбить на две группы 2ⁿ способами.

Число способов, посредством которых n различных предметов могут быть разбиты на k групп, из которых первая содержит n₁ предметов, вторая – n₂ предметов и так далее, равно

В частности, n предметов можно разделить на две части, n = n₁ + n₂, следующим количеством способов:

Общее число способов, посредством которых n неразличимых предметов может быть разбито на k групп, равно:

.

Иногда требуется, чтобы в каждой группе было по крайней мере по одному предмету, чтобы не было пустых групп. В этом случае k предметов надо разнести в каждую группу по одному, а остальные (n-k) предметов можно разбивать на k групп произвольным образом. Очевидно, число таких способов определяется приведенной выше формулой, в которой n заменяется на n - k , то есть: .

Пример. При игре в бридж между четырьмя игроками распределяют 52 карты по 13 карт каждому игроку. Число возможных сдач или положений на карточном столе равно числу разделений 52 различных предметов на 4 группы по 13 предметов каждому; это число согласно равно:

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

Размещение частиц по ячейкам

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