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

Рассмотрим в качестве примера "магический квадрат", у которого суммы чисел по строкам, столбцам и диагоналям равны, а сами числа должны составлять натуральный ряд: 1, 2, 3, . . . A ², где A - длина стороны квадрата, выраженная числом клеток. Магический квадрат со строной A = 3 показан на рис. 12.1.

С этой старинной головоломкой можно связать различные задачи абстрактно-математического характера. Можно, например, заняться поиском формального алгоритма составления магических квадратов, но эта задача будет лишь отчасти комбинаторной. Можно определить в общем виде сумму чисел, которая по определению должна быть постоянной величиной для магического квадрата с заданной стороной А. Числа в клетках образуют арифметическую прогрессию с разностью, равной единице и числом членов, равным А². Искомая сумма определится как сумма прогрессии, деленная на А:

m множеств с мощностями соответственно n₁, n₂, ...n_m состоит из кортежей длиной m. На первом месте в каждом таком кортеже стоит один из элементов множества М₁, на втором - элемент из М₂, и т.д.

Для решения поставленной задачи соберем все кортежи с одинаковыми первыми элементами в отдельные классы. Всего таких классов очевидно будет n₁, по числу элементов во множестве M_1.. Внутри каждого класса произведем разбиение по второму элементу кортежа. Число таких подклассов (внутри каждого класса) будет равно n₂. Действуя далее аналогично, мы дойдем до подклассов самого низшего уровня, в каждом из которых будет только по одному кортежу. В итоге общее количество кортежей, т.е. элементов декартова произведения, составит

Эта формула дает готовые ответы на вопросы вроде следующих: “Сколько существует различных трехзначных десятичных чисел?”, “Сколько можно придумать четырехбуквенных слов в русском алфавите?”. Решим с ее помощью задачу о числе различных булевых функций от k аргументов. Ряд значений аргументов булевой функции представляет двоичный цифровой кортеж длиной k. Всего таких кортежей согласно полученной нами формулы будет 2^k. Чтобы задать одну функцию, нужно записать ряд её двоичных значений. В этом ряду будет столько цифр, сколько существует кортежей значений аргументов, т.е. тоже 2^k. Всего разных функций наберется столько же, сколько существует различных двоичных кортежей длиной 2^k, т.е. . Это - очень быстро растущая функция. При k = 1 получается всего 4 функции, а при k = 4 - уже 65 536.

Размещения без повторений получаются из конфигураций предыдущего вида, если исключить из декартовой степени все кортежи с повторяющимися элементами. Чтобы определить число таких конфигураций, разобьём их множество на классы с одинаковыми первыми элементами. Поскольку число таких элементов равно n, то и классов будет n. На втором шаге разобъем каждый класс на подклассы по второму элементу. Так как элементы не должны повторяться, а один из них уже стоит на первом месте в кортеже, то подклассов на втором шаге разбиения будет только n - 1. На третьем шаге получим n -2 и т.д. Последний, m - ый элемент можно будет выбрать n - (m - 1) способами, ведь m - 1 элементов уже занято. По этим рассуждениям составляется формула, которую приходится упрощать искусственным способом:

Частный случай размещения без повторений получается при n = m, т.е. когда число элементов в исходном множестве совпадает с длиной рассматриваемых кортежей. Размещения этого вида называются перестановками, а их число обозначается

Другой вид конфигураций получим, если будем рассматривать не кортежи, а неупорядоченные подмножества. Они называются сочетаниями из n элементов по m. Число С_n^m различных сочетаний из по m определим из следующих соображений. Если бы это были не множества, а кортежи длиной m, то их число равнялось бы

При переходе от кортежей к неупорядоченным множествам число конфигураций должно уменьшиться. Ведь из всех выборок, отличающихся только порядком перечисления элементов, нужно оставить только одну. А мы уже знаем, что число конфигураций, отличающихся только порядком элементов равно P ^m = m!. Следовательно, число сочетаний равно

Из доказанного равенства вытекает, что биномиальные коэффициенты можно находить последовательно, один за другим, увеличивая n и m и суммируя найденные значения. Этот алгоритм наглядно описывается треугольной таблицей, называемой "треугольником Паскаля", в которой n- это номер строки, а m - номер числа в строке (начиная с m=0) Треугольник Паскаля до n = 4 показан на рис. 12.2. каждый элемент треугольника представляет сумму двух ближайших элементов из предыдущей строки.

Рассмотрим ещё один вид конфигураций. Нам уже известно, что разбить заданное множество М на классы можно разными способами. Найдем число всех разбиений на k классов с заданными мощностями m₁, m₂,...m_k. При этом, согласно определения операции разбиения должно соблюдаться равенство m₁ + m₂ + ...+m_k = n.

Рассуждения будем строить по правилу умножения. Для составления класса М₁ нужно отобрать m₁ элементов исходного множества М. Число вариантов такого выбора равно числу сочетаний

Для составления класса М₂ придется подбирать элементы из числа оставшихся n - m₁. Следовательно, число сочетаний в этом случае выразится

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

Содержание