Проектная работа "Комбинаторные задачи"

СОДЕРЖАНИЕ

«ОСОБАЯ ПРИМЕТА» КОМБИНАТОРНЫХ ЗАДАЧ……………..…………………………3

СВЕДЕНИЯ ИЗ ИСТОРИИ……………………………………………………............................4

Комбинаторика в Древнем Китае………………….…………………...............................4

Комбинаторика в Древней Греции………………….…………………............................5

Мистики, астрологи, каббалисты………………….…………………..............................7

Комбинаторика в странах Востока…………………..………………………………….8

Liber Abaci………………………………………..……………………………………….10

Игра в кости…………………………………………………………………………….....11

Игрок и ученые………………………….……….…………………………………….....12

Новая ветвь математики……………………………………………………………….....13

Комбинаторика и шифры………………………….…………………………………....14

Анаграммы ………………………….…………..................................................................15

Иероглифы и клинопись …………………….………………...........................................17

ПЕРЕСТАНОВКИ……………………………………………………………………………...21

Решение задачи о квартете……………………………….……………………………...22

Зеркально-симметричные перестановки………….……………………………………...22

Перестановки с повторениями ………………………….…….……….………….……...23

РАЗМЕЩЕНИЯ………………………………………….……………………………………...25

Есть ли у нуля факториал? ………………………….……………………………………...25

Размещения с повторениями ………………………..……………………………………...26

Решение задачи о паспортах …………………………………………………..…………...27

СОЧЕТАНИЯ…………………………………………………………………………………...28

Задача о Лотто-Миллион …………………………………………………………….……29

Сочетания с повторениями ………………………………………………………………30

БИНОМ НЬЮТОНА …………….………………………………………………………………..32

Биномиальные коэффициенты и сочетания ………………………………………………...33

Свойства биномиальных коэффициентов…………………………………………………...34

Треугольник Паскаля……………………………………………………………………….……34

ЗАДАЧИ ПО КОМБИНАТОРИКЕ……………………………………………………………36

Задача о разбиении плоскости прямыми……………………………………………………...36

Задача о разбиении пространства плоскостями………………………………..………..37

Обобщённый факториал и числа Каталана………………………….………………….38

ЗАКЛЮЧЕНИЕ………………………………………………………………………………..40

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ…………………………………...……...41

«ОСОБАЯ ПРИМЕТА» КОМБИНАТОРНЫХ ЗАДАЧ

В знаменитой басне Крылова «Квартет» «про­казница Мартышка, Осёл, Козёл да косолапый Мишка» устроили любопытный эксперимент: они исследовали влияние взаимного располо­жения музыкантов на качество исполнения. И если бы не вмешался Соловей, участники квар­тета, наверное, перепробовали бы все возмож­ные варианты. Зададимся вопросом: сколько существует способов, чтобы рассадить, напри­мер в один ряд, четырёх музыкантов?

Другой случай. Воспетый Маяковским «молоткастый, серпастый» советский паспорт имел серию и номер, состоящие в общей слож­ности из трёх частей:

1) некоторое число, записанное римскими цифрами;

2) две русские буквы;

3) шесть арабских цифр.

Например, IХ-РГ № 062993. Разумеется, все пас­порта должны иметь разные номера. Сколько может быть различных паспортов?

Третья ситуация. Нас приглашают сыграть в Лотто-Миллион. Суть игры в том, что нужно из 49 номеров угадать б, которые выпадут во время тиража. Для участия в игре следует при­обрести специальную карточку и вычеркнуть в ней 6 любых квадратов, пронумерованных числами от 1 до 49. Чтобы выиграть наверняка, можно было бы запастись таким количеством карточек, какое необходимо для вычёркивания 6 номеров всеми возможными способами. Сколько этих способов?Общее у всех трёх задач то, что их решени­ем занимается отдельная область математики, называемая комбинаторикой. «Особая примета» комбинаторных задач — вопрос, который всегда можно сформулировать так, чтобы он начинался словами: «Сколькими способами...».

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

СВЕДЕНИЯ ИЗ ИСТОРИИ

Комбинаторика в Древнем Китае

Первое упоминание о вопросах, близких к комбинаторным, встречается в китайских рукописях, относящихся к XII — XIII векам до н. э. Точно датировать эти рукописи невозможно, поскольку в 213 г. до н. э. император Ши Хуан-ди приказал сжечь все книги (они писались на бамбуковых дощечках), так что до нас дошли лишь основанные на них более поздние книги. В этих книгах писалось, что все в мире является сочетанием двух начал — мужского и женского, которое авторы обозначали символами «—» и «- -». В рукописи, сейчас из­вестной как «Книга перемен», показаны различные соединения этих знаков по два и по три:

Восемь рисунков из трех рядов символов изображали землю, гору, воду, ветер, гром, огонь, пар и небо (некоторые рисунки имели и иные значения). Неудивительно поэтому, что сумма первых 8 натуральных чисел (т. е. число 36) воплощала в представлениях древних китайцев весь мир. По мере углубле­ния знаний понадобилось выразить и другие элементы миро­здания с помощью тех же знаков «—» и «- -». Были состав­лены 64 фигуры, содержавшие уже пять рядов черточек. Надо полагать, что удвоение числа рисунков при добавлении одного ряда символов было замечено. Это можно рассматривать как первый общий результат комбинаторики. В этой книге есть и более сложные рисунки. Как утверждает приводимое в ней предание, император Ию (по другой версии Фуси — родона­чальник китайской цивилизации) более 2300 лет тому назад увидел на берегу реки Лошуй на панцире священной черепахи рисунок из белых и черных кружков (рис. 90). Если заменить каждую фигуру соответствующим числом, возникнет таблица, изображенная на том же рисунке справа. При сложении чисел в каждой строке, столбце и диагонали полу­чается одна и та же сумма 15. При том мистическом толко­вании, которое придавали числам древние китайцы, от­крытие таблицы со столь чудесными свойствами произвело неизгладимое впечатление.

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

Комбинаторика в Древней Греции

Философ Ксенократ, живший в IV веке до н. э., подсчитывал число слогов. В III веке до н. э. стоик Хрисипп полагал, что число утверждений, получаемых из 10 аксиом, превышает миллион. По мнению же Гиппарха, из утверждающих аксиом можно составить 103049 сочетаний, а добавив к ним отрицаю­щие, 310 952.

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

Конкретные комбинаторные задачи, касавшиеся перечисле­ния небольших групп предметов, греки решали без ошибок. Аристотель описал без пропусков все виды правильных трехчленных силлогизмов, а его ученик Аристоксен из Тарента перечислил различные комбинации длинных и коротких слогов в стихотворных размерах. Живший в IV веке н. э. математик Папп рассматривал число пар и троек, которые можно получить из трех элементов, допуская их повторения.

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

Как и китайцы, пифагорейцы придавали особое значение числу 36 — оно было для них не только суммой первых 4 четных и первых 4 нечетных чисел, но и суммой первых трех кубов: 36 = 1 ³+ 2³ + 3³ . Символом совершенства пифагорейцы считали совершенные числа, равные сумме своих делителей, например,

6 = 1 + 2 + 3, 28 = 1 + 2 + 4 + 7 + 14, а символом дру­жбы — дружественные числа, каждое из которых равно сумме делителей другого числа (например, 220 и 284). Отыскание таких чисел требовало комбинаторного искусства. _ь_

В школе Пифагора была доказана теорема о сторонах прямоугольного треугольника. Это вызвало интерес к представлению чисел в виде суммы двух квадратов, к квадрат­ным числам 1, 4, 9, 16 и т. д. Квадраты натуральных чисел те изображались при этом геометрически (рис. 2). Но пифагорейцы рассматривали и иные конфигурации точек. Каждый треугольник на рис. 2 получается из предыдущего увеличением го длины его стороны на 1. Подсчитывая число точек в каждом треугольнике, получаем последовательность треугольных чисел 1, 3, 6, 10, ... Ее можно получить, последовательно складывая натуральные числа: 1, 1 + 2, 1 + 2 + 3, 1 + 2 + 3 + 4ит. д.

