Многочлены, формальные степенные ряды, нумераторы

Формула вида /(х) = а₀+ а_хх + … + a_tJxⁿ, где х, а₀, а_{, а_п е Z (или R), а_п Ф 0 и х — переменная, называется каноническим многочленом (полиномом)) над Z (над К)К Числа а₀, …, а_п называются коэффициентами многочлена /(х), в частности а_п — старшим коэффициентом, я₀ — свободным членом. Число п называют степенью многочлена f (x) и обозначают deg/(x). Многочлен х^к называется одночленом или мономом степени к > 0, и а_к называется коэффициентом при мономе x^k в многочлене f (x). Многочлен над R называется действительным многочленом.

Сумма, разность и произведение канонических многочленов также приводятся к каноническому виду. Если g (x) = b₀ + Ь_}х + … + b_nrx^m, т <�п, го канонический вид суммы:

где bj = 0 для i > т. Канонический вид произведения многочленов: i.

где с_{ = X ^ajbj-j для всех i = 0, 1,т: -г п. В частности, af (x) = аа₀ + аа_{х +.

7=0.

+ … + aa_tTxⁿ для а е R. Отсюда выполнены свойства:

Канонический многочлен f (x_{, …, x_k) над множеством R от переменных х_х,…, x_k — это выражение вида: f (x_v…, x_k) =? …xj*, где xf = 1.

(i_v.i_k)eN$

при i = 1,…, ky элементы а_У| ^ из /? называются коэффициентами многочлена

(в частности, а_{0 0} — свободный член), и только конечное число коэффициентов отлично от нуля.

Многочлен xj^[1] … xjf называется одночленом или мономом степени ?'=ц +… + + i_k > 0, и a_{i{ j/f} называется коэффициентом при мономе xj^[1] … xjf в /(x_t,…, х*). Степенью многочлена /(х_1? …, х*) (обозначается deg/(x_t, …, х^,)) называется наибольшая из степеней его мономов с ненулевыми коэффициентами.

Множество всех многочленов над Z (над R) от переменных x_v …, x_k обозначим Z[x_v …, x_k] (R[x_v …, x_k]). Такие многочлены также можно складывать и умножать, приводя к каноническому виду.

Если g (x_{, х_к) =? bj_X'j_kxJ¹ …х?, то канонический вид суммы мно;

(i_v.i_k)G'b

гочленов:

Канонический вид произведения многочленов можно вычислить, умножив с соответствующими коэффициентами каждый моном многочлена f (x_b …_Ух_к) на каждый моном многочленаg (x_v…, x_k), гnea_{i{ ik}x[^{ …xfb^ j_kx{¹ …x^J_k^k = = _ikbj^ j_kX^+Ji —x^l^^Jk, записав сумму всех получившихся мономов с коэффициентами и приведя подобные мономы (т.е. сумму мономов вида ах¹… х% + Ьх[¹ … х¹? + … записав как {а + Ъ + …)х[^{ …х%). Степени суммы и произведения полиномов определены формулами (1.7) и (1.8).

Формальный степенной ряд над R от переменной х — это бесконечная сумма вида f (x) = а₀ + а_хх +…+ а, рс^п +…, где х — переменная, а₀, а_Л, …, а_п — элементы множества /?, называемые коэффициентами ряда. Коэффициенты суммы и произведения рядов вычисляются, как для многочленов. Аналогично определяются формальные степенные ряды над R от нескольких переменных.

Выборку т элементов из множества и размещение их по п классам (неограниченным ячейкам) в комбинаторике называютурновой схемой. Обычно интересуются количеством заполнений предметов в ячейки, когда заполнения удовлетворяют некоторым ограничениям. Всевозможные заполнения, интерпретируемые как события, образуют полное множество событий, т. е. при реализации урновой схемы неизбежно реализуется одно из событий полного множества. Полному множеству событий соответствует формальный многочлен или формальный ряд, в зависимости от того, конечное или бесконечное множество событий. Например, событию А с полным множеством взаимоисключающих событий х_{, …, х_п соответствует формальный многочлен f_A(X_y…, х_п) = х_{ -г … + х_п, называемый нумератором события А. Если ЛВ обозначает одновременную реализацию событий А и В, то нумераторы событий А + В и АВ, где f_B(y_{,…, у_т) = У + … + у_т, имеют выражения.

Используем нумератор для решения перечислительных задач.

Пусть множество исходов состоит из всех неупорядоченных выборок без возвращения из {1, …, п}, Ai — событие, связанное с включением или не включением i в выборку, i е {1, …, п]. Исход «включение i» в выборку обозначим x_iy и исход «невключение г» обозначим 1. Тогда нумератор выборки произвольного набора из {1,…, п} есть /_Л1. ._Л/7 = (1 +*i)-(l + х_п).

Число выборок размера k равно числу мономов степени k в канонической форме многочлена (1 +х₁)…(1 +х_п), т. е. равно C^k_n.

Нумератор события, связанного с включением i в выборку с повторениями, есть /_; = 1 + Xj + х? + …, i = 1, …, п. Число выборок размера k есть.

п

число мономов степени k в формальном ряду f-f_n = П (1 ^{+ :}Ч + ^х? -к.), рав;

i=1.

ное коэффициенту % при х* в ряду (1 + х + х² + …)". Поскольку 1 + х + + х²+…= 1/(1 — х), то для определения a_k используем разложение в степенной ряд (Тейлора — Маклорена) функции 1/(1 — х)^п, имеющее вид.

• —1 ₌ у (^{п +} к 1)• _хк Следовательно, а_к = С* = С* _b <.
• (1 -ХУ &(n-t)ki ^{к п м}

Пример 1.7 (задача о размене доллара) Определим, сколькими способами можно разменять 1 доллар, используя монеты достоинством 1, 5, 10, 25 и 50 центов. Обозначим /,(х) нумератор события «выбор монеты i центов»,/(.г) = 1 + х' + х²'+…, i е {1,5, 10, 25, 50}. Тогда нумератор/(х) всех наборов монет имеет вид.

Задача сводится к нахождению коэффициента а_т при х¹⁰⁰ в ряду /(х), который равен коэффициенту Я|₀₀ при х¹⁰⁰ в многочлене (1 + х+ … + х¹⁰⁰)(1 + х⁵ + … + х¹⁰⁰) … … (1 +х⁵⁰ + х¹⁰⁰). Вычисления упрощаются при использовании рекуррентных соотношений. В частности, величина («,₀₀ — 1) равна сумме коэффициента при х¹⁰⁰ в многочлене (1 + х +… + х^{, 00})(1 + х⁵ +… + х¹⁰⁰)(1 + х¹⁰ +… + х¹⁰⁰)(1 + х²⁵ +… + х¹⁰⁰) и коэффициента при х⁵⁰ в многочлене (1 + х + … + х⁵⁰)(1 + х⁵ + … + х⁵⁰)(1 + х¹⁰ + … + х⁵⁰) (1 + х²⁵ + х⁵⁰). В результате подсчета а_т = 292. >

• [1] Более общее определение дается для многочлена над кольцом, определение кольца см. в параграфе 2.2.
• [2] Более общее определение дается для многочлена над кольцом, определение кольца см. в параграфе 2.2.