Требуется найти число различных многочленов степени n из F[x], которые не имеют корней. С какой стороны подойти к решению?

задан 6 Сен '18 22:36

Я думаю, что если про поле F не известно, что оно конечное, то ничего "умного" здесь сказать нельзя.

(6 Сен '18 23:53) Sunbro
10|600 символов нужно символов осталось
1

Судя по условию, поле $%F$% предполагается конечным. Пусть его порядок равен $%q$% (степени простого числа). Будем находить число многочленов без корней в поле при условии, что старший коэффициент многочлена равен 1. Общее количество получается домножением на $%q-1$% (число ненулевых элементов поля).

Применим формулу включений и исключений, вводя множества $%A_i$% тех многочленов, которые имеют $%i$%-й по счёту корень ($%1\le i\le q$%). Элементы поля при этом предварительно нумеруем от 1 до $%q$%.

Нам требуется найти мощность дополнения множества $%|A_1\cup\cdots\cup A_q|$%. По формуле, из общего числа многочленов (степени $%n$% со старшим коэффициентом 1), равного $%q^n$%, нужно вычесть знакочередующуюся сумму $%|A_1|+\cdots+|A_q|-|A_1A_2|-|A_1A_3|-\cdots-|A_{q-1}A_q|+\cdots$%. Заметим, что $%|A_i|=q^{n-1}$% в силу теоремы Безу: многочлен степени $%n$% с фиксированным корнем $%\alpha$% равен произведению $%x-\alpha$% на многочлен $%(n-1)$%-й степени. Аналогично, мощности попарных пересечений все равны $%|A_iA_j|=q^{n-2}$% при $%i < j$%, мощности тройных пересечений равны $%q^{n-3}$% и так далее. Само число $%k$%-кратных пересечений равно $%C_q^k$%; эта величина равна нулю при $%k > q$%.

Итого мы получаем $%q^n-q\cdot q^{n-1}+C_q^2q^{n-1}-\cdots+(-1)^kC_q^kq^{n-k}+\cdots$%, где $%k\le n$%. Первые два члена сокращаются, и мы имеем ответ $$\sum\limits_{k=2}^n(-1)^kC_q^kq^{n-k}.$$

Заметим, что при $%n=1$% количество многочленов без корней равно нулю, при $%n=2$% будет $%\frac{q(q-1)}2$%, при $%n=3$% получается $%\frac{(q+1)q(q-1)}3$%, но далее выражения постепенно усложняются. При $%n=4$% будет $%\frac{q(q-1)(3q^2+q+2)}8$%, при $%n=5$% ответ равен $%\frac{(q+1)q(q-1)(11q^2-5q+6)}{30}$%, то есть общий ответ вряд ли хорошо может "сворачиваться".

ссылка

отвечен 6 Сен '18 23:55

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×4,177
×366
×62

задан
6 Сен '18 22:36

показан
135 раз

обновлен
6 Сен '18 23:55

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru