Задача о беспорядках и формула включения-исключения: от Монмора до наших дней

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

Первые предпосылки к использованию формулы включения-исключения можно найти в работах Блеза Паскаля и Пьера де Ферма. Однако явного формулирования этого принципа в то время ещё не было. Французский математик Пьер Монмор впервые явно применил идею принципа включения-исключения для анализа карточной игры «Treize», в которой игрок выигрывает, если ни одна из 13 вытащенных наудачу карт не совпадает со своим порядковым номером [1, 2]. Это стало одним из первых примеров применения формулы включения-исключения, пока еще без явной формулировки.

Английский математик Абрахам де Муавр в своей работе « The Doctrine of Chances »

(1718) независимо от Монмора использовал принцип включения-исключения для решения задач теории вероятностей. В книге он рассматривал задачи, где нужно было вычислять вероятности объединения нескольких событий, например, вероятность того, что хотя бы одна из нескольких костей выпадет определённым образом. Однако в наше время авторство постановки задачи о беспорядках и определение формулы для вычисления их количества через применение формулы включения-исключения приписывают Леонарду Эйлеру (1707-1783). В XIX веке принцип включения-исключения был окончательно сформулирован и стал стандартным инструментом в комбинаторике и теории вероятностей.

Пьер Монмор, полное имя Пьер Ремон де Монмор, был французским математиком. Он родился 27 октября 1678 года в Париже и умер 7 октября 1719 года. Монмор известен своими работами в области теории вероятностей и комбинаторики. Его наиболее известная работа – это книга «Essay d'analyse sur les jeux de hazard» (Аналитическое исследование азартных игр), опубликованная в 1708 году (второе издание в 1713) [2]. В этой книге он рассмотрел различные аспекты теории вероятностей, включая анализ азартных игр, таких как карточные игры и игры в кости. Монмор также ввёл понятие «перестановка» и изучал их свойства, что стало важным вкладом в комбинаторику. Так же в этой книге Пьер Монмор исследовал задачу о встрече (или задачу о совпадениях, Probleme des rencontres).

В разделе «Problème divers sur le jeu de Treize» [2, с. 54] Монмор рассматривает карточную игру, где игроки по очереди вытягивают карты из колоды, и вычисляет вероятность того, что никто не вытянет свою собственную карту (аналог современных «беспорядков»). Формулировка задачи в книге Мон-мора: «Пьер держит определённое количество различных карт, которые не повторяются и перемешаны в произвольном порядке: он заключает пари с Полем, что если будет вытягивать их по очереди, называя их в порядке рангов (начиная либо с самой старшей, либо с самой младшей), то хотя бы один раз вытянет ту карту, которую назвал. Например, если у Пьера на руках четыре карты иметь туз, двойку, тройку и четвёрку, перемешанные в произвольном порядке, [Пьер] парирует, что, вытягивая их по очереди и называя "один", когда тянет первую, "два" – когда вторую, "три" – когда третью, с ним произойдёт одно из следующих событий:

• -    вытянуть туз, когда он назовёт "один",

• -    вытянуть двойку, когда назовёт "два",

• -    вытянуть тройку, когда назовёт "три",

• -    или вытянуть четвёрку, когда назовёт "четыре".

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

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

RemAR QjJ Е I,

L A folution precedence fournitun ufage fingulicr des nombres figures, done je parlerai dans la fuite, car jc trouve en examinant la formule, que Ie fort de Pierre eft exprimc par une fuite infinie de ternies qui ont alter-nativement +&■—, & tels que le numcrareur eft la fuite des nombres qui competent dans la Table, page So, la coionne perpendiculaire qui repond a p, cn commencanr parp,&le denominateur lafuite des produirsp x p— i x p — i x p— J xp —4 xp— j; en forteque ces produits qui fe crouvent dans le numerateur & dans le denoniina-reurtedctruifints,ii reftepour expreffion du fort de Pierre cette fuite tres fimple |—п *гЬ“ Г77П * "^75 __——2_— ц. &c. (ces points font ici & teront dans la fuite la marque de produits).

Рис. Фрагмент книги « Essay d'analyse sur les j'eux de hazard »

Для решения этой задачи он вывел рекуррентную формулу и составил таблицу ее значений:

M = (n - 1)-(Mn-1 +Mn-2), где М - число способов, где ни одна карта не осталась на своём первоначальном месте,

M n -1 и M n -2 - числа для n — 1 и n — 2 карт, соответственно.

Таким образом, Монмор формулирует задачу о беспорядках в терминах карточной игры и не выводит явную формулу подсчета их числа через принцип включения-исключения, но его рекуррентное решение эквивалентно современному представлению формулы ! n =( n —1)-(!( n —1)+!( n —2)), которая стала впоследствии называться субфакториалом.

В отличии от работ Монмора, Леонард Эйлер абстрагировал задачу о беспорядках до

In = nl(1 - 1 + 1 - 1 + -+ (-1)ⁿi) , 1!    2!    3!                       n!/

которая следует из принципа включения-исключения. Следуя этому принципу, сначала он вычитал количество перестановок, в которых хотя бы один элемент остаётся на своём месте. Затем добавлял обратно количество перестановок, в которых хотя бы два элемента остаются на своих местах (так как они были вычтены дважды). Продолжал этот процесс, чередуя вычитание и добавление для перестановок с тремя, четырьмя и так далее фиксированными точками. В оригинале работы Эйлера формула выглядит следующим образом:

« Если мы обозначим число перестановок n элементов, где ни один элемент не остаётся на своём месте, как N, то :

N=n!-n!/1!+n!/2!-n!/3!+ -±n!/n!

Это следует из принципа, который я называю взаимной компенсацией избыточных подсчётов » [3,с.259].

Однако ни Монмор, ни Эйлер еще не ввели в обращение термин субфакториал ! n . Его автором стал британский математик Уильям Аллен Уитвортв работе «Choice and Chance» в 1867году: «Мы будем называть !n субфакториалом n, так как он подчиняется правилам, подобным факториалу, но с чередующимися знаками» [4].

Эйлер также заметил, что при увеличении n отношение числа беспорядков к общему числу перестановок стремится к 1/ e , где e — основание натурального логарифма ( e -2.71828). Это связано с тем, что ряд в формуле (1) является частичной суммой ряда Тейлора для e ^—1: lim — = ¹ .

пчм и! в

Таким образом, первенство в постановке задачи о беспорядках в контексте теории игр чистой комбинаторики и представил явную формулу для подсчета их числа в своей работе «Calcul de la probabilité dans le jeu de ren-contre» («Расчёт вероятности в игре встреч»), которая была опубликована в Mémoires de l'Academie des Sciences de Berlin [3].

Эйлер установил, что число беспорядков n (количество перестановок n элементов, в которых ни один элемент не остаётся на своём месте) можно вычислить по следующей формуле:

сформулировал Монмор, а Эйлер решил ее в общем виде, вывел явное представление числа беспорядков через формулу (1) и установил ее связь с е .

Так же первенство Монмора в постановке задачи, которая мы теперь знаем под названием задача о беспорядках, в своей книге « A History of the Mathematical Theory of Probability » (1865) подтверждает известный историк математики Исаак Тодхантер. В этой книге глава 11 была посвящена Пьеру Ремону де Монмору и его основному труду « Essay d’Analyse sur les Jeux de Hazard ». Тодхантер отмечает, что Монмор не дал строгих доказательств некоторых утверждений, но:" The solutions given by Montmort, though sometimes wanting in generality, exhibit considerable ingenuity, and served to advance the science by stimulating further research ." («Решения, данные Монмором, хотя иногда и лишены общности, демонстрируют значительную изобретательность и послужили развитию науки, стимулируя дальнейшие исследования») [5]. А его работа стала мостом между ранними исследованиями (Паскаль) и строгой теорией (де Муавр, Лаплас).

В общем виде задачу о беспорядках можно найти в работе другого известного математика - Пьера-Симона Лапласа. В своей работе «Аналитическая теория вероятностей» ( Theorie Analytique des Probabilities , 1812) он рассматривает задачу о перестановках без неподвижных точек в контексте теории вероятностей.

Однако во многих учебниках по перечислительной комбинаторике до сих пор задача о беспорядках записана как задача Леонарда Эйлера, в следующей формулировке: «На вечеринке n гостей оставляют свои шляпы в гардеробе. После вечеринки каждый гость случайным образом берёт одну шляпу. Какова вероятность, что ни один гость не получит свою собственную шляпу?» Хотя нет подтверждений о том, что именно Эйлер привел такую формулировку "задачи о шляпах", именно под таким названием она сейчас широко известна.

Сам принцип включения-исключения, как он известен сегодня, развивался постепенно, начиная с работ Абрахама де Муавра (XVIII век) и позже был обобщён и уточнён другими математиками, такими как Огюстен Луи Коши и Пьер-Симон Лаплас. Название "  включение - исключение " закрепилось в математике благодаря работам Джеймса Джозефа Сильвестра, но важно уточнить, что сам Сильвестр не всегда использовал этот точный термин. Однако его работы 1850-1880-х годов систематизировали принцип и привлекли к нему

l^u^u-uAJ = ZdAl—WA ^Л'1

A2 П-ПАД

Глэшер писал: « Этот метод основывается на последовательном исправлении избыточного учёта элементов. Если элемент принадлежит ровно k множествам, то в итоговой сумме он будет подсчитан ровно один раз» и иллюстрирует его применение на задаче : "Сколько чисел от 1 до 100 не делятся ни на 2, ни на 3, ни на 5?" .

Монмор в своей работе [2], по сути, использовал эту формулу (2) для решения задачи о беспорядках, где множества A i представляли собой перестановки, в которых i -й элемент остаётся на своём месте.

В России популяризатором задачи о беспорядках был Николай Яковлевич Виленкин -известный советский и российский математик, автор множества учебников и популярных книг по математике, включая книги по комбинаторике и теории вероятностей. В своей работе [10] он использовал формулировку задачи о беспорядках без привязки к предметам, и предлагал использовать метод включений-исключений для ее решения при помощи формулы (2).

внимание [6]. Сильвестр применяет комбинаторные методы, включая прообраз принципа включений-исключений, для задач о разбиении чисел. Хотя сам термин " включение – исключение " явно не используется, логика метода явно прослеживается. Но первое строгое математическое доказательство и формулировка принципа включения-исключения появились лишь в конце XIX века в работах Джеймса Уитбреда Ли Глэшер "On the principle of inclusion and exclusion" , опубликованной в 1871 году в журнале The Quarterly Journal of Pure and Applied Mathematics [7]. В этой работе Глэшер дал строгое математическое обоснование принципа включения-исключения для конечных множеств, используя методы математической индукции и представил его виде, в котором он используется в настоящее время во всех учебниках [8, 9].

Если A i , A 2 ,...,A n - конечные множества, то мощность их объединения вычисляется по формуле:

+ Yi

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

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

Особенно значительный вклад в современное применение принципа включения-исключения внес Джан-Карло Рота (19321999), который обобщил его с помощью теории обращений Мёбиуса для частично упорядоченных множеств. Этот подход не только систематизировал предыдущие результаты, но и открыл новые возможности для применения в теории геометрических решеток и изучении матроидов. Джан-Карло Рота в своей работах [11] показывает, как классическая формула включений-исключений для множеств вытекает из обращения Мёбиуса на булеане 2X и в своих лекциях по комбинаторике, изданных в "Indiscrete Thoughts", пишет: «Принцип включений-исключений — это замаскированная функция Мёбиуса для булеана. Любое комбинаторное обращение есть его тень.» Работа Роты выявила глубокие связи между комбинаторикой, алгеброй и топологией, повлияв на развитие геометрической вероятности и стохастических процессов. Его серия из десяти статей по «Основаниям комбинаторики» в 1960-х годах сделала комбинаторику важным разделом современной математики.

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

В XXI веке развитие принципа включения-исключения включало его адаптацию для решетных методов в теории чисел (работы Эрдёша и Тао), а также использование при определении топологических инвариантов через характеристику Эйлера. Современные математики уже используют этот принцип в нетривиальных контекстах. Например, Катерина Мунанье – современный математик, работающая на стыке вероятностных методов, теории случайных графов и машинного обучения. Хотя её имя не столь широко известно, как имена классиков, её исследования содержат применение принципа включений-исключений. В исследованиях по гигантским компонентам случайных графов (например, в моделях Эрдёша-Реньи или масштабноинвариантных сетях) принцип включений-исключений был применен при подсчёте вероятности того, что граф содержит хотя бы один связующий путь между подмножествами вершин или для учёта пересечений множеств рёбер [12]. Израильский математик Нога Алон использовал этот принцип для подсчёта числа подграфов с определёнными свойствами, оценки вероятностных характеристик графов и в задачах на покрытия множеств и трансверсали, где метод включения- исключения помогает оценить мощность объединений множеств.

Современные русские математики также не только используют принцип включений-исключений, но и активно его развивают. Профессор А.М. Райгородский (МФТИ) применяет принцип в задачах экстремальной комбинаторики и теории случайных графов, профессор С.К. Смирнов использовал в своих работах о перколяции методы включений-исключений для расчета вероятностей связности, также можно упомянуть работы профессоров Г.А. Кабатянского и А.А. Разборова, и еще много других современных авторов.

Сегодня этот принцип продолжает вдохновлять новые исследования – от машинного обучения (алгоритмы выбора признаков) до квантовой информатики, где он помогает оценивать энтропию. Принцип включения-исключения – это "мост" между классической и современной математикой. От подсчёта беспорядков у Монмора до алгоритмов машинного обучения – его универсальность обеспечила ему место в работах сотен математиков.