2.1.14. Контрольные вопросы и упражнения

1. Выборка, среди элементов которой нет одинаковых, а порядок записи элементов важен, является ______________________ .

2. Выборка, среди элементов которой нет одинаковых, а порядок записи элементов безразличен, является ________________________ .

3. Количество размещений с повторениями из nэлементов поrэлементов определяется по формуле

__________ = ________________________ .

4. Количество сочетаний из nэлементов поrэлементов определяется по формуле

____________ = ________________________ .

5. Сформулируйте основные правила комбинаторики.

6. Сколькими способами можно выбрать конверт и марку для письма, если имеется 5 конвертов и 4 марки?

7. Сколько пятизначных номеров можно составить из девяти цифр {1,2,3,4,5,6,7,8,9}?

8. Сколькими способами можно составить трехцветный полосатый флаг (все полосы горизонтальные), если имеются ткани пяти различных цветов?

9. Сколькими способами могут расположиться в турнирной таблице 7 футбольных команд, если известно, что все команды набрали различное количество очков?

10. Сколькими способами можно составить команду из 4 человек, если имеется 7 бегунов?

11. Сколькими способами можно разложить 12 различных предметов по четырем различным ящикам так, чтобы в каждом ящике оказалось по три предмета?

12. Сколькими способами можно разложить 6 одинаковых шаров по четырем различным ящикам?

13. Запишите разложение бинома .

14. Докажите свойство симметрии биномиальных коэффициентов, сравнив формулы для и.

15. Найдите максимальный числовой коэффициент в разложении бинома .

16. Пользуясь формулой бинома Ньютона, вычислите с точностью до.

2.2. Группы подстановок

2.2.1. Понятие группы

Теория групп начала оформляться в качестве самостоятельного раздела математики в конце VIII века. Она дала мощные средства для исследования алгебраических уравнений, геометрических преобразований, а также для решения ряда задач топологии и теории чисел. Специалисты, занимающиеся обработкой информации, используют методы теории групп при кодировании и декодировании информации.

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

Для этого сначала определим понятие бинарной алгебраической операции.

Бинарная операцияна множестве – это соответствие, при котором каждой упорядоченной паре элементов данного множества отвечает однозначно определенный элемент того же множества. Так, действие сложения есть бинарная операция на множестве целых чисел; в самом деле, еслиrи s– любые два целых числа, тотоже является целым числом.

Определение 1. Непустое множество G с заданной на нем бинарной алгебраической операцией  называется группой, если:

1) операция  ассоциативна;

2) существует единичный элемент такой, что для каждоговыполняется условие:;

3) для каждого существует обратный элементтакой, что.

Эти три условия, необходимые для того, чтобы множество G с заданной на нем операцией  являлось группой, называются аксиомами группы.

Пример 1. Рассмотрим в качестве множества G множество всех целых чисел Z,а в качестве бинарной операции – сложение.

Проверим для пары (Z, +) аксиомы группы.

1) Ассоциативность. Сложение чисел ассоциативно: для любых Z, ;

2) Единичный элемент: нуль является единичным элементом для рассматриваемого множества относительно операции сложения, так как для каждого Z выполняется условие: ;

3) Обратный элемент: для каждого Z существует элемент –x, такой, что.

Итак, проверка показывает, что (Z, +) – группа.

Пример 2. Рассмотрим то же множество Z, но теперь с операцией умножения, т.е. рассмотрим пару (Z, ·). Проверим аксиомы группы.

1) Ассоциативность. Умножение чисел ассоциативно: для любых Z, ;

2) Единичный элемент: число 1 является единичным элементом рассматриваемого множества относительно операции умножения, т.е. для каждого Z выполняется условие: ;

3) Обратный элемент. Так как аксиома должна выполняться для любого элемента множества Z, то попытаемся найти обратный элемент для числа 2, т.е. нужно найти Z, такой что или. Такого целого числа не существует, таким образом, множество целых чисел, с заданной на нем операцией умножения, не является группой.

Определение 2. Множество называетсяподгруппой группы G, если оно замкнуто относительно операции , , и для каждогообратный элемент.