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

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

Сумма, разность и произведение канонических многочленов также приводятся к каноническому виду. Если g(x) = b0 + Ь}х + ... + bnrxm, т <п, го канонический вид суммы:

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

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

7=0

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

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

(iv..ik)eN$

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

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

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

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

Если g(x{, хк) = ? bjX'jkxJ1 ...х?, то канонический вид суммы мно-

(iv..ik)G'b

гочленов:

Канонический вид произведения многочленов можно вычислить, умножив с соответствующими коэффициентами каждый моном многочлена f(xb ...Ухк) на каждый моном многочленаg(xv...,xk), гneai{ ikx[{ ...xfb^ jkx{1 ...xJkk = = ikbj^ jkX+Ji —xl^Jk, записав сумму всех получившихся мономов с коэффициентами и приведя подобные мономы (т.е. сумму мономов вида ах1... х% + Ьх[1 ... х1? + ... записав как + Ъ + ...)х[{ ...х%). Степени суммы и произведения полиномов определены формулами (1.7) и (1.8).

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

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

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

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

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

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

п

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

i=1

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

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

Пример 1.7 (задача о размене доллара)

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

Задача сводится к нахождению коэффициента ат при х100 в ряду /(х), который равен коэффициенту Я|00 при х100 в многочлене (1 + х+ ... + х100)(1 + х5 + ... + х100) ... ... (1 +х50 + х100). Вычисления упрощаются при использовании рекуррентных соотношений. В частности, величина («,00 - 1) равна сумме коэффициента при х100 в многочлене (1 + х +... + х,00)( 1 + х5 +... + х100)( 1 + х10 +... + х100)( 1 + х25 +... + х100) и коэффициента при х50 в многочлене (1 + х + ... + х50)(1 + х5 + ... + х50)(1 + х10 + ... + х50) (1 + х25 + х50). В результате подсчета ат = 292. >

  • [1] Более общее определение дается для многочлена над кольцом, определение кольца см.в параграфе 2.2.
  • [2] Более общее определение дается для многочлена над кольцом, определение кольца см.в параграфе 2.2.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >