Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007 (1119377), страница 19
Текст из файла (страница 19)
Иезуитский священник Бернард Баухуис (Вегпагс! ВаиЬшв) сочинил однострочную хвалу Деве Марии в вяде латинского гекзаметра: ТоС БЫ випС г)оСев, т'!гйо, ссиоС вЫега сш!о. (19) 107 ТоС с!огеэ БЬЬ циоС сю!о випС зЫега, 1г!гбо. 270 ВоСев СоС, сш1о випС зЫега сСиоС, БЫ Мгбо. 329 ВоСев, сю!о эипС циоС вЫега, Игйо С1Ы сос. 384 БЫега срюС сее1о, СоС випС мийо БЫ с)огеэ.
725 ь)иос сее1о випс эЫега, сос У!гбо с1Ь! 6осш. 949 Бипс с(осев т'пйо, с!нос в!бега, сос с!Ы сее!о. 1022 БипС сш!о СоС Игбо БЫ, йиоС вЫега, доСгн. (20) Он остановился на 1022 перестановках, потому что 1022 — количество видимых звезд, перечисленных в знаменитом каталоге Птолемея (Рсо1ету). Идея такой перестановки слов была хорошо известна в то время; эту игру слов в своей книге РоеВсе ИЬг! бергот (1,уоп, 1561), Воо1с 2, СЬарСег 30, Юлиус Скалигер (ЗиЬив Бсайбег) назвал "Стихами-хамелеонами" (РгоСеиэ тегэея). Латинский язык приспособлен для перестановок наподобие (20), поскольку окончания латинских слов зачастую выражают грамматическое значение существительного, делая относительный порядок слов существенно менее важным для смысла предложения, чем, например, в английском языке.
Путеанус указал, однако, что он специально избегал неподходящих перестановок, например БЫега сос сш!о, ЪЧщо, с!нос эипс БЬ1 г!осев„ поскольку они указывают не нижнюю, а верхнюю границу количества достоинств Девы Марии. !См. с. 12 и 103 книги Путеануса.1 Существует всего 8! = 40320 способов перестановки слов в строке (19). Но цель состоит не в том, чтобы получить нх все — большинство из них "нечитаемо". Каждый же из 1022 стихов Путеануса соответствует строгим правилам классического гекзаметра, которым следовали греческие и латинские поэты со времен Гомера и Вергилия: !) каждое слово состоит нз длинных ( — ) или коротких ( ) слогов; й) слоги каждой строки принадлежат одному из 32 шаблонов: (::1(:-1(::Н:- )--(-) сделано для ссгсяснЛсс$ассаса.ого ["У тебя столько добродетелей, Дево, как звезд на небе"; см.
Б)нйгапппагит ИЬп' сг (Со!ойле, 1616), 49.) Его стих побудил Эрикуса Путеануса (Егусшэ Рисеапив), профессора университета в Лувене (Пп!тегз1су оП оитасп), написать книгу Р!есас!я ТЬаитаса (Апснегр, 1617), в которой он представил 1022 перестановки слов Баухуиса. Например, у Путеануса имеются следующие варианты: 84 КОМБИНАТОРНЫЙ ПОИСК 7.2.1 Другими словами, имеется шесть метрических стоп, причем каждая из первых четырех может быть либо дактилем, либо споцдеем в терминологии (5); пятая стопа должна быть дактилем, а последняя — трохеем или спондеем.
Правила для определения длинных и коротких слогов в латинской поэзии в общем случае достаточно запутанны, но восемь слов Баухуиса соответствуют следующим шаблонам: тос = —, ПЬ1 =, эппс = —, догея = — —, Ъ'1гйо =, Опог = —, э16ега = — —, сю)о = — —. (23) Обратите внимание, что у поэтов есть по два варианта при использовании слов 'ПЬР и ' г 1гйо'. Таким образом, например, строка (19) соответствует шаблону гекзаметра (24) ТоФ Н-Ь1 эппс Йо- Гез, ХЛг- бо, цпог врбе-га са. 1о.
(Дактнль, спондей, спондей, спондей, дактиль, споидей; "там-тата там-там там-там там-там там-тата там-там". Запятые представляют небольшие паузы при чтении стиха„именуемые цезурами (сювпга); здесь они на рассматриваются, хотя Путевнус аккуратно вставил их в каждую из 1022 перестановок.) Возникает естественный вопрос: если переставить слова Баухуиса случайным образом, каковы шансы на то, что они будут гекзаметром? Иными словами, сколько перестановок подчиняются правилам (1) и (й) с учетом шаблонов из (23)? Г.В.
Лейбниц (С.%. 1 е1Ьшг) рассматривал этот вопрос среди других в своей работе 111яэег1ано де Аг1е СошЫпаГог1а (1666), опубликованной„когда он претендовал на место в университете Лейпцига (Пп1гегэйу оП е1рящ). В это время Лейбницу было только 19 лет, и по большей части он был самоучкой, так что его понимание комбинаторики было весьма ограниченным; например, он считал, что имеется 600 перестановок множества (до, до, ре, ми, фа, соль) и 480 — множества (до, до, ре, ре, ми, фа), и даже утверждал, что (22) представляет 76 вариантов, а не 32 (см. Ц 5 н 8 в его задаче 6), Однако Лейбниц понимал, что следовало бы разработать общие методы для подсчета всех "подходящих" перестановок в ситуациях, когда многие подстановки таковыми не являются.
Он рассмотрел несколько примеров стихов-хамелеонов, корректно проведя подсчеты для более простых и наделав массу ошибок там, где слова оказывались слоэкнее. Хотя Лейбниц и упомянул работу Путеануса, ои не пытался подсчитать количество гекзаметров среди перестановок строки (19). Существенно более успешный подход был предложен несколько лет спустя Жаном Престетом (Левп Ргея1ес) в работе Йешепв дев МаГЬ4ша119пез (Раня, 1675), 342— 438. Престет привел рассмотрение данного вопроса, из которого вытекало наличие ровно 2196 перестановох слов хвалы Баухуиса, являющихся гекзаметрами.
Однако вскоре он обнаружил, что упустил некоторое количество случаев, в частности случаи 270, 384, 725 нз (31). Поэтому он полностью переписал данный материал при переиздании книги Хоигеапх Ййшепв дез МагЬ4шандиез и 1689 году. На с. 127 — 133 новой книги Престет показывает, что правильное количество перестановок-гекза.- метров равно 3276, что почти на 50% превышает ранее указанное им число. сделано для мгьпидп?апаса.ого 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМБИНАТОРНЫХ ОБЪЕКТОВ 85 Тем временем Джон Уоллис (ЗоЬп %айв) рассмотрел данную задачу в работе !7!всоигве от" СошЬ!паяопв (1 опбоп, 1685), 118-119, опубликованной в качестве дополнения к его книге 2геаяве от А)яеЬга.
Объяснив, почему он считает, что корректное количество равно 3096, Уоллис допустил предположение, что он мог упустить некоторые варианты и/или сосчитать другие более чем по одному разу; "однако в настоящее время я не заметил за собой ни того, ни другого". Анонимный критик работы Уоллнса указал, что верное количество перестановок составляет 2580, но не двл никакого доказательства этому факту (Асга Его!гогитп, 5 (1686), 289). Этим критиком почти наверняка был Лейбниц, хотя никакого ключа к пониманию числа 2580 среди его многочисленных неопубликованных заметок найдено не было. Наконец, на сцене появляется Я.
Бернулли, в инаугурационной лекции которого при вступлении в должность декана факультета философии университета Базеля (Вп!тегв!!у о! Ваве1) в 1692 году была упомянута данная задача и сказано, что аккуратный анализ дал корректный ответ, равный 3312(!) перестановкам. Доказательство Бернулли было опубликовано посмертно в первом издании Агв Соп)есглпой (1713), 79-81.
[Эти страницы, кстати, были опущены в более поздних изданиях этой знаменитой книги и в сборниках работ Бернулли, поскольку изначально он не предназначал их для публикации; редактор внес их в книгу по ошибке. См. В!е Игег(ге топ,7акоЬ Вегпои!Ь', 3 (Вазе!: В!гЬЬаивег, 1975), 78, 98-106, 108„154-155.) Так кто же был прав? Сколько же гекзаметров среди перестановок — 2196, 3276, 3096, 2580 или 33127 В.А. Уитворт (%,А. 'тт'Ь!!эгогФЬ) и В.Э. Хартли (%.Е. Наг!!еу) заново рассмотрели этот вопрос в ТЬе Матйегпаг!са! Савеые, 2 (1902), 227 — 228, где каждый из них представил элегантные доказательства и сделал выводы, что ни одно из предложенных чисел ие является корректным ответом.
Их общим решением было 2880, и это был первый случай, когда два математика независимо получили одно и то же решение данной задачи. Но из упражнений 21 и 22 вы узнаете истину: прав был только Бернулли, все остальные ошибались. Кроме того, изучение трехстраничного вывода Бернулли указывает, что он был успешен в основном потому, что автор строго придерживался метода, который сейчас называется методом с вовврашвм (Ьас!гггас!г ше!Ьог!). Мы тщательно изучим этот метод в разделе 7.2.2, где также узнаем, что рассматриваемая здесь задача легко решается как частный случай видачи пючного иокрмшил (ехас! совет ргоЫеп1).
Даже мудреншие н осторожнейшне люди часто страдают от того, что логики называют неполным перечислением возможностей. — Якоб Бернулли !'.!атея Вегпоийу) (!б92) Разбиения множества. Похоже, впервые разбиения множеств изучались в Японии, где в конце ХУ вЂ” начале ХИ веков среди высших классов стала популярна игра генджи-ко (йеп11-Ьо). Ведущий должен скрытно выбрать пять пакетов фимиама, причем некоторые из них могут быть одинаковы, и по очереди воскурить их.
Игроки должны попытаться определить, какие запахи были одинаковы, а какие различны — словом, угадать, какое из иге = 52 разбиений множества (1, 2, 3„4, 5) выбрано ведущим. сделано для ыгвлуАя!апаса.огя 86 КОМБИНАТОРНЫЙ ПОИСК Рис, 47. Диаграммы, использовавшиеся для представления разбиений множества в ХЪ'1 веке в Японии (копия из коллекции Тамаки Яно (Таша1о Ъ'епо) нз университета Сантами) Вскоре стало привычным изображать 52 возможных варианта с помощью диаграмм, подобных приведенным парис.
47. Например, верхняя диаграмма при чтении справа ивлево указывает, что одинаковы два первых запаха и три последних, т.е. это разбиение 12 ~ 345. Две другие диаграммы представляют соответственно разбиения 124 ( 33 и 1 ) 24 ! 35. Чтобы помочь запоминанию, каждый из 52 шаблонов получил свое название благодаря знаменитой книге Х1 века г-жи Мурасвки (МпгаааЫ) Рассказ о генджи„в соответствии с приведенной ниже последовательностью )Епсус1орейа Хъроп1сю (Токуо: ВапвеЫо, 1910), 1299). Ш11 !!!3!6! 10 6!! !6! 1!6 !!!!! 6!! 1В Ф6!61 Ш!! 6!! !6! Йн! Ш!1 Ш!! 61! 6!1 !!6 61 ~~В 6!1!16 16! !!Ш й~ Ы! ГФ !!6 16! !!Ш 6!! !!6 6!! !!6 й й Й пй 16! Гб 6!! Пп! Ш!! 1П! Л! !!6 6!! Е6 61! (Как и во множестве других примеров, варианты здесь перечислены без какого-то логичного порядка.) П ивлекательная прирг да шаблонов генджи-ко привела к тому, что многие семьи р использовали нх в качестве геральдических символов.
Например, ниже приведены стилизованные версии (25), которые были найдены в стандартном каталоге узоров к~и~но на~ела ХХ века: [См. гпш)е АдасЫ„,)арапже Оещп Мос1й (г1ен Ъогк: Вотег, 1912), 150-153.) сделано для таги и,111$ииа1н.ого 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМБИНАТОРНЫХ ОБЪЕКТОВ 87 В начале ХУП1 века Такаказу Секи (Тайайаэц БеЫ) со своими учениками приступил к изучению количества разбиений множества ш„для произвольного п, вдохновленный известным результатом шэ = 52.
Ешисуке Мапунага ( тоэЬ1эцйе Масеппайа) нашел формулы для количества разбиений множества, когда имеется Йу подмножеств размером пэ для 1 < 1 < 1, и й1п1 + ° + оп~ — — и (см. ответ к упражнению 1.2.5-21). Он также открыл базовое рекуррентное соотношение 7.2.1.5-(14), а именно шч+1 = я~а+ пЪ-1+ юе-х+'''+ шо, (26) при помощи которого легко вычислить значения ш„. Открытия Мацунаги остались неопубликованными до выхода в 1769 году книги Ериюки Аримы ( топупЫ Апта) Яйй1 Бапрб. Задача 56 из этой книги состоит в решении уравнения "т„= 678570" относительно и. Детальное решение Арины (с надлежащими благодарностями Мацунэге) дает ответ и = 11.
Вскоре после этого Масанобу Сака (МаэапоЬп Вайа) изучал количество ( чь ) сцособов разбиении множества из и элементов на й подмножеств в своей работе БапроОаййш' (1782). Он открыл рекуррентную формулу (27) и протабулировал результаты для и < 11. Джеймс Стирлинг (Лашеэ Бйг11пй) в своей Работе МеГЬодпэ Глйегепй1айэ (1730) откРыл числа ( чь ) в чисто алгебРаическом контексте; таким образом, Сака был первым, кто осознал их комбинаторную важность.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
