Автор работы: Пользователь скрыл имя, 15 Января 2014 в 23:05, шпаргалка
Работа содержит ответы на вопросы для экзамена по "Комбинаторике".
1. Элементы комбинаторики
Комбинаторика - раздел математики, в котором изучаются различные соединения (комбинации) элементов конечных множеств.
Многие комбинаторные задачи могут быть решены с помощью двух правил - правила умножения и правила сложения.
Теорема 1.1 Правило умножения: если из некоторого конечного множества первый объект (элемент а) можно выбрать n1 способами, а второй объект (элемент b) - n2 способами, то оба объекта (а и b) в указанном порядке можно выбрать n1 ∙ n2 способами.
Этот случай распространяется на случай трех и более объектов.
Теорема 1.2 Правило сложения: если некоторый объект а можно выбрать n1 способами, а объект b можно выбрать (независимо от выбора объекта а) n2 способами, то любой из объектов (а или b) можно выбрать n1 + n2 способами.
Это правило распространяется на любое конечное число объектов.
Существуют две схемы выбора m элементов из заданного множества: без возвращения, когда выбранные элементы не возвращаются в исходное множество, и с возвращением, когда выбор осуществляется поэлементно с обязательным возвращением отобранного элемента на каждом шаге.
Пусть дано множество, состоящее из n различных элементов.
Определение. Перестановкой из п элементов называются множества, состоящие из n элементов и отличающиеся порядком их расположения
Число перестановок из n элементов обозначается символом
Пример. Расставить на полке 10 книг можно различными способами.
Определение. Размещением из п элементов по m (0 ≤ m ≤ n) называются комбинации данного множества, состоящие из m различных элементов и отличающиеся между собой порядком их расположения.
Число размещений из n элементов по m обозначается символом
Пример. Из десяти различных книг произвольным образом берутся и ставятся на полку одна за другой 3 книги. Имеется вариантов расстановок.
Определение. Сочетанием из п элементов по m (0 ≤ m ≤ n) называются комбинации по m элементов, которые отличаются между собой только составом (порядок не имеет значения).
Число сочетаний из n элементов по m обозначается символом
Пример. Из десяти чисел четыре можно выбрать способами.
1.2 Схема выбора с возвращением.
Определение. Размещением из n элементов по m с повторением (0 ≤ m ≤ n) называется любое упорядоченное подмножество данного множества, содержащее m элементов.
Число всех размещений с повторениями из n элементов по m обозначается символом
Пример. Из цифр 1, 2, 3, 4 можно составить трехзначных числа.
Определение. Сочетанием из n элементов по m с повторением (0 ≤ m ≤ n) называется любое подмножество данного множества, содержащее m элементов.
Число сочетаний из n элементов по m с повторением обозначается символом
Пример. Из трех видов конфет, имеющихся в продаже, покупатель может взять пять конфет способами.
Определение. Перестановкой с повторением из n элементов называется перестановка, в которой участвуют n1 элементов 1-го типа, n2 элементов 2-го типа, ..., nm элементов m-го типа, где n1+n2+…+nm=n
Число перестановок с повторениями (иногда говорят о числе разбиений множества) из n элементов обозначается символом
Пример. В студенческой группе, состоящей из 25 человек, при выборе старосты за выдвинутую кандидатуру проголосовали 12 человек, против -10, воздержались 3. Такое голосование могло быть проведено способами.
1. Элементы комбинаторики
Комбинаторика - раздел математики, в котором изучаются различные соединения (комбинации) элементов конечных множеств.
Многие комбинаторные задачи могут быть решены с помощью двух правил - правила умножения и правила сложения.
Теорема 1.1 Правило умножения: если из некоторого конечного множества первый объект (элемент а) можно выбрать n1 способами, а второй объект (элемент b) - n2 способами, то оба объекта (а и b) в указанном порядке можно выбрать n1 ∙ n2 способами.
Этот случай распространяется на случай трех и более объектов.
Теорема 1.2 Правило сложения: если некоторый объект а можно выбрать n1 способами, а объект b можно выбрать (независимо от выбора объекта а) n2 способами, то любой из объектов (а или b) можно выбрать n1 + n2 способами.
Это правило распространяется на любое конечное число объектов.
Существуют две схемы выбора m элементов из заданного множества: без возвращения, когда выбранные элементы не возвращаются в исходное множество, и с возвращением, когда выбор осуществляется поэлементно с обязательным возвращением отобранного элемента на каждом шаге.
Пусть дано множество, состоящее из n различных элементов.
Определение. Перестановкой из п элементов называются множества, состоящие из n элементов и отличающиеся порядком их расположения
Число перестановок из n элементов обозначается символом
Пример. Расставить на полке 10 книг можно различными способами.
Определение. Размещением из п элементов по m (0 ≤ m ≤ n) называются комбинации данного множества, состоящие из m различных элементов и отличающиеся между собой порядком их расположения.
Число размещений из n элементов по m обозначается символом
Пример. Из десяти различных книг произвольным образом берутся и ставятся на полку одна за другой 3 книги. Имеется вариантов расстановок.
Определение. Сочетанием из п элементов по m (0 ≤ m ≤ n) называются комбинации по m элементов, которые отличаются между собой только составом (порядок не имеет значения).
Число сочетаний из n элементов по m обозначается символом
Пример. Из десяти чисел четыре можно выбрать способами.
1.2 Схема выбора с возвращением.
Определение. Размещением из n элементов по m с повторением (0 ≤ m ≤ n) называется любое упорядоченное подмножество данного множества, содержащее m элементов.
Число всех размещений с повторениями из n элементов по m обозначается символом
Пример. Из цифр 1, 2, 3, 4 можно составить трехзначных числа.
Определение. Сочетанием из n элементов по m с повторением (0 ≤ m ≤ n) называется любое подмножество данного множества, содержащее m элементов.
Число сочетаний из n элементов по m с повторением обозначается символом
Пример. Из трех видов конфет, имеющихся в продаже, покупатель может взять пять конфет способами.
Определение. Перестановкой с повторением из n элементов называется перестановка, в которой участвуют n1 элементов 1-го типа, n2 элементов 2-го типа, ..., nm элементов m-го типа, где n1+n2+…+nm=n
Число перестановок с повторениями (иногда говорят о числе разбиений множества) из n элементов обозначается символом
Пример. В студенческой группе, состоящей из 25 человек, при выборе старосты за выдвинутую кандидатуру проголосовали 12 человек, против -10, воздержались 3. Такое голосование могло быть проведено способами.