Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Функция Мёбиуса. Формула обращения МёбиусаСодержание книги
Поиск на нашем сайте
Функция Мёбиуса натурального аргумента определяется следующим:образом: Первые 13 значений
Далее символ означает, что суммирование распространяется на все натуральные делители числа . Лемма. Доказательство. Для утверждение очевидно. Пусть и − каноническое разложение числа . Тогда, учитывая, что делители имеют вид , где , ,…, ; , получаем
поскольку Теорема. (Аддитивная формула обращения Мёбиуса.) Пусть и − функции натурального аргумента . Тогда, если то Доказательство. Имеем Пусть . Тогда прификсированном пробегает все значения делителей числа . Это означает, что знаки суммирования в последней двойной сумме можно поменять местами, т.е. Теперь, учитывая, что получаем Имеется другая форма доказанной теоремы: Теорема. (Мультипликативная формула обращения Мёбиуса.) Пусть где символ обозначает произведение, распространенное на все делители числа . Тогда Доказательство: Примеры использования формулы обращения Мёбиуса: . Задача о числе кольцевых последовательностей. См.: Холл М. Комбинаторика. М.: Мир, , § . . Число неприводимых многочленов заданной степени над конечным полем из элементов. См.: Берлекэмп Э. Алгебраическая теория кодирования. − М.: Мир, 1970, Гл. 3. Глухов М. М., Елизаров В. П., Нечаев А. А. Алгебра. В -х т. М.: Гелиос, . Т. , § . Для самостоятельного изучения: Обращение Мёбиуса на частично упорядоченных множествах. Принцип включения-исключения как частный случай формулы обращения Мёбиуса. См.: Холл М. Комбинаторика. М.: Мир, , § ; Бендер Э., Гольдман Дж. О приложениях обращения Мёбиуса в комбинаторном анализе. В кн.: Перечислительные задачи комбинаторного анализа. М.: Мир, 1971. С. - . Сравнения для чисел сочетаний Пусть − простое число. Лемма. Доказательство. При числитель в формуле Следствие. Доказательство. Лемма. Пусть , , , − неотрицательные целые числа, причем , . Тогда Доказательство. Имеем С другой стороны, Сравнивая коэффициенты при одинаковых степенях , получаем требуемый результат. ∎ Пусть , ; , − представления неотрицательных целых чисел и по основанию . (Здесь любое целое, при котором , ). На множестве неотрицательных целых чисел определим отношение частичного порядка (отношение предшествования) , полагая , тогда и только тогда, когда , ,…, Теорема Лукаса ( ). Доказательство. Согласно предыдущей лемме, где , . Применяя лемму повторно к надлежащее число раз, получаем требуемый результат. ∎ Замечание. Теорема не верна для непростых . Например (см. Берлекэмп, с. ), Следствие. II. Алгебраические структуры II. 1. Множества с бинарными операциями. Группоиды, полугруппы, моноиды Бинарной алгебраической операцией (или законом композиции) на непустом множестве S называется отображение : , сопоставляющее паре , элементов , однозначно определённый элемент , . На множестве может быть задано много операций . (Если, например, конечно, то число способов равно , где − число элементов в .) Желая выделить одну их них, например, , пишут , . Такой объект называют бинарной алгеброй, или группоидом. Вместо , часто пишут , а саму операцию обозначают каким-либо символом (, , , и т.п.). Замечание. Наряду с бинарными операциями рассматривают более общие -арные операции (унарные при , тернарные при и т.д.). Связанные с ними алгебраические структуры (системы) составляют предмет исследования т.н. универсальных алгебр. Бинарная операция на множестве называется ассоциативной, если , для любых , , . Группоид с ассоциативной операцией называют полугруппой. Пример неассоциативного группоида. На множестве определим операцию как . Операция неассоциативна: , но . Теорема. Если бинарная операция на множестве ассоциативна, то значение выражения не зависит от расстановки в нём скобок. Доказательство. При , или утверждение очевидно. Для достаточно, применяя индукцию, показать, что
для любых , . По предположению индукции расстановка скобок в не существенна; в частности, . Если , то . Если , то . К такому же виду приводится и правая часть доказываемого равенства (1). ∎
Элемент называется нейтральным относительно операции , если для любого . Полугруппу , с элементом называют моноидом (или полугруппой с единицей) и обозначают , , . В полугруппе (группоиде) может быть не более одного нейтрального элемента: если , − нейтральные элементы, то Группоид (полугруппу) , называют подгруппоидом (подполугруппой) группоида (полугруппы) , , если и для любых , . В этом случае говорят, что подмножество замкнуто относительно операции . Моноид , , называют подмоноидом моноида , , , если выполняется и . Элемент моноида , , называется обратимым, если найдётся элемент такой, что (очевидно, что тогда и обратим). Если таким же свойством обладает и элемент , т.е. , то из равенств следует, что элемент является на самом деле единственным (по отношению к ). Это позволяет говорить об обратном элементе , к(обратимому) элементу , со свойствами: , . Если , − обратимые элементы моноида , , , то их произведение − также обратимый элемент, поскольку , . Очевидно, что − обратимый элемент. Следовательно, имеет место Теорема. Множество всех обратимых элементов моноида , , замкнуто относительно операции ∗ и образует подмоноид в , , .
Группы Определение группы. Моноид , , , все элементы которого обратимы, называется группой. Другими словами, группа − это множество с бинарной операцией , для которых выполняются следующие аксиомы: . (Замкнутость операции.) , . . (Ассоциативность операции.) , . (Существование нейтрального элемента.) ∃ . . (Существование обратного элемента.) . Замечание. Возвращаясь к введённым выше алгебраическим структурам, мы наблюдаем среди них следующую иерархию: пара , является группоидом, если выполняется аксиома ; полугруппой, если выполняются аксиомы и ; моноидом, если выполняются аксиомы , и ; группой, если выполняются аксиомы , , и . Удобно считать, что наряду с бинарной операцией в группе определена унарная операция взятия обратного : , . Справедливы формулы: , . Естественным образом определяются степени элементов с очевидными свойствами: ( раз), ( раз), , ; , (, , . Переставлять элементы в выражении , вообще говоря, нельзя (т.е. ). Если , то элементы называются перестановочными, или коммутирующими. Если любые два элемента группы коммутируют, то группа называется коммутативной, или абелевой (в честь норвежского математика Риль Хенрика Абеля ( - )). Операция в группе чаще всего обозначается либо символом (сложение), либо символом (умножение). При этом группа называется соответственно аддитивной или мультипликативной, её нейтральный элемент − соответственно нулём () или единицей (). В аддитивной группе элемент, элемент, обратный к элементу , называется противоположным и обозначается , а вместо пишут . В мультипликативной группе вместо обычно пишут , опуская символ операции. Примеры аддитивных групп. 1) , , , , , , , – аддитивные группы кольца и полей , , . Пишут просто , , , . 2) Любое кольцо по сложению − абелева группа. В частности, кольцо многочленов ,…, ] и кольцо матриц , порядка над полем − абелевы группы. 3) Любое векторное пространство над полем относительно сложения − абелева группа. 4) , 1,…, − полная система наименьших неотрицательных вычетов по модулю с операцией сложения по модулю . Примеры мультипликативных групп. 1) , , − мультипликативные группы полей , , . 2) − множество обратимых элементов любого кольца с единицей относительно умножения. В частности, = ; , − множество обратимых матриц из . 3) − всех (вещественных и комплексных) корней , , 1,…, , − мнимая единица, уравнения − мультипликативная абелева группа. 4) − множество вращений правильного -угольника в плоскости и в пространстве − некоммутативная группа (при ).
Далее чаще используется мультипликативная форма записи операции. Группа обычно обозначается одной буквой без указания операции. Множество всех элементов группы называется основным множеством группы и обозначается той же буквой . Если основное множество конечно, то группа называется конечной; в противном случае она называется бесконечной. Число элемент конечной группы называется её порядком. Группа порядка 1 называется единичной, или т ривиальной. О бесконечной группе говорят, что она имеет бесконечный порядок. Для обозначения порядка группы (мощности основного множества) используются равноправные символы Card (кардинальное число), и (). Если , − подмножества (основного множества) группы, то полагаем , , . Подгруппой группы называется подмножество в само являющееся группой относительно той же операции, что и в . Другими словами, подмножество является подгруппой тогда и только тогда, когда ( единица в ) и замкнуто относительно умножения и взятия обратного, т.е. , (на самом деле здесь даже равенства). Если − подгруппа в , то пишут ; если при этом , то называется собственной подгруппой и это обозначается как . Примеры.
|
||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2016-12-13; просмотров: 1021; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.116.43.109 (0.015 с.) |