Рис.2

А шестиугольники приводят к последовательности шести­угольных чисел 1, 6, 15, ... получаемых как частичные суммы членов арифметической прогрессии 1, 5, 9 ...

В дальнейшем такие суммы удалось выразить с помощью биномиальных коэффициентов C^k_n , играющих важную роль в комбинаторике.

Переход от плоскости к пространству дал возможность строить еще более сложные числа. Например, из треугольников можно составить пирамиды. Подсчитывая число точек в таких пирамидах, пришли к пирамидальным числам 1, 4, 10, 20, ..., которые были суммами ряда 1 + 3 + 6 + 10 + ..., составлен­ного из треугольных чисел. Однако дальнейшие обобщения требовали уже введения многомерных пространств, что лежало за рамками возможностей древнегреческой математики.

Учение о фигурных числах привлекало к себе математиков на протяжении многих столетий. Ими много занимался жив­ший в XVII веке французский ученый Пьер Ферма, который доказал, например, что любое натуральное число есть треуголь­ное или сумма 2 или 3 треугольных чисел; квадратное или сумма 2, 3 или 4 квадратов; пятиугольное или сумма 2, 3, 4 или 5 пятиугольных и т. д. Как и многие другие полученные им результаты, он лишь сформулировал это утверждение в письме к Блезу Паскалю (юрист по основной профессии, Ферма занимался математикой лишь в часы досуга). Частные случаи этой теоремы доказали Эйлер и Лагранж, а общее доказатель­ство было дано в 1815 г. французским математиком О. Коши.

Наряду с комбинаторикой чисел греческие ученые занима­лись и отдельными вопросами геометрической комбинаторики — правильными и полуправильными многогранниками, состав­лением фигур из 14 частей особым образом разрезанного квад­рата и т. д. Последнему вопросу была посвящена работа Архи­меда «Стомахион».

Мистики, астрологи, каббалисты

Со II века до н. э. начинается сначала медленный, а потом все более быстрый упадок науки в эллинистических странах, отражавший общий кризис античного общества. Многие работы того времени были посвящены мистическим толкованиям чисел в духе пифагорейцев (например, «Арифметическая теология» неопифагорейца Никомаха, жившего в I - II веках н. э.). Большое развитие получили различные числовые суеверия и толкования, связанные с заменой букв соответствующими чис­лами (греки обозначали числа с помощью букв — первые 9 букв алфавита обозначали числа от 1 до 9, следующие за ними — 10, 20, ..., 90, а последние 9 букв — 100, 200, ..., 900). Были «ученые», называвшиеся каббалистами, которые подвер­гали такому «анализу» слова Библии и других священных книг и делали на основе своих изысканий пророчества о будущем мира.

Во время богословских споров, начавшихся после победы христианства, старались получить из имен еретиков число 666 — ведь по Апокалипсису это было «звериное число», символ антихриста. Такие попытки предпринимались и позднее — лютеране пытались вывести число 666 из имени римского папы, а католики — из имени Мартина Лютера. В романе «Война и мир» Л. Н. Толстой описывает, как Пьер Безухов пытался вывести это число из имени Наполеона Бонапарта. Такого рода исследования при всей своей бесплодности давали толчок к дальнейшему развитию комбинаторики.

Наряду с каббалистами и мистиками комбинаторикой в это время занимались астрологи. Их интере­совал вопрос о движении планет и их «влиянии» на судьбы людей. Особое значение придавали они сочетаниям планет — встречам различных планет в одном знаке Зодиака. Астролог бен Эзра в 1140 г. рассчитал количество сочетаний семи планет по две, по три и т. д. Он знал, что число сочетаний семи планет по две равно числу их сочетаний по пять, а число сочетаний по три равно числу сочетаний по четыре. Если обозначить эти утверждения в современных символах, то получатся равенства С²₇ =С⁵₇ и С³₇=С⁴₇.

В окончательном виде формулу для числа сочетаний полу­чил живший в начале XIV века еврейский математик Леви бен Гершон, доказавший, что

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

Комбинаторика в странах Востока

В VIII веке н. э. начался расцвет арабской науки. Арабы перевели многие творения греческих ученых, изучили их, а затем продвинулись вперед в областях, мало привлекавших внимание греков, — в науке о решении уравнений, теории и практике вычислений и т. д. Решая вопрос об извлечении корней любой степени, арабские алгебраисты пришли к формуле для степени суммы двух чисел, известной под исторически неверным назва­нием «бином Ньютона». По-видимому, эту формулу знал жив­ший в XI — XII веках н. э. поэт и математик Омар Хайям. Во всяком случае, уже в XIII веке такую формулу приводит в своих трудах Насир ад-Дин ат-Туси, а в XV веке она была исследована Гиясэддином ал-Каши.

Судя по некоторым европейским источникам, восходящим к арабским оригиналам, для отыскания коэффициентов этой формулы брали число 10001 и возводили его во 2-ю, 3-ю, ..., 9-ю степени. Получалась таблица

10001¹ -10001

10001² - 100020001

10001³ - 1000300030001

10001⁴ - 10004000600040001

10001⁵ - 100050010001000050001

10001⁶ - 1000600150020001500060001

10001⁷ - 10007002100350035002100070001

10001⁸ - 100080028005600700056002800080001

10001⁹ - 1000900360084012601260084003600090001

в которой подчеркнуты коэффициенты бинома Ньютона. Если опустить в этой таблице излишние нули и добавить сверху

10001⁰ = 1, то получится треугольная таблица из биномиальных коэффициентов.

Арабские ученые знали и основное свойство биномиальных

коэффициентов, выражающееся формулой

Одновременно с арабами вычислением биномиальных коэф­фициентов занимались китайские математики. Они составили

к XIII веке н. э. таблицу таких чисел вплоть до п = 8, приве­денную в книге алгебраиста Чжу Ши-дзе «Яшмовое зеркало». Имеются сведения, что астроном И Синь в VIII веке н. э. вычислил количество различных расположений фигур в игре, напоминавшей шахматы.

Интересовались сочетаниями и в Индии. Еще во II веке до н. э. индийцы знали числа С и тот факт, что сумма равна 2ⁿ. А в XII веке индийский математик Бхаскара написал книгу «Лилавати», в которой среди других вопросов математики изучаются и проблемы комбинаторики. Он писал о применениях перестановок к подсчету вариаций размера в стихосложении, различных расположений в архитек­туре и т. д. Он дал также правила для отыскания числа перестановок и сочетаний нескольких предметов, при этом рассматривается случай, когда в перестановках есть повторяю­щиеся элементы.

Liber Abaci

Развитие торговли в XII с Востоком привело к проникновению в Европу арабской науки. Наиболее смелые и любознательные европейцы пробирались в находившуюся под владычеством арабов Испанию и знакоми­лись там не только с творениями греческих ученых, но и с достижениями арабской и индийской научной мысли — алгеброй и десятичной системой счисления.

В арабских учебных заведениях получил образование и Леонардо — сын пизанского купца, торговавшего в Алжире. В своей книге “Liber Abaci”, вышедшей в 1202 г., Леонардо, получивший прозвище Фибоначчи, привел в систему всю ариф­метику арабов, некоторые сведения по геометрии Евклида и добавил к ним результаты своих изысканий. Труд Фибоначчи содержал и новые комбинаторные задачи, например, об оты­скании наименьшего количества гирь, с помощью которых можно получить любой целый вес от 1 до 40 фунтов. Рас­сматривал Леонардо и отыскание целочисленных решений урав­нений. В дальнейшем аналогичные задачи привели к отыска­нию количества натуральных решений систем уравнений и неравенств, которое может рассматриваться как одна из глав комбинаторики.

Но главной заслугой Леонардо перед комбинаторикой было то, что он сформулировал и решил задачу о кроликах. Со времен греческих математиков были известны две последова­тельности, каждый член которых получался по определенным правилам из предыдущих — арифметическая и геометрическая прогрессии. В задаче Леонардо появилась новая последова­тельность, члены которой были связаны друг с другом соотно­шением . Это была первая в истории науки формула, в которой следующий член выражался через два предыдущих. Подобные формулы получили название рекур­рентных (от латинского recurrere — возвращаться). Метод рекуррентных формул оказался впоследствии одним из самых мощных для решения комбинаторных задач.

