10. Определение поля

Полем   называют коммутативное кольцо с единицей, в котором каждый ненулевой элемент имеет мультипликативный обратный элемент (т.е. обратный по умножению).

Другими словами, полем называют множество, которое является аддитивной абелевой группой; ненулевые же элементы этого множества образуют мультипликативную абелевую группу, и выполняется закон дистрибутивности.

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

Отметим некоторые свойства полей, вытекающие из их определения.

1. Для любого элемента поля  .

2. Для ненулевых элементов   и   поля  .

3. Для любых элементов   и   поля  .

4. Если   и  , то  .

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

Пример 5.11. Множество чисел  , где   – простое число, образует конечное поле, в котором сложение и умножение производятся по модулю  .

Пример 5.12. При   имеем простейшее двоичное поле, состоящее из двух элементов 0 и 1. Эти элементы являются соответственно единичными элементами относительно операций сложения и умножения по модулю 2, которые определяются правилами:  ;  ;  ;  ;  . Так как  , то операции сложения и вычитания в двоичном поле совпадают, а так как  , также совпадают операции умножения и деления. Это поле находит широкое применение в теории и технике помехоустойчивого кодирования. 

11. Перестановки

Перестановки. Перестановкой называется расположение элементов множества в определенном порядке.

Теорема. Число перестановок n-элементного множества S, т.е. число способов его упорядочивания выражается формулой P_n=n!.

Символом n! обозначается произведение натуральных чисел от 1 до n: n!=1×2×...×n. Считается, что 0!=1.

Доказательство. Будем последовательно выбирать элементы множества S и располагать их в определенном порядке на n местах. На первое место можно поставить любой из n элементов. После того, как заполнено первое место, на второе место можно поставить любой из оставшихся n-1 элементов и т.д. Тогда по правилу произведения все n мест можно заполнить n×(п-1)×(п-2)×...×2×1=n! способами. Следовательно, n-элементное множество можно упорядочить n! способами.

12.Перестановки с повторениями

Перестановки с повторениями. Перестановкой с повторениями называется расположение элементов мультимножества в определенном порядке.

Теорема. Число перестановок с повторениями для мультимножества   выражается формулой

 ,

где   .

Доказательство 1. Рассмотрим одну перестановку мультимножества и заменим в ней все одинаковые элементы разными. Тогда, число различных перестановок, которые можно составить из рассматриваемой перестановки, равно k₁!×k₂!×…×k_m!. Проделав это для каждой перестановки, получим n! перестановок. Следовательно,

C_n(k₁,k₂,…,k_m)×k₁!×k₂!×…×k_m!=n!,

  

Число C_n(k₁,k₂,…,k_m) называется полиномиальным коэффициентом. Приведем еще одно доказательство данной теоремы.

Доказательство 2. Для упорядочивания мультимножества необходимо из n мест выбрать k₁ мест для элемента s₁, что можно сделать   способами, затем из n-k₁оставшиеся мест выбрать k₂ мест для элемента s₂, что можно сделать   способами и т.д. Тогда число способов упорядочивания мультимножества S по правилу произведения равно (напомнив, что 0!=1)

 .