Материал: erovenko_va_osnovy_vysshei_matematiki_dlia_filologov

Глава 2

КОМБИНАТОРИКА И ВЕРОЯТНОСТЬ

Взятая в цифрах, вещь может дать тамерланову тьму, род астрономии. Что под стать воздуху самому.

Иосиф Бродский

Ñтремление увидеть за словом цифры (число), представить искусство как определенного вида математику или описать его через нее берет

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

Математику как олицетворение рассудочности обычно противопоставляют поэзии, постигающей мир «иными путями». Тем не менее именно в анализе поэтического языка содержатся наиболее оправданные сопоставления элементов логики художественного и математического мышления. В стремлении к многоохватному анализу может исчезнуть сама проблема «поэзия и математика». Выделение аспектов, для анализа которых необходим математический анализ, методологически допустимо, если они не отрицают иных постановок вопросов, связанных с проблемами эстетиче- ской ценности и многозначности поэтического языка. В начале прошлого века были предприняты попытки «поверить алгеброй гармонию». Русский математик академик А. А. Марков в работе «Пример статистического ис-

следования над текстом “Евгения Онегина” иллюстрирующий связь испытаний в цепь» (Известия Императорской академии наук. СПб., 1913) провел статистическое исследование чередования гласных и согласных букв, в качестве иллюстрации к созданной им математической теории «марковских цепей». Это был неслучайный факт. Поскольку в языке можно наблюдать регулярные отношения и, кроме того, так как язык содержит поддающиеся счету дискретные единицы, то он допускает возможность математи- ческого описания. До сих пор эти факты не оказывали существенного влияния на методологию лингвистики. За исключением структурной лингвистики она оставалась эмпирической наукой.

72

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

периментов на современных вычислительных машинах с соответствую-

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

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

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

жении «тесного структурного параллелизма между фрагментами двух языков: «человеческого» языка обыденной жизни и языка ньютоновской

механики в его крайне схематизированном и топологизированном варианте»7. В этой работе Том опирался на математическую теорию, которой он дал рекламный вариант названия — «теория катастроф». В частности, он отмечал, что полная формализация естественных языков представляется невозможной по следующим причинам:

А. Если бы одновременная формализация данного языка и метаязыка, его описывающего, оказалась возможной, то как и в математике появились бы парадоксы, препятствующие полной формализации арифметики.

Б. Даже если не требовать одновременной формализации метаязыка,

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

7Òîì Ð. Топология и лингвистика // Успехи математических наук. — 1975. — Т. 30, вып. 1. — С. 199.

73

В. Наконец, само понятие «правильной составленности» в естественном языке не является ни жестко определенным, ни четко ограниченным.

Это в первую очередь относится к тем случаям, когда с языком приходится иметь дело вычислительной машине. Математические методы оказываются в этом случае необходимыми из-за того, что современные машины пока еще плохо приспособлены, для того чтобы непосредственно «понимать» язык лингвистов, которые сами понимают друг друга далеко не однозначно. Например, как говорил академик А. Н. Колмогоров: «Ñòè-

ховедение вместе со всеми филологическими дисциплинами переживает сейчас закономерный этап устремления к более точным и объективным

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

орию вероятностей и математическую статистику.

2.1. ОСНОВНЫЕ ПРИНЦИПЫ КОМБИНАТОРИКИ

Классической теории вероятностей предшествуют разделы комбинаторики. В знаменитой басне И. А. Крылова «Квартет» группа музыкантов «проказница Мартышка, Îñ¸ë, Коз¸л да косолапый Мишка» устроили любопытный эксперимент — они исследовали влияние взаимного расположения музыкантов на качество исполнения. Если бы не вмешался Соловей, участники квартета, наверное, перепробовали бы все возможные вариан-

òû. Первичная мотивация: Сколько всего способов имеется для того, чтобы рассадить в один ряд этих четырех «музыкантов»? Такого рода задачами занимается отдельная область математики, которая называется «комбинаторикой».

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

гут быть сделаны.

Некоторые комбинаторные задачи решали еще в Древнем Китае, а позднее — в Римской империи, однако как самостоятельный раздел математики комбинаторика оформилась в Европе лишь в XIII веке в связи с развитием теории вероятностей. В XX веке комбинаторику стали рассматривать как часть теории множеств, изучающей различные проблемы, возникающие при изучении конечных множеств, поскольку любую ком-

74

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

Иногда по смыслу задачи, очевидно, что существует лишь конечное число интересующих нас объектов. Они, как правило, являются определенными комбинациями других объектов, например, букв, чисел, слов и т. д. Отсюда и соответствующее название — комбинаторика (от латинского слова combinatio — соединение). Из сказанного ясно, что комбинаторика имеет дело лишь с натуральными числами и поэтому может показаться, что она более «элементарна», чем другие разделы математики. Такое впе- чатление обманчиво. Как говорил Альберт Эйнштейн: «Íå âñå, ÷òî ìîæ-

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

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

Пример. Пусть в магазине имеются 7 различных видов коробок конфет и 5 различных коробок печенья. Сколькими способами можно выбрать в подарок коробку конфет или коробку печенья? Сколькими способами можно составить набор, состоящий из коробки конфет и коробки пе-

ченья?

Ответ на первый вопрос очевиден. Коробку конфет можно выбрать 7 способами, коробку печенья — 5 способами. Следовательно, коробку конфет или коробку печенья можно выбрать 7 + 5 = 12 способами.

Для ответа на второй вопрос заметим, что если мы составляем набор из коробки конфет и коробки печенья, то к каждой из 7 различных коробок конфет можно подобрать коробку печенья 5 способами, а именно к первой коробке конфет можно подобрать 5 различных коробок печенья, но второй коробке конфет — опять 5 различных коробок печенья и т. д. Таким образом, набор, состоящий из коробки конфет и коробки печенья, можно выбрать 5 + 5 + 5 + 5 + 5 + 5 + 5 = 7 5 = 35 способами.

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

75

тесно связана с теорией конечных множеств. Такие понятия теории мно-

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

Комбинаторный принцип сложения. Если множество A содержит n разных элементов, а множество B — m разных элементов и A B = ,

то множество A B содержит n + m элементов.

Доказательство. Пересчитаем элементы объединения непересекающихся множеств A è B, ò. å. A B. Сначала пересчитаем все элементы, входящие в множество A, и дадим им номера от 1 до n, поскольку в множестве A по условию n элементов. Напомним, что среди элементов множества A нет элементов множества B, так как по условию A B = . Поэтому, когда мы перейдем к пересчету элементов, принадлежащих множеству B, то придется начать с номера n + 1, затем будут номера n + 2, n + 3 и т. д. до номера n + m, поскольку в множестве B по условию m элементов. С помощью этой процедуры подсчета элементов множества A B все они будут исчерпаны, а так как они получили номера от 1 до n + m, то, следовательно, заданное множество A B содержит n + m элементов.

Замечание. Если некоторый объект «A» можно выбрать n способами, а другой объект «B», отличный от «A», — m способами, то согласно комбинаторному принципу сложения объект «A или B» можно выбрать n + m способами.

Поясним сказанное на следующем примере.

Пример. Рассмотрим, сколькими способами студенту филфака можно выбрать одну книгу, когда на полке находятся 15 книг по философии, 10 книг по информатике и 5 книг по «математике для гуманита-

ðèåâ».

Заметим, что книгу по философии можно выбрать 15 способами, книгу по информатике — 10 способами, а книгу по «математике для гуманитариев» — 5 способами. Согласно комбинаторному принципу сложения и в силу предыдущего замечания студент филфака может выбрать одну книгу на полке 15 + 10 + 5 = 30 способами.

Комбинаторный принцип сложения по индукции можно распространить на объединение k попарно непересекающихся множеств.

Если все варианты выбора делятся на k взаимоисключающих типов, причем имеется n1 вариантов 1-ãî òèïà, n2 вариантов 2-ãî òèïà, …, nk вариантов k-ãî òèïà, то общее число вариантов равно n1 + n2 + … + nk.

76