Студопедия

КАТЕГОРИИ:


Архитектура-(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)

Основные формулы комбинаторики

Комбинаторика – раздел математики, изучающий вопросы о том, сколько комбинаций определённого типа можно составить из данных предметов (элементов).

Правило суммы: пусть имеется n попарно непересекающихся множеств A 1, A 2, …, An, содержащих m 1, m 2, …, mn элементов соответственно. Число способов, которыми можно выбрать один элемент из всех этих множеств, равно

m 1 + m 2 + … + mn.

Кортеж – конечная последовательность (допускающая повторения) элементов какого-нибудь множества.

Правило произведения: пусть имеется n множеств A 1, A 2, …, An содержащих m 1, m 2, …, mn элементов соответственно. Число способов, которыми можно выбрать по одному элементу из каждого множества, т. е. построить кортеж (а 1, а 2,..., аn), где аi Î Аi (i = 1, 2, …, n), равно

m 1 ּ m 2 ּ … ּ mn.

Определение 1. Размещениями из n различных элементов по m элементов () называют комбинации, составленные из данных n элементов по m элементов, которые отличаются либо самими элементами, либо порядком элементов.

Пример. Из трёх элементов a, b, c можно составить следующие размещения по два элемента: ab, ac, bc, ba, ca, cb.

Число различных размещений без повторений из n элементов по m элементов определяется по формуле:

.

Размещения с повторениями (n различных элементов, элементы могут повторяться):

.

Пример. Возьмем буквы Б, А, Р. Какие размещения из этих букв, взятых по две, можно получить? Сколько таких наборов получиться, если: 1) буквы в наборе не повторяются; 2) буквы могут повторяться?

1) Получатся следующие наборы: БА, БР, АР, АБ, РБ, РА.

.

2) Получатся наборы: ББ, БА, БР, АА, АБ, АР, РР, РБ, РА.

Определение 2. Перестановками из n различных элементов называют размещения из этих n элементов по n.

Перестановки можно считать частным случаем размещений при m=n. Тогда число всех перестановок без повторений из n элементов вычисляется по формуле:

Перестановки с повторениями (k различных элементов, где элементы могут повторяться раз и , где n – общее количество элементов):

.

Пример. Возьмем буквы Б, А, Р. Какие перестановки из этих букв можно получить? Сколько таких наборов получится, если: 1) буквы в наборе не повторяются; 2) буква А повторяется два раза?

1) Получатся наборы: БАР, БРА, АРБ, АБР, РАБ, РБА.

2) Получатся наборы: БАРА, БРАА, БААР, ААРБ, ААБР, АБАР, АРАБ, АРБА, АБРА, РАБА, РААБ, РБАА.

Определение 3. Сочетаниями из n различных элементов по m элементов называются комбинации, составленные из данных n элементов по m элементов, которые отличаются хотя бы одним элементом.

Отметим разницу между сочетаниями и размещениями: в первых не учитывается порядок элементов.

Число сочетаний без повторений из n различных элементов по m элементов вычисляется по формуле:

.

Пример. В лабораторной клетке содержат трёх белых и трёх коричневых мышей. Найдите число способов выбора двух мышей, если они могут быть любого цвета.

m=2, n =6, тогда.

Сочетания с повторениями (n элементов, взятых по m, где элементы могут повторяться):

.

Пример. Возьмем плоды: банан (Б), ананас (А) и репа(Р).Какие сочетания из этих плодов, взятых по два, можно получить? Сколько таких наборов получится, если: 1) плоды в наборе не повторяются; 2) можно брать по два одинаковых плода?

1) Получатся наборы: БА («банан, ананас» и «ананас, банан» – один и тот же набор), АР и РБ.

.

2) Получатся наборы: ББ, БА, БР, АА, АР, РР.

.

<== предыдущая лекция | следующая лекция ==>
Разность и дополнение множеств. | Лекция 2. 1. Найдите полученные промежутки:
Поделиться с друзьями:


Дата добавления: 2014-01-07; Просмотров: 2021; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.009 сек.