Игра в кости

Значительный толчок к развитию комбинаторики дали азартные игрыв. Наибольшее распространение получила игра в кости — два или три кубика с нанесенными на них очками выбрасывали на стол, и ставку брал выбросивший большую сумму очков.

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

Опытные иг­роки, неустанно упражнявшиеся в бросании костей, заметили, что некоторые суммы очков выпадают часто, а другие — редко. Само слово «азартный» происходит от арабского «азар» — трудный, так называли редко выпадавшие комбинации костей. Пытаясь понять, в чем тут дело, составляли таблицы, показывавшие, сколькими способами можно получить то или иное число очков. На первых порах иногда допускалась ошибка — подсчитывали лишь число различных сочетаний костей, дававших данную сумму. Например, при бросании двух костей сумма 6 получается как 1 +5,2+ 4и З + 3, сумма 7 — из сочетаний 1 + 6,2 + 5иЗ+ 4,а сумма 8 — из сочетаний 2 + 6,3 + 5и4 + 4. Так как каждый раз получается три различных сочетания с данной суммой, то делался ошибочный вывод, что суммы очков 6, 7 и 8 должны выпадать одинаково часто. Но это противоречило опыту — 7 очков выпадали чаще. Дело в том, что при бросании двух костей сочетание 3 + 3 может быть получено единственным образом, а сочетание 3 + 4— двумя способами (3 + 4 и 4 + 3). Этим объясняется большая частота выпадения суммы 7.

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

Более сложными оказались соответствующие исследованиядля трех костей. Здесь при учете порядка костей оказывается 3 6 =216 различных комбинаций, а без учета порядка — лишь 56.

Этими вопросами занимались такие известные итальянские математики XVI века, как Д. Кардано, Н. Тарталья и др. Наиболее полно их исследовал в XVII веке Галилео Галилей, но его рукопись оставалась неопубликованной до 1718 г.

Игрок и ученые

Одним из самых азартных игроков в кости в XVII веке был шевалье де Мере, непрерывно изобретавший новые виды состя­заний. Например, он предложил, что будет бросать четыре кости и брать выигрыш лишь в случае, когда хотя бы одна из них откроется на шести. Однако вскоре его партнеры отказа­лись от участия в такой игре — шевалье чаще выигрывал, чем проигрывал. Тогда де Мере придумал новый вариант — он бросал несколько раз пару костей и брал выигрыш, если хотя бы раз выпадали две шестерки. Надо было лишь определить, сколько следует сделать бросков, чтобы игра была ему столь же выгодна, как и первая. Шевалье решил, что надо бросать кости 24 раза. Ведь при четырех бросках одной кости шестерка выпадала более чем в половине случаев, а так как вторая кость дает шесть вариантов выпадения, то и надо умножить 4 на 6. Рассуждение казалось безукоризненным, но опыт не подтвердил надежд де Мере — теперь он стал чаще проигрывать, чем выигрывать.

Другой проблемой для де Мере была задача о разделе ставки. Проблема состояла в следующем: «матч» ведется до шести выигранных партий; он был прерван, когда один игрок выиграл 5 партий, а другой — 4; как разделить ставку? Было ясно, что раздел в отношении 5:4 несправедлив.

Де Мере обратился за разъяснениями к двум крупнейшим математикам Франции XVII века — Блезу Паскалю и Пьеру Ферма. Разбираясь в этих и других задачах, поставленных перед ними де Мере, они сформулировали и доказали первые теоремы комбинаторики и теории вероятностей. А задачу о разделе ставки Паскаль решил в общем случае, когда одному игроку остается до выигрыша r партий, а второму s партий. Другое решение задачи дал Ферма.

Новая ветвь математики

Работы Паскаля и Ферма ознаменовали рождение двух новых ветвей математической науки — комбинаторики и тео­рии вероятностей. Если до них комбинаторные проблемы лишь затрагивались в общих трудах по астрологии, логике и мате­матике, а большей частью относились к области математичес­ких развлечений, то уже в 1666 г. Готфрид Вильгельм Лейбниц публикует «Диссертацию о комбинаторном искусстве», в кото­рой впервые появляется сам термин «комбинаторный.Диссертация Лейбница должна была стать лишь началом боль­шой работы, о которой он часто упоминал в своих письмах и печатных трудах и для которой делал в своих записных книжках многочисленные заметки. Из них видно, что Лейбниц планировал для комбинаторики все новые и новые приложения: к кодированию и декодированию, играм, статистике, теории наблюдений. Под комбинаторикой Лейб­ниц понимал примерно то, что мы теперь называем дискретной математикой. К области комбинаторики Лейбниц относил и «универсальную характеристику» — математику суждений, т. е. прообраз нынешней математической логики.

Проекты Лейбница казались несбыточными здравомысля­щим математикам его времени, но после создания компьютеров многие планы Лейбница стали претворяться в жизнь, а дискретная математика выросла в своем значении настолько, что начала соперничать с классическим математи­ческим анализом.

В 1713 г. племянник Якоба Бернулли (скончавшегося в 1705 г.) Николай опубликовал часть II книги Якоба Бернулли «Ars conjectandi» («Искусство предположений»), в которой ука­зывались формулы для числа размещений из п элементов по k, выводились выражения для степенных сумм и т. д. Замеча­тельные достижения в области комбинаторики принадлежат одному из величайших математиков XVIII века Леонарду Эйле­ру, швейцарцу, прожившему почти всю жизнь в России, где он был членом Петербургской академии наук. Основные работы Эйлера в области науки посвящены математическому анализу, в котором он проложил новые пути, создал целый ряд новых областей и подвел итоги исследованиям в других областях. Но у Эйлера хватало времени размышлять и о задачах, которые, казалось бы, не заслуживали его внимания, — о том, можно ли обойти мосты в Кенигсберге (ныне Калининграде) так, чтобы не побывать дважды на одном и том же мосту; можно ли поставить 36 офицеров из 6 разных полков так, чтобы в каждой шеренге и каждой колонне было по одному офицеру каждого воинского звания из каждого полка; сколькими способами можно разбить данное число на слагаемые и т. д. Но, странное дело, работа о мостах явилась зерном, из которого впоследствии выросли топология и теория графов, задача об офицерах ока­залась сейчас связанной с планированием экспериментов, а методы, использованные при решении задачи о разбиении чисел, после длительного и сложного пути развития преврати­лись в науку об интегральных преобразованиях, применяемую для решения уравнений математической физики.

После работ Паскаля и Ферма, Лейбница и Эйлера можно было уже говорить о комбинаторике как о самостоятельной ветви математики, тесно связанной с такими областями науки, как теория вероятностей, учение о рядах и многими другими. В конце XVIII века немецкий ученый Гинденбург и его учени­ки сделали даже попытку построить общую теорию комбина­торного анализа. Однако она не увенчалась успехом — в то время еще не было накоплено достаточного количества важных и интересных задач, которые могли бы дать необходимый фундамент для такой теории.

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

Комбинаторика и шифры

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

Комбинаторные методы применял для шифрования еще итальянский ученый XVI века Джовани Баттиста делла Порта. Они были основаны на циклической перестановке букв. Русские дипломаты в XV - XVI веках применяли «тарабарскую грамо­ту», в которой все гласные буквы оставались неизменными, а согласные заменялись друг на друга по такой схеме:

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

Для кодирования и расшифровки привлекались математики. Еще в конце XVI века расшифровкой переписки между про­тивниками французского короля Генриха III и испанцами за­нимался один из создателей современной алгебры Франсуа Виета. А в Англии XVII века монархистские заговорщики поражались быстроте, с которой Кромвель проникал в их замыслы. Монархисты считали шифры, которыми они пользо­вались при переписке, неразгадываемыми, и считали, что клю­чи к ним были выданы кем-то из участников заговора. И лишь после падения республики и воцарения Карла II они узнали, что все их шифры разгадывал один из лучших английских математиков того времени, профессор Оксфордского универси­тета Уоллис, обладавший исключительными комбинаторными способностями. Он назвал себя основателем новой науки «крип­тографии» (тайнописи).

Анаграммы

До XVII столетия почти не было научных журналов. Ученые узнавали о трудах своих коллег из книг или из частных писем. Это создавало большие трудности при опубликовании новых результатов — ведь печатание книг занимало целые годы, а написать о своем открытии в частном письме было рискованно — не ровен час, кто-нибудь присвоит достижение, и поди доказывай, что он узнал это из полученного письма, а не сам придумал. А могло случиться, что получатель письма долго думал над тем же вопросом, нашел его решение, и письмо действительно ничего нового ему не открыло — он сам соби­рался написать коллеге аналогичное сообщение.

Из-за этого часто возникали споры о приоритете. Еще в конце XVII столетия шли долгие споры о приоритете между Ньютоном и Лейбницем (о том, кто первый создал дифферен­циальное и интегральное исчисления), между Ньютоном и Гуком (кто первый сформулировал закон всемирного тяготения) и т. д.

А в древности Архимеду пришлось даже пуститься на хитрость. Когда некоторые александрийские ученые присвоили себе его результаты, о которых узнали из полученных от него писем, он написал им еще одно письмо. В нем содержались совершенно замечательные формулы для площадей и объемов некоторых фигур. Александрийцы снова сказали, что эти фор­мулы они давным-давно знают, и ничего нового им Архимед не сообщил. Но тут выяснилось, что Архимед поймал их в ловушку — сообщенные в письме формулы были неверными!

Для того чтобы и приоритет обеспечить, и не допустить преждевременной огласки достигнутых результатов, ученые в краткой фразе формулировали суть открытия, а потом пере­ставляли в ней буквы и посылали письмо с переставленными буквами своим коллегам. Такие тексты с переставленными буквами называются анаграммами. Например, слова «Москва» и «смоква» — анаграммы. Когда же печаталась книга с по­дробным изложением результата, в ней давалась расшифровка анаграммы.

К анаграммам прибегали и в политических спорах. Напри­мер, после убийства французского короля Генриха III из имени его убийц (брат Жак Клеман) составили анаграмму (меня создал ад). Против­ники короля не остались в долгу и из его имени (Анри де Валуа) составили анаграмму (Иродова мерзость).

Когда Христиан Гюйгенс открыл кольцо Сатурна, он соста­вил анаграмму

aaaaaaa, ccccc, d, eeeee, g, h, iiiiiii, lll, mm,

nnnnnnnnn, oooo, pp, q, rr, s, ttttt, uuuuu.

Буквы в ней можно поставить в таком порядке, что полу­чится текст «Annulo cingitur tenui, piano, nusquam cohaerente, ad eclipticam inclinato» («окружен кольцом тонким, плоским, нигде не подвешенным, наклонным к эклиптике»).

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

Иероглифы и клинопись

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

У Шампольона были предшественники — шведский архео­лог Д. Окерблад и английский физик Т. Юнг, которые подвер­гли египетские тексты комбинаторному анализу. В их руках были «билингвы» — надписи, сделанные одновременно на египетском и греческом языках. Сравнивая оба текста и выяс­няя повторяемость групп знаков, Окерблад опознал некоторые знаки так называемого демотического письма — поздней ста­дии развития египетской письменности. А создатель волновой оптики Томас Юнг любил на каникулах отдохнуть от размыш­лений на физические темы и занимался то каллиграфией, то составлением алфавитов иностранных языков, то... танцами на слабо натянутом канате, — по мнению Юнга все, что мог сделать один человек, мог повторить другой. В 1814 г. он взял с собой на каникулы древнеегипетский папирус и попробовал прочесть его. Не имея должной филологической подготовки, путем лишь комбинаторного исследования текста он получил интересные результаты, а затем попробовал читать иероглифы. Кое-каких успехов он добился и здесь, но сказалось недоста­точное знание языков — он искал иероглифы не только для согласных, но и для гласных букв, а в египетском письме гласные опускались. Лишь Шампольону, сочетавшему неза­урядный комбинаторный дар с глубочайшим знанием филоло­гии, удалось прочесть иероглифы.

Сложность задачи, стоявшей перед Шампольоном, усугу­блялась тем, что не были известны ни язык надписей, ни смысл знаков. Однако, выделив знаки, которые в греческом тексте обозначали имена царей, Шампольон обнаружил, что некоторые знаки в именах фараонов Птолемея и Клеопатры совпадают. Так были найдены звучания иероглифов, означавших буквы «п» и «л» (до этого места дошел и Юнг). А затем Шампольон распознал имена римских императоров Тиберия и Траяна, древних фараонов Рамсеса и Тутмеса — ключ к чтению иерог­лифов, утерянный несколько тысячелетий тому назад, был вновь обретен.

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

Еще теснее связана с комбинаторикой история расшифровки клинописных надписей. Историкам удалось установить, что эти надписи были сделаны в эпоху Ахеменидов, правивших в Иране два с половиной тысячелетия тому назад. Были сделаны и предположения о языке надписей. А потом комбинаторный анализ текста вскрыл часто повторявшуюся группу из семи знаков. Иногда эта группа повторялась дважды подряд с не­большими изменениями. И датский ученый Мюнтер решил, что эта группа означает слово «царь», а повторенная дважды — «царь царей». Но узнать звучание этих знаков Мюнтер не сумел. Это сделал молодой немецкий учитель Гротефенд. Лю­битель различных головоломок и тайнописи, он однажды (как гласит предание, после веселого вечера в дружеской компании) заключил пари, что расшифрует клинопись. Анализируя соче­тания знаков около титулов «царь» и «царь царей», Гротефенд обнаружил, что некоторые из них встречаются в разных пози­циях. Отсюда был сделан вывод, что это имя царя, которое в иной позиции означает «сын царя такого-то». Это позволило опознать и группу знаков для слова «сын». В одном месте после этой группы знаков не стояло слово «царя». Значит, решил Гротефенд, царь, о котором идет здесь речь, не был сыном царя — это был сам основатель династии Дарий, сын Гистаспа. А так как Дарий был отцом Ксеркса, то у Гротефенда были в руках звуковые значения для знаков, входивших в имена «Гистасп», «Дарий», «Ксеркс» — начало расшифровки клино­писи было положено!

Комбинаторика позволила прочесть и крито-микенское ли­нейное письмо.

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

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

Лишь через два года после смерти исследовательницы мо­лодой английский архитектор Майкл Вентрис, расширяя ее координатную сетку, попробовал угадать значения некоторых гласных — число гласных меньше числа согласных, и перебор лучше начинать с них. Одна из попыток оказалась удачной — текст заговорил на языке, весьма напоминавшем греческий. Но это не был классический греческий язык «Илиады» и «Одис­сеи», а греческий язык более ранней эпохи. Вентрису помог завершить расшифровку видный знаток раннего греческого языка Чэдвик. Используя имена царей и списки географичес­ких названий, исследователи расшифровывали один слог за другим. А потом началась цепная реакция дешифровки — три десятка знаков получили свое значение.

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

При расшифровке буквенной письменности оказывается ве­сьма важным отделение знаков, обозначающих гласные буквы, от знаков, обозначающих согласные буквы. И здесь на помощь приходит комбинаторика. Филолог В. В. Шеворошкин устано­вил метод, основанный на комбинаторном сравнении частоты различных сочетаний пар знаков. Хорошо известно, что в языках гласные и согласные определенным образом чередуются друг с другом. Это позволяет разделить все знаки на две группы так, что, как правило, знаки одной группы перемежаются в тексте знаками другой группы. Тогда знаки, входящие в мень­шую группу, будут обозначать гласные, а входящие в большую группу, — согласные. Этот метод дал исследователю ключ к чтению карийских надписей.

ПЕРЕСТАНОВКИ

Пусть имеется п объектов, неважно каких, лишь бы все они различались между собой: книги, детские кубики или музыканты крыловского «Квартета». Мысленно расставим их в ряд и та­кое упорядоченное расположение объектов назовём перестановкой. Попытаемся ответить на вопрос: сколько всего возможно перестано­вок из п предметов? Число перестановок обо­значают Р_п, подчёркивая тем самым, что оно зависит от количества предметов п.

Перестановки -- комбинации, состоящие из одних и тех же n различных элементов и отличающиеся только порядком их расположения.

Попытаемся найти Р_п сначала для неболь­ших п. Если п = 1, т. е. имеется один-единственный предмет, то существует и один-единствен­ный способ его расстановки. Поэтому Р₁ = 1. Возьмём п = 2. Сразу понятно, что Р₂ = 2, поскольку два предмета (назовём их А и Б) можно расставить двумя различными способами: АБ и БА. Попробуем рассуждать несколько иначе: первый предмет (А) установим непо­движно, а второй (Б) будем «прилаживать» к нему. Безусловно, объект Б можно поставить либо спереди, либо сзади от А, следовательно, число перестановок Р₂ вдвое больше, чем Р₁ , т.е. Р = Р₁ •2 = 1 • 2. Добавим теперь третий предмет В. К каждой из перестановок двух объектов А и Б можно пристроить третий предмет тремя различными способами: поста­вить его спереди, между ними либо сзади. Пе­рестановка АБ, таким образом, порождает три перестановки: ВАБ, АВБ и АБВ, перестановка БА — также три: ВБА, БВА и БАВ, и все по­лучившиеся шесть перестановок — разные. Отсюда Р₃ = P₂ • 3 = 1 • 2 • 3.

Вообще, из каждой перестановки п -1 пред­метов можно получить п дополнительных пе­рестановок, добавляя n-й предмет либо спе­реди, либо сзади, либо между имеющимися предметами (между п - 1 предметами суще­ствует п - 2 промежутка; 1 + 1+n-2 — вот и выходит ровно п). Стало быть, при переходе от п - 1 к п предметам количество перестано­вок увеличивается в п раз. Поэтому общая фор­мула будет такой: .

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

Восклицательным знаком (в математике он называется факториалом) принято обозна­чать произведение всех натуральных чисел от 1 до n включительно.

Выше приведён не просто вывод формулы, но одновре­менно способ того, как получить все воз­можные перестановки. Надо отметить, что он далеко не единственный. Например, все пере­становки можно получить из начальной, по­очерёдно меняя местами соседние объекты:

АБВ →АВБ →ВАБ → ВБА →БВА → БАВ.

Правило суммы (или сложения): Если некоторый объект А может быть выбран из совокупности объектов m способами, а другой объект В может быть выбран n способами, то выбрать объект А или объект В можно выбрать (m+n) способами.

Правило произведения (или умножения): Если некоторый объект А может быть выбран из совокупности объектов m способами, и после такого выбора объект В может быть выбран n способами, то пару объектов А и В в указанном порядке можно выбрать (m n) способами.

Решение задачи о квартете

Четыре горе-музыканта из басни Крылова долго пересаживались с места на место. В ходе этого «творческого поиска» Осёл внёс предло­жение: «Мы, верно, уж поладим, коль рядом ся­дем». Попробовали — не помогло. Но в ряд-то можно сесть по-разному! Давайте определим число возможных перестановок. Здесь п = 4, поэтому способов «усесться чинно в ряд» име­ется Р₄ = 4! = 1 2 3 4 = 24.

Зеркально-симметричные перестановки

Добавим, что для решения некоторых задач приходится применять идею перестановок не в «чистом» виде, а с поправками. Допустим, глав­ный фактор, влияющий на качество игры, — это соседи каждого музыканта, и не важно, кто из них справа, а кто слева. При таком условии перестановка «Мартышка, Осёл, Козёл, Мишка» эквивалентна зеркально-симметричной: «Миш­ка, Козёл, Осёл, Мартышка». Понятно, что в этом случае все Р₄ вариантов разбиваются на пары равнозначных перестановок. И если из каждой пары оставить по одной перестановке, то об­щее число различающихся вариантов будет 12.

Теперь представим, что музыканты сели не в ряд, а по кругу. В этом случае можно рассуж­дать так: в каждом из вариантов пронумеруем всех участников по часовой стрелке, начиная, скажем, с Осла. В различных перестановках каждый музыкант, конечно, должен иметь разные номера. Только у одного из них — Осла — будет постоянный номер 1. Значит, осталось пронумеровать различными способами только троих. Поэтому здесь число воз­можных перестановок — Р₃ = 3! = 6.

Перестановки с повторениями

Есть особый (и очень важный!) вид переста­новок — перестановки с повторениями. В них среди прочих участвуют предметы, неразличи­мые между собой, — «близнецы». Замена одно­го «близнеца» другим не приводит к новой расстановке. Предположим, что, отчаявшись, наши музыканты решили создать вместо квар­тета симфонический оркестр. Для этого Мар­тышка привела с собой ещё 15 Мартышек, Осёл — ещё 20, Ослов, Козёл — 10 Козлов, лишь Мишка поленился и остался в одиночестве. Выясним, сколькими способами можно расса­дить их в ряд.

Возьмём любую произвольную расстанов­ку всех 16 + 21 + 11 + 1= 49 музыкантов. Если бы «близнецов» в их числе не оказалось, то перестановок было бы 49!. Но вот среди них появилось 16 одинаковых Мартышек. Не тро­гая остальных зверей, а меняя местами лишь Мартышек всеми возможными способами (а их будет 16!), получим вроде бы новые переста­новки, но теперь уже неразличимые. То есть каждые 16! старых перестановок преобразу­ются в одну новую и общее число перестано­вок уменьшается в 16! раз. Очевидно, та же ис­тория и с Ослами, и с Козлами (лишь Медведь по-прежнему один). В итоге количество пере­становок окажется равным

Медведя не учитывали, но, дабы не нарушать единообразия, добавим и его, т. е. поделим ука­занное выражение ещё на 1! = 1:

Чтобы отличить перестановку с повторениями от обычной, над буквой Р ставится горизонтальная черта.

Можно получить и общую формулу для случая, когда имеется п групп «близнецов», состоящих соответственно из k₁ ,k₂ ,… , k_n неразличимых предметов:

Множество факториалов в этой формуле может вызывать трудности. Но в комбинаторике факто­ри- ал — частый гость, даже хозяин. К сожале­нию, на калькуляторе функция «факториал» обычно отсутствует, поэтому при практических расчётах приходится последовательно умно­жать натуральные числа. Занятие довольно трудоёмкое — попробуйте, например, вычис­лить 49!. Однако, когда не требуется абсолют­ной точности, для больших п можно с успехом использовать формулу, которую вывел в XVIII в. шотландский математик Джеймс Стирлинг:

Она примечательна не только высокой точ­ностью (уже при и - 10 погрешность менее 1 %) , но и неожиданным присутствием двух заме­чательных чисел: числа Эйлера е = 2,71828... и числа π = 3,14159… А произвести вычисле­ния по формуле Стирлинга на хорошем каль­куляторе не составляет труда.

РАЗМЕЩЕНИЯ

Иногда бывает нужно из п имеющихся различ­ных объектов отобрать произвольные т штук (т ≤ п) и расположить их в некотором поряд­ке. Каждое такое упорядоченное расположение называется размещением. Сколько существует размещений при заданных п и т? Оказывается, ответ можно дать, основываясь на знании пе­рестановок.

Размещения -- комбинации, составленные из n различных элементов по m элементов, которые отличаются либо составом элементов, либо их порядком.

Обозначим искомое число А_n^m . Сначала возьмём любую перестановку всех n объектов и рассмотрим первые т из них. Они образуют размещение т объектов из п имеющихся, тогда как последние п - т объектов совершенно не влияют на это размещение, как их ни перестав­ляй. Но эти п - т «хвостовых» объектов могут быть переставлены Р_п-т способами. Значит, каж­дому размещению можно «пришить» Р_п-т раз­личных «хвостов», что порождает столько же перестановок всех п объектов. Общее число пе­рестановок всех объектов Р_п в таком случае рав­но произведению искомого А_n^m числа и Р_n-m:

Отсюда

Есть ли у нуля факториал?

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

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

Второй вопрос: сколькими способами мож­но сделать упорядоченный выбор из п объек­тов... всех п? Поступаем так: выбираем любой объект, рядом с ним размещаем второй, потом тре-тий и т. д. Получается обыкновенная пере­становка всех п объектов, и число таких пере­становок Р_п = п!. С другой стороны, согласно найденной формуле, это же число равняется

Появилось новое выражение 0! (факториал мы определяли только для натуральных чисел). Предположим, что 0! — это какое-то неизвест­ное число, и найдём его из равенства A_nⁿ =P _n . Тогда =n!, откуда 0! = 1, т. е. факториал нуля равен единице (хотя казалось, что это не­пременно должен быть нуль). Факториал нуля возникает в самых разных комбинаторных задачах, но везде и всегда его принимают равным единице.

Размещения с повторениями

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

Каждый предмет после «использования» возвращается обратно и может быть «использован» повторно

Определить это число несложно. На первом месте в списке может находиться любой из п объектов, на втором — тоже любой, и на тре­тьем, и на четвёртом... в общем, на каждом. Поэтому число размещений с повторениями выражается формулой

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

Решение задачи о паспортах

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

Буквы. В русском алфавите 33 буквы. Нам нужно выбрать любые две, при этом они могут оказаться и одинаковыми. Следовательно, име­ет место размещение с повторениями, где п = 33 и т = 2: = ЗЗ² =1089.

Цифры. Здесь выбирается (и опять с по­вторениями) т = 6 цифр из n = 10 возможных. Для этого есть = 10⁶ способов.

Итог: поскольку каждую пару букв можно соединить с любой шестёркой цифр, то воз­можно существование • - ЗЗ² •10⁶ = = 1 089 000 000 паспортов, имеющих одни и те же римские цифры серии, — больше миллиар­да! Ну а если потребовать, чтобы в каждом но­мере и буквы, и цифры были различными, — сколько тогда получится паспортов? Здесь вместо размещений с повторениями нужно ис­пользовать обычные размещения. Поэтому от­вет таков:

В результате число зна­чительно уменьшилось.

СОЧЕТАНИЯ

В некоторых задачах по комбинаторике не имеет значения порядок расположения объектов в той или иной совокупности. Важно лишь то, какие именно элементы её составля­ют. К примеру, представим себе школьный класс, который пришёл в спортзал. Школьники могут выстроиться в шеренгу, а бегать где попало, прыгать, кувыркаться, стоять на голове, лазать по канату — всё равно они оста­нутся тем же самым множеством учеников класса. Теперь часть из них переведём в сосед­нее помещение, где им также дозволяется бегать, прыгать и т. д. Такая выборка элементов, при которой их порядок совершенно неважен, называется сочетанием.

Сочетания -- комбинации, составленные из n различных элементов по m элементов, которые отличаются хотя бы одним элементом.

Число всевозможных сочетаний из п элементов по т обозначается С_n^m Найдём это число.

Будем основываться на том, что нам извест­но: на размещениях и перестановках. Сначала из п элементов выделим какие-либо т элемен­тов с учётом очерёдности выбора. Это — разме­щение, и число таких размещений A_n^m . Очевид­но, что различные размещения, в которые входят те же объекты, но в ином порядке, будут соответствовать одному сочетанию (ведь в со­четании порядок роли не играет). Другими сло­вами, любая перестановка выбранных m эле­ментов порождает то же самое сочетание. Но таких перестановок Р_т. Поэтому число соче­таний из п элементов по m в Р_m раз меньше числа размещений, т. е.

Следует обратить внимание на своеобразную симмет­рию этой формулы: если заменить m на п - m, получится то же самое, только факториалы в знаменателе поменяются местами. Отсюда сле­дует замечательное свойство сочетаний:

Объясняется это можно следующим образом: каждому сочетанию из т отобранных элементов всегда соответствует сочетание из п - т оставшихся. Так что мож­но с самого начала говорить не о выделении т объектов из n, а о разбиении множества ис­ходных п элементов (например, тех же школь­ников) на две части — поmиn-m в каждой (m человек — в один зал, а п - т — в другой).

Попытаемся теперь ответить на следующий вопрос: сколькими способами п школьников могут разделиться по t залам так, чтобы в пер­вом зале оказалось m₁ школьников, во втором т_г и т. д., где т₁ + т_г + ... + m_t=n? Обозначим искомое число через . Как его полу­чить? Сначала из общего количества п школь­ников выделим m₁ потом из п - т₁ оставшихся т₂ и т. д., следовательно,

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

Задача о Лотто-Миллион

Сколько карточек Лотто-Миллион нужно ку­пить и заполнить, чтобы на них оказались все комбинации по 6 номеров из 49 возможных? Количество карточек равно числу сочетаний из 49 элементов по 6, т. е.

а это составляет почти 14 млн. Можно сделать вывод : для реализации подобной идеи уже надо быть миллионером! Но и в этом случае раз­богатеть будет трудно, поскольку выигрыш не фиксирован и в каждом тираже на призо­вой фонд отводится лишь часть собранной от продажи билетов суммы.

Заполненная карточка Лотто-Миллион

Допустим, мы купили С₄₉⁶ карточек и все их по-разному заполнили. После тиража 6 счастливых номеров окажется только на одной из них. Но в Лотто-Миллион выигрывают и карточки с совпадением 5 и даже 4 номеров. Сколько их?

Если на карточке угадано 5 номеров, это значит, что из 6 выпавших номеров здесь мо­гут быть вычеркнуты любые 5, а из остальных 43 — лишь 1. Поэтому число способов угадать 5 номеров равно . Точно так же карто­чек с совпадением 4 номеров будет . Наконец, на карточках не окажется ни од­ного выпавшего номера.

Сочетания с повторениями

И перестановки, и размещения могут быть с повторениями. Имеет смысл говорить и о соче­таниях с повторениями. Из множества, содер­жащего n предметов, нужно взять один произволь­ный, занести его в список, после чего вернуть обратно. Затем точно так же выбрать ещё один объект и т. д., пока в списке не окажется m на­именований (среди них могут быть и одинаковые). Принципиальное отличие от размещений с повторениями заключается в том, что в дан­ном случае элементы списка не нумеруются. Например, списки «А, Б, А, Г» и «Б, Г, А, А» счита­ются одинаковыми. Найдём число сочетаний с повторениями из n элементов по m. Произвольно пронумеруем элементы ис­ходного множества числами от 1 до n. Пусть в какое-то из полученных сочетаний вошло k элементов под номером 1, k₂ элементов под но­мером 2, ..., k_n элементов под номером n. Что можно сказать обо всех этих числах k_i ? Cумма (ведь в списке всего m объектов!).

Теперь изобразим это сочетание в виде цепочки из нулей и единиц. Единица здесь будет обозначать каждый отдельный элемент сочетания, а нуль — символизировать границу между группами элементов, соответствующих соседним k_i . Если некоторое k_i = 0, т. е. элемен­тов с номером i в списке нет, то в соответству­ющем месте цепочки окажутся два «погра­ничных» нуля подряд.

Итак, записываем: сначала k₁ единиц, затем один нуль, после этого k₂ единиц и снова нуль… k_n-1 единиц и опять нуль, наконец, k_n единиц - и всё.

Поскольку сумма всех k_i равна m, в по­строенной цепочке содержится m единиц. Ну­лей же n - 1. Так что вся цепочка состоит из n +m - 1 цифр.

Подведём итог. Каждому возможному спис­ку поставлена в соответствие некоторая цепоч­ка из нулей и единиц длиной n +m - 1. При этом если два списка одинаковы, то и цепочки получатся одинаковыми. Верно и обратное: каждой цепочке соответствует определённый список. Например, цепочка 1111001010 гово­рит нам, что в списке — четыре элемента номер 1, ни одного элемента номер 2, по од­ному элементу номер 3 и 4 и ни одного эле­мента номер 5. Таким образом, задача свелась к поиску ответа на вопрос: сколько можно со­ставить различных цепочек длиной n +m – 1 из m единиц и n- 1 нулей? А это не что иное, как число перестановок с повторениями из m нулей и n- 1 единиц, т. е. . Поэтому

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

БИНОМ НЬЮТОНА

В алгебре довольно часто приходится возводить в степень двучлен а + b. Недаром каждый школьник заучивает наизусть формулы квад­рата и куба суммы двух чисел. Аналогичная формула, но уже для произвольного п 0 называется биномом Ньютона, хотя и была известна задолго до него. ( Слово «бином» в переводе с латыни означает «двучлен».) Формула эта имеет прямое отноше­ние к комбинаторике.

Для удобства в выражении (а + b)ⁿ вынесем bⁿ за скобки и обозначим а/b через х. Поучается bⁿ (x+1)ⁿ. На время забудем про множи­тель b^п и будем искать формулу для (х + 1)ⁿ. После раскрытия ско­бок перед нами предстанет многочлен n-й сте­пени. Нужно только определить коэффици­енты при различных степенях х.

Выпишем произведение из n скобок (x+1):

Теперь раскроем скобки, но при этом не будем приводить подобные члены. Например:

и т. д.

Естественно, результат представляет собой сумму каких-то степеней х (в том числе и ну­левой, т. е. 1).

Наконец, соберём все x по одинаковым сте­пеням и получим многочлен n-й степени уже в привычном виде. Ясно, что коэффициент при х^т будет равен количеству слагаемых х^т в пер­воначальном, неприведённом виде. Сколько их? Ещё не зная, как ответить на этот вопрос, мы уже чувствуем, что перед нами комбина­торная задача...

Биномиальные коэффициенты и сочетания

После перемножения п скобок (х + 1) любая появившаяся степень х возникла как произве­дение п сомножителей — по одному от каж­дой скобки. Но все сомножители равны либо х, либо 1. Для появления т-й степени х необ­ходимо, чтобы при перемножении ровно из т скобок были взяты сомножители х, а из осталь­ных п - т скобок — 1. Сколькими способами можно выбрать т объектов (в данном случае скобок) из п возможных?

Таблица биномиальных коэффициентов из книги Якоба Бернулли «Искусство предположений». 1713г.

Или, другими слова­ми, каково число сочетаний из п элементов по т? Ответ : С_n^m . Итак, раскрыв все скоб­ки, получим С_n^m слагаемых, равных x^m, и, зна­чит, после приведения подобных членов коэф­фициент при x^m равен С_n^m . Поэтому

Так как числа С_n^m являются коэффициентами в формуле бинома Ньютона, они называются биномиальными коэффициентами. Попробуем выписать формулы бинома (х + 1)ⁿ для не­которых конкретных значений х, например для x=0, ±1,±2, ±1/2.

Нетрудно вывести подобную формулу и для (а + b)ⁿ. Надо только вспомнить, что а/b = х и (а + b)^п = bⁿ (х + 1)ⁿ. В результате получим

Формула для (a+b)⁴: =

=

Формула для (a+b)⁵: =

=

Формула бинома Ньютона позволяет обна­ружить важную зависимость между биномиаль­ными коэффициентами. Рассмотрим формулу для (x + 1)ⁿ⁺¹ . Чему равен коэффициент при x^m+1? Ясно, что это . С другой стороны (x + 1)ⁿ⁺¹ можно получить, умножив формулу для (x + 1)ⁿ на (x + 1). Тогда (m + 1)-я степень числа х может быть получена либо при умно­жении слагаемого на х, либо при умно­жении на 1. Поэтому коэффициент в формуле для (x + 1)ⁿ⁺¹ ' должен быть равен сумме C_n^m и , т. е.

Свойства биномиальных коэффициентов

1. 

2. (правило симметрии)

3. 

4. 

5. (правило Паскаля)

6. 

Треугольник Паскаля

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

того, что выпишем в одну строку бесконечное число нулей и только одну единицу среди них:

…000010000…

Ниже создадим вторую строку чисел, записы­вая между каждыми двумя числами первой строки их сумму. Затем под второй строкой запишем по тем же правилам третью, четвёр­тую и т. д.:

…0 0 0 0 1 0 0 0 0…

…0 0 0 1 1 0 0 0…

…0 0 0 1 2 1 0 0 0…

…0 0 1 3 3 1 0 0 0…

…0 0 1 4 6 4 1 0 0…

…0 1 5 10 10 5 1 0 0…

…0 1 6 15 20 15 6 1 0…

…1 7 21 35 35 21 7 1 0…

В треугольнике Паскаля п-я строка содержит биномиальные коэффициенты С_n⁰ ,C_n¹, C_n² ,..., C_nⁿ Это следует из формулы (*), которая примени­тельно к построенной таблице означает, что каждое число равно сумме двух вышестоящих.

Треугольник Паскаля обладает множеством замечательных свойств. Например, сумма чи­сел и-й сроки треугольника равна 2^п. Чтобы доказать это, достаточно рассмотреть бином, у которого а = b= 1. С одной стороны, он равен 2ⁿ, а с другой — сумме всех биномиальных ко­эффициентов этой строки.

Другое свойство: количество нечётных чи­сел в п-й строке всегда равно степени двойки, более того, оно равно 2^k , где k — число единиц в двоичной записи числа п. Например, 5-я строка содержит числа 1, 5, 10, 10, 5, 1, среди которых 4 нечётных. В то же время число 5 в двоичной системе счисления записывается как 101. Число 101 содержит 2 единицы, и 2² = 4. Ещё одно свойство треугольника Паскаля: в каждой строке сумма чисел, стоящих на нечётных местах, равна сумме чисел, стоящих па чётных местах. Чтобы убедиться в этом, рас­смотрим бином, у которого а = 1, b= -1. Кро­ме того, если номер строки — простое число, то все числа в строке, за исключением двух крайних единиц, делятся на номер строки.

ЗАДАЧИ ПО КОМБИНАТОРИКЕ

Задача о разбиении плоскости прямыми

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

Попробуем сначала найти ответ для неболь­ших п. При п=1 плоскость окажется разбитой на две части (обозначим это так х₁ = 2), при n= 2 — на четыре (х₂ = 4). Следующее значе­ние —x₃= 7 (рис. 1). Проведём ещё одну пря­мую. Тут же возникает сомнение: а не будет ли число частей зависеть от расположения чет­вёртой прямой относительно первых трёх? В самом деле, четвёртая прямая может пересечь образованный тремя предыдущими треуголь­ник (рис. 2), но может и обойти его (рис. 3). Число частей в обоих случаях оди­наково: x₄₌ 11. Построив пятую прямую, обна­ружим, что результат опять не зависит от вза­имного расположения прямых и х₅ = 16. Но рисунок будет уже буквально загромождён пря­мыми, так что придётся ограничиться пятью первыми значениями: 2, 4, 7, 11, 16.

Обратим внимание: разности соседних чисел представляют собой последовательные натуральные числа, начиная с 2. Действитель­но, 4 - 2 = 2, 7 - 4 = 3, 11-7=4, 16- -11=5. Получается, что очередная, п-я по счёту прямая увеличивает число имевшихся до этого частей ровно на п. Убедимся, что так будет всегда.

Предположим, что п - 1 прямых уже есть и мы проводим ещё одну, начиная из бесконеч­ности. Новая прямая идёт по одной из облас­тей, на которые уже была разделена плоскость. Но вот она встретилась с какой-то прямой — и эта область разбилась надвое, т. е. появилась ещё одна часть. Прямая идёт дальше по оче­редной области и, встретившись со следующей прямой, разделяет надвое и эту область. Час­тей опять стало на одну больше. Таким обра­зом, новая прямая пересечётся по одному разу со всеми п - 1 прямыми, и при столкновении с последней, (п - 1)-й, число частей увеличится тоже на п - 1. Но на этом прямая не обрыва­ется: «распростившись» с последней из «ста­рых» прямых, она режет очередную область, уходя в бесконечность.

Итак, п-я прямая действительно увеличивает число частей на п, т. е. для любого п 1 спра­ведливо равенство х_п = х_n-1 + п. Остаётся най­ти формулу для х_n в зависимости от п. Испыта­ем формулу вида х_n = ап² + bп + с, где а, b, с — какие-то неизвестные пока числа. Их нужно подобрать так, чтобы выполнялись два условия:

1)х_n-х_n-1 = п(п 1),

2)х₁ = 2.

Поскольку

из первого условия получаем, что для любого п 1 должно выполняться равенство 2ап + (b -- -а) = п. Это возможно, только если 2а = 1 и b - а = 0. Значит, а =b= 1/2. Поэтому. Из второго условия следует, что х₁ = = 1² /2 + 1/2 + с = 2, откуда с = 1. Окончательно

Задача о разбиении пространства плоскостями

Теперь можно рассмотреть и пространствен­ный вариант этой задачи: требуется выяснить, на сколько частей (обозначим их у_n) разбива­ют пространство п плоскостей, если никакие две из них не параллельны, никакие три не пересекаются по одной прямой и никакие четыре не проходят через одну точку.

Допустим, п плоскостей уже имеется и про­странство разбито на y_n частей. Проведём ещё одну плоскость — (п + 1)-ю. Каждая из ранее построенных плоскостей пересекается с ней по какой-либо прямой, и эти п прямых разби­вают новую плоскость на х_n частей. А каждая из этих частей плоскости делит некоторую ранее «отрезанную» область пространства на две части. То есть (п + 1)-я плоскость увеличи­вает число частей ровно на х_п. Поэтому у_n+1 = = у_п + +х_n = у_n+ (п² + п + 2) / 2. Поскольку, кроме того, y₁ = 2, ясно, что данная формула позво­ляет вычислить у_n для любого сколь угодно большого п. Можно получить и явное выражение у_n через п, если по аналогии с предыдущей задачей искать у_n в виде у_n = an³ +bп² + сп + d.. Приводим результат:

Обобщённый факториал и числа Каталана

На окружности заданы 2п точек. Сколькими способами их можно попарно соединить с помощью п отрезков, чтобы никакие два от­резка не пересекались?

Обозначим искомое число способов через z_n. Предположив, что значения z₁ , z₂ , …, z_n из­вестны, найдём z_n+1. Расположим на окружности 2(п + 1) точек и выберем любую из них (точка А на рис. 4). Её можно соединить с любой из остальных точек. При этом проведён­ная хорда разобьёт оставшиеся точки на две группы. Точки, принадлежащие разным груп­пам, соединить нельзя — отрезок непременно пересечёт только что проведённую хорду. Зна­чит, остается как-то соединить точки в каждой группе между собой. Но если число точек в группах нечётное, то провести отрезки не удастся — одной точке не хватит пары. Следовательно, точку A можно соединять не с каждой из прочих точек, а через одну — так, чтобы 1-й и 2-й группах оказалось соответственно О и 2п точек; 2 и 2п - 2; 4 и 2п - 4; ...; 2п и 0. Если одной из групп 0 точек, то всё многообразие соединений дают 2п точек другой группы, и иx число равно 2_n. Если же в одной группе 2т ≠0 точек, а в другой 2(п - т) ≠0, то число возможных соединений становится равным

Отсюда получаем выражение для z_n+1:

Используя данную формулу, можно, начиная с z₁ = 1 , вычислить первые несколько значений z_п :

z₂=1 + 1 = 2,

z₃= 2 + 1 • 1 + 2 = 5,

z₄=5+ 1 • 2 + 2 • 1 + 5 = 14,

z₅ = 14 + 1 • 5 + 2 • 2 + 5 • 1 + 14 = 42.

Эти числа в XVIII в. рассматривал Леонард Эйлер, правда в связи с совершенно другой за- дачей. Он подобрал (как сам признался, с большим трудом) формулу для z_n:

В числителе дроби стоит так называемый обобщённый факториал.

Выражение k! означает, что перемножаются все натуральные числа подряд и наибольший из сомножителей равен k. Выражение k!! означает, что перемножаются натуральные числа через одно и наибольший сомножитель также равен k. Таким образом, если k чётное, то k!! есть произведение всех чётных чисел, не превышающих k (k!! = 2 • 4 • ... • k); если же нечётное, то это произведение всех нечётных чисел, не превышающих k (k!! = 1 • 3 •... × ×k). Аналогично, если после числа расположено три восклицательных знака, то нужно перемножать каждое третье число, а если четыре — каждое четвёртое. Применительно к нашему случаю имеем (4п - 2)!!!! = 2 • б • 10 •... • (4п - 2).

Числа z_n появляются в самых разных комбинаторных задачах. Их принято называть числами Каталана в честь бельгийского математика XIX в., хотя Эйлер открыл их раньше.

ЗАКЛЮЧЕНИЕ

Комбинаторные методы находят множество применений. Представителям самых различных специальностей приходится решать задачи, в которых рассматриваются те или иные комбинации, составленные из букв, цифр и иных объектов. Они используются для решения транспортных задач (в частности задач по составлению расписаний), для составления планов производства и реализации продукции, в теории случайных процессов, статистике, вычислительной математике, планировании экспериментов, шахматных программах для ЭВМ и т. д. Комбинаторика используется для составления и декодирования шифров и для решения других проблем теории кодирования и теории информации. Значительную роль комбинаторные методы играют и в чисто математических вопросах — при изучении конечных геометрий, теории групп и их представлений, неассоциативных алгебр и т. д. Сочетая комбинаторные рассмотрения с изучением рентгеновских снимков, ученым удалось разгадать строение гемоглобина, инсулина и др. Торжеством комбинаторного подхода к явлениям жизни можно считать расшифровку строения дезоксирибонуклеиновой кислоты (ДНК), сделанную в Кембридже Ф. Криком и Дж. Уотсоном в 1953 г. В физике комбинаторика оказывается необходимой при изучении свойств кристаллов, описании модели ферромагнетизма и т. д. Комбинаторика оказалась полезна Дмитрию Ивановичу Менделееву в открытии периодической системы элементов . Также комбинаторика дала возможность перечислить изомеры органических соединений данного состава.

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

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

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Виленкин Н.Я. и др. Алгебра и математический анализ для 11 класса: Учеб. пособие для учащихся шк. И классов с углубл. изуч. Математики / Н.Я.Виленкин., О.С.Ивашев-Мусатов, С.И.Шварцбурд. – М.: Просвещение, 1993. – 288с.

2. Макарычев Ю.Н. и др. Алгебра. 9 кл.: Учеб. для шк. и кл. с углубл. изуч. математики. – М.: Мнемозина, 2004. – 439с.

3. Макарычев Ю.Н., Миндюк Н.Г. Алгебра: Элементы статистики и теории вероятностей: Учеб. пособие для учащихся 7-9 кл. общеобразоват. учреждений / Под. ред. С.А.Теляковского. – М.: Просвещение, 2003. – 78с.

4. Мордкович А.Г., Семенов П.В. События. Вероятности. Статистическая обработка данных: Доп. параграфы к курсу алгебры 7-9 кл. общеобразоват. учреждений. – М.: Мнемозина, 2004. – 112с.

5. Решение задач по статистике, комбинаторике и теории вероятностей. 7-9 классы / Авт.-сост. В.Н.Студенецкая. – Волгоград: Учитель, 2005. – 429с.

6. Ткачева М.В., Федорова Н.Е. Элементы статистики и вероятность: Учеб. пособие для 7-9 кл. общеобразоват. учреждений. – М.: Просвещение, 2004. – 112с.

7. www.bymath.net/studyguide/alg/sec/alg31.html

8. www.math4you.ru/theory/TerVerMatStat/TerVerKom/ 

9. www.pm298.ru›Формула Ньютона

19