КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Лекция 7. Элементы комбинаторики
Комбинаторика – это раздел математики, изучающий количество комбинаций, которые можно составить из заданного конечного множества попарно различных элементов произвольной природы. Одно из важных правил комбинаторики – правило умножения: если объект А может быть выбран из множества M n h способами и при каждом выборе объекта А другой объект В может быть выбран k способами, то объект , состоящий из двух объектов А и В может быть выбран hk способами.
Конечные подмножества элементов множества M n называются соединениями. Если в совокупности соединений подмножества образованы только попарно различными элементами множества M n, то такие соединения называются соединениями без повторений. Если в совокупности соединений входят подмножества не только с попарно различными элементами множества M n, но и с одинаковыми, то такие соединения называются соединениями с повторениями. Различают три основных типа соединений: размещения, перестановки, сочетания. Определение 7.1. Размещением из n элементов по m элементов без повторений называется упорядоченное подмножество попарно различных m элементов множества M n (). Определение 7.2. Перестановкой из n элементов без повторений называется упорядоченное множество всех n элементов множества M n, то есть перестановка без повторений – это размещение без повторений из n по n элементов. Определение 7.3. Сочетанием из n элементов по m элементов без повторений называется подмножество из m попарно различных элементов множества M n без учёта порядка их следования (). Для размещения или сочетания с повторениями требуется лишь условие, что и, следовательно, m может быть любым натуральным числом, независимым от числа n элементов множества M n.
В перестановке с повторениями присутствуют все элементы множества M n, причём указывается, сколько раз повторяются элементы . Число элементов в такой перестановке может быть любым натуральным числом, б о льшим или равным n. Обозначим символами , , число всех размещений, сочетаний без повторений из n элементов по m элементов и число всех перестановок без повторений из n элементов (). Символы для обозначения числа всех соединений определённого типа берутся из начальных букв соответствующих французских слов: arrangement – размещение, combination – комбинация, сочетание, permutation – перестановка. Символами , , обозначим число всех размещений, сочетаний, перестановок с повторениями (m, mi – любые натуральные числа). Число mi указывает, что элемент ai повторяется в перестановке mi раз, причем . Произведение n первых натуральных чисел обозначается символом n! и называется n -факториалом: . ☼ По определению 0!=1 и =1. ☼
♦ Теорема 7.1. Число размещений без повторений из n элементов по m элементов вычисляется по формуле , (7.1) число размещений из n элементов по m элементов с повторениями . (7.2) Доказательство. Докажем методом математической индукции формулы (7.1) и (7.2). 1) Для m =1 они справедливы, так как выбор по одному элементу из множества M n можно осуществить только n способами, а по формулам (7.1) и (7.2) , . 2) Пусть эти формулы справедливы для произвольного фиксированного натурального числа k, то есть , . По правилу умножения , , так как в случае подмножества с попарно различными элементами множества M n после выбора k элементов из M n в нём останется n – k элементов, из которых по одному элементу можно выбрать n – k способами. А в случае размещения с повторениями (k +1)‑м элементом может быть любой из n элементов множества M n. Учитывая, что , убеждаемся в справедливости формул (7.1) и (7.2). ■
Следствие 1. Так как , то . Таким образом, получается формула числа перестановок:
(7.3) Формула для перестановок с повторениями такова: . (7.3а) Справедливость этой формулы установим следующими рассуждениями: если бы в перестановке все элементов были попарно различными, то таких перестановок было бы . Но, меняя между собой одинаковый элемент ai любыми mi! способами, мы не изменяем самой перестановки. Поэтому в знаменатель надо внести произведение факториалов .
Следствие 2. По правилу умножения . Следовательно, , то есть справедлива формула . (7.4)
♦ Теорема 7.2. Число сочетаний из n элементов по m элементов с повторениями вычисляется по формуле . (7.5) Доказательство. Докажем формулу (7.5) методом математической индукции. 1) Для m =1 она справедлива, так как , а выбор по одному элементу из множества M n можно осуществить только n способами. 2) Пусть формула (7.5) верна для произвольного фиксированного , то есть . Тогда, по правилу умножения, , т.к. вставить один элемент, взятый из M n, мы можем n + k способами, добавив к уже выбранным k элементам либо один из них, либо любой из M n. А в знаменателе число k +1 означает, что вставить этот дополнительный элемент, не изменяя сочетания, мы можем либо вначале, либо между первым и вторым и т.д., либо после последнего (то есть k +1 вариантов). Учитывая, что , убеждаемся, что формула (7.5) справедлива для m = k +1, а значит, она справедлива и для любого натурального числа m. ■
♦ Теорема 7.3. Справедливо правило симметрии . (7.6) Доказательство. . ■ ♦ Теорема 7.4. Справедлива формула (правило Паскаля) . (7.7) Доказательство. . ■
♦ Теорема 7.5. Число всех подмножеств из n элементов равно : . Доказательство. Докажем теорему методом математической индукции. 1) При n =1 имеем множество одного элемента , которое содержит два подмножества: пустое множество и само себя. 2) Пусть установлено, что множество из k элементов содержит ровно подмножеств. Рассмотрим множество из k +1 элементов. Любое его подмножество В получается одним из двух способов: а) берётся подмножество В множества , в) берётся подмножество и присоединяется элемент . Каждым из этих способов получаем подмножеств, а всего подмножеств множества А. ■
Рассмотрим несколько задач, решение которых осуществляется с использованием доказанных формул.
J Пример 7.1. Сколько пятизначных чисел можно составить из цифр 1, 3, 7?
Дата добавления: 2014-01-05; Просмотров: 1111; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |