Математика · объяснение и практика

Как коэффициент произведения кодирует набор допустимых выборов

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

Синяя и оранжевая половины складываются в целый круг.

В теме Доказательства и комбинаторные модели · Учебная карта

В маршруте Счёт через устройство объектов · 10 тем

Главная мысль

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

Степень хранит вклад, коэффициент — число способов

Пусть первая коробка может получить ноль, один или два одинаковых жетона. Её варианты кодирует 1+x+x². Вторая получает ноль или два, поэтому ей соответствует 1+x². Чтобы описать совместный выбор, выражения перемножают: из каждого множителя берут один член, а степени складываются как суммарное количество жетонов.

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

Ограничения остаются внутри множителей

Добавим третью коробку с количествами от нуля до трёх. Для суммы четыре нужно найти коэффициент x⁴ в (1+x+x²)(1+x²)(1+x+x²+x³). Если вторая коробка получает ноль, возможны пары первой и третьей (1,3),(2,2). Если она получает два, подходят (0,2),(1,1),(2,0). Всего пять наборов.

Такая запись естественно учитывает запрещённые промежуточные количества. Для второй коробки нет члена x, поэтому единица не появляется скрыто при вычислении. Разные обязательные минимумы задаются дополнительными степенями: x²(1+x+x²) означает допустимые количества два, три, четыре. Конечная вместимость требует конечного множителя, а не безграничной геометрической суммы.

Пример

Первый выбор имеет величину 0,1,2, второй — 0,2. Сколько сочетаний дают сумму два?

Коэффициент x² в (1+x+x²)(1+x²) равен двум: подходят (2,0) и (0,2). Пара (1,1) запрещена отсутствием единицы во втором выборе.

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

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

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

От чтения к действию

А теперь — вы

Первый выбор принимает значения 0,1,2, второй — 0,1,2,3. Каков коэффициент x³ в (1+x+x²)(1+x+x²+x³)?

Частые вопросы

Почему в множителе есть единица?

Она означает разрешённый нулевой вклад: x⁰=1. Если пустой выбор запрещён, постоянный член нужно убрать.

Можно ли использовать коэффициенты больше единицы сразу?

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

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться