Введение в комбинаторику

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

Этот раздел – комбинаторика, “наука о способах подсчета вариантов”. Эта наука имеет тот же, примерно 300 летний возраст, что и сама статистика. Комбинаторика – сверстница теории вероятностей, теоретического фундамента прикладной статистики. Как и в древней, в современной статистике невозможно обойтись без навыков просчитывать в уме или, по крайней мере, быстро, по простым формулам, варианты событий, размещений предметов, значений величин и т.п.

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

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

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

· Вам, очевидно, известно, что внутренний, “машинный” язык компьютера люди построили по образу и подобия человеческого языка: буквы, слова, предложения.

Обстоятельства надежности записи и чтения на этом языке привели к решению сделать компьютерный язык предельно бедным. В нем всего две буквы (“0” и “1”, “+ " и “–”, “да” и “нет”, ­– в зависимости от физического процесса записи), всегда 8 букв в слове, отсутствует пробел между словами (это была бы третья буква).

И вот возникает вопрос ­– а сколько вариантов у машинного слова, т.е. у одного байта? Еще проще – если одним байтом записывать числа, то сколько положительных целых чисел можно охватить 1 байтом? В поисках ответа можно терпеливо выписывать все возможные варианты слов из 8 нулей и единиц: 00000000, 00000001, 00000010 и т.д. до 11111111. Но ведь это долго и надо быть уверенным, что ничего не пропустили!

Так вот – законы комбинаторики позволяют мгновенно ­решить эту задачу и получить ответ – вариантов записи байта ровно 256.

Это чисто практический вопрос – ведь компьютер с возможностью считать в целых числах от –128 до 127 никто не купит.

Ну, если целые числа хранить в 2-х машинных словах, в 2-х байтах или в 16 “разрядах”.? Уж это новое число вариантов никто не согласится вычислять простым перебором! А ответ комбинаторики все тот же прост – в этом случае есть возможность работать с целыми числами от –32768 до 32767.

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

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

Для решения вопроса можно нарисовать выпуклый 25–угольник и провести в нем все диагонали, пересчитав в конце их число и не забыв добавить число сторон. Человек, знающий комбинаторику, во-первых, не сделает ошибки –25·24=600 каналов. Во-вторых, он мгновенно укажет верный ответ – всего требуется 300 каналов. Комментарии излишни…

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

Перестановками называют операции над упорядоченным рядом из n различных объектов, в процессе которых “списочный состав” ряда не изменяется, но “места” объектов в этом ряду изменяются от варианта к варианту. Не будем тратить время на обоснование расчетной формулы для произвольного n, а попробуем найти число перестановок в ряду из 1, 2 и 3 предметов.

Воспользуемся для этого простенькой схемой:

n=1 A 1 вариант.

n=2 AB BA 1·2= 2 варианта.

n=3 ABC ACB BCA BAC CAB CBA 1·2·3= 6 вариантов.

Можно доказать строго, что в общем случае число перестановок в ряду из n элементов составит

{8–1}

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

Опустим доказательство формулы для расчета числа сочетаний из n по k в общем виде и приведем лишь примеры для числа сочетаний из 3 по 2 и из 5 по 3.

· Элементы исходного множества A, B, C.

Варианты подмножеств: AB, AC, BC – всего три.

· Элементы исходного множества A, B, C, D, E.

Варианты подмножеств: ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE – всего десять.

В общем случае число вариантов сочетаний или просто – число сочетаний из n по k определяется по формуле

= {8–2}

Существует еще один способ вычисления числа сочетаний из n по k – с использованием коэффициентов в развернутой форме бинома (p+q)ⁿ. В самом деле, например, при n=3 коэффициенты при степенях разложения составляют 1, 3, 3, 1 – а это и есть сочетания из 3 по 0, 1, 2, 3 и 4 элементов.

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

Для n

Первый элемент любого основания равен 1, второй – номеру основания, а все последующие – сумме двух "вышестоящих".