Мои Конспекты
Главная | Обратная связь


Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

Перестановки, инверсии, транспозиции.



Определение 1.Пусть - первых попарно различных натуральных чисел, т.е. N, , если . Упорядоченный набор первых натуральных чисел будем называть перестановкой из элементов.

Перестановку будем называть основной. Множество всех перестановок из элементов будем обозначать так: .

 

Пример 1. - перестановка из четырёх элементов. - перестановка из семи элементов.

Теорема 1. Число различных перестановок из элементов равно .

Доказательство проведём методом математической индукции по числу .

База математической индукции.Пусть .Очевидно, существует единственная перестановка из одного элемента, т.е. для теорема верна.

Индукционный переход. Докажем, что утверждение теоремы верно для перестановок из - го элемента, если оно верно для перестановок из элементов.

Множество всех перестановок из - го элемента разобьём на групп в зависимости от расположения в перестановке числа .

В 1 –ю группу включим все перестановки, в которых число стоит на первом месте, т.е. перестановки вида , в которых .

Во 2 –ю группу включим все перестановки, в которых число стоит на втором месте, т.е. перестановки вида , в которых и т.д.

В –ю группу включим все перестановки, в которых число стоит на последнем месте, т.е. перестановки вида , в которых .

Подсчитаем, сколько перестановок содержится в каждой такой группе. Если мы из каждой перестановки, входящей в - ю группу, вычеркнем число , то получившиеся перестановки будут образовывать всевозможные перестановки из элементов, а их число по индукционному предположению равно . Таким образом, получаем: число различных перестановок из элементов равно .

 




Поиск по сайту:







©2015-2020 mykonspekts.ru Все права принадлежат авторам размещенных материалов.