3.4. Обобщенное правило произведения

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

Пусть количество элементов множества с весом тогда сумма весов элементов множества

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

Положим вес элемента множества равным

Пусть количество элементов с весом тогда сумма весов элементов множества

Теорема.

Доказательство.

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

(см. скан)

Решение. Исходное положение — вершина Каждый шаг движения по кубу — это выбор одного из трех ребер. Пусть 1 обозначает выбор ребра вдоль оси вдоль оси вдоль оси . В соответствии с этим введем множества такие, что Тогда все маршруты длины составят множество Например, маршрут 2113 означает, что из, пошли затем в вернулись и поднялись в

Назначим веса элементам множества: По правилу обобщенного произведения сумма весов всех маршрутов длины равна

После возведения в степень получим, что

где вес маршрута, включающего шагов вдоль оси вдоль — вдоль количество маршрутов с весом

Заметим, что только маршрут, заканчивающийся в имеет вес с четными степенями в замкнутом маршруте, сделав шаг вдоль оси, необходимо вернуться по этой оси. Для выделения таких маршрутов положим ( — произвольные). Тогда выражение (3.4.1) примет вид

где число маршрутов, заканчивающихся

Учитывая симметрию точек относительно можно заключить, что Тогда из системы (3.4.2) следует, что

Уравнение (3.4.3) содержит два неизвестных и С при Для их определения составим систему уравнений из выражения (3.4.3), полагая Это возможно, выполняется условие Получим систему

Отсюда число искомых маршрутов.

Задача. Найти число решений уравнения

Решение. Введем множества:

Назначим веса элементам данных множеств следующим образом:

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

Раскроем выражение

где число решений уравнения Фактически, сумма весов элементов множества является производящей функцией числа решений уравнения Таким образом, Разложим данное выражение на множители:

где число решений уравнения

Сравнивая коэффициенты при одинаковых степенях получим:

где