Решение комбинаторных задач
Задачу можно назвать комбинаторной, если ее решением является перебор элементов некоторого конечного множества.
Особая примета комбинаторных задач – вопрос, который можно сформулировать таким образом, что он начинался бы словами:
• Сколькими способами…?
• Сколько вариантов…?
Для того, чтобы решить задачу по комбинаторике, необходимо сначала понять её смысл, то есть, представить мысленно процесс или действие, описанное в задаче.
Нужно чётко определить тип соединений в задаче, а для этого надо, составив несколько различных комбинаций, проверить повторяются ли элементы, меняется ли их состав, важен ли порядок элементов.
КОМБИНАТОРИКА
Термин «комбинаторика » происходит от латинского слова «combina», что в переводе на русский означает – «сочетать», «соединять».
Комбинаторика
раздел математики, посвящённый решению задач выбора и расположения элементов в соответствии с данными условиями.
Комбинаторика
математический раздел, изучающий вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов.
Комбинаторика
раздел математики, который изучает множества (перестановки, размещения, сочетания и перечисление элементов) и отношения на них.
Комбинаторика
занимается различного рода соединениями, которые можно образовать из элементов некоторого конечного множества.
Комбинаторика
Важный раздел математики, знание которого необходимо представителям самых разных специальностей. С комбинаторными задачами приходится иметь дело физикам, химикам, биологам, лингвистам, криптографам и другим специалистам.
Комбинаторные методы лежат в основе решения многих задач теории вероятностей и ее приложений.
|
ПРАВИЛО СУММЫ
Если некоторый объект A можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор «либо А, либо В» можно осуществить (m+n) способами.
При использовании правила суммы надо следить, чтобы ни один из способов выбора объекта А не совпадал с каким-либо способом выбора объекта В.
Если такие совпадения есть, правило суммы утрачивает силу, и мы получаем лишь (m + n - k) способов выбора, где k—число совпадений.
ПРАВИЛО ПРОИЗВЕДЕНИЯ
Если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары (А,В) в указанном порядке можно осуществить mn способами.
При этом число способов выбора второго элемента не зависит от того, как именно выбран первый элемент.
Примеры:
Но бывает, что множества X и Y пересекаются, тогда пользуются другой формулой.Пример. Из 100 туристов, отправляющихся в заграничное путешествие, немецким языком владеют 30 человек, английским - 28, французским - 42. Английским и немецким одновременно владеют 8 человек, английским и французским - 10, немецким и французским - 5, всеми тремя языками - 3. Сколько туристов не владеют ни одним языком? Решение: Выразим условие этой задачи графически. Обозначим кругом тех, кто знает английский, другим кругом - тех, кто знает французский, и третьим кругом - тех, кто знают немецкий. Всеми тремя языками владеют три туриста, значит, в общей части кругов вписываем число 3. Английским и французским языком владеют 10 человек, а 3 из них владеют еще и немецким. Следовательно, только английским и французским владеют 10-3=7 человек. Аналогично получаем, что только английским и немецким владеют 8-3=5 человек, а немецким и французским 5-3=2 туриста. Вносим эти данные в соответствующие части. Определим теперь, сколько человек владеют только одним из перечисленных языков. Немецкий знают 30 человек, но 5+3+2=10 из них владеют и другими языками, следовательно, только немецкий знают 20 человек. Аналогично получаем, что одним английским владеют 13 человек, а одним французским - 30 человек. По условию задачи всего 100 туристов. 20+13+30+5+7+2+3=80 туристов знают хотя бы один язык, следовательно, 20 человек не владеют ни одним из данных языков.Ответ. 20 Домашняя работа. 1)Ученик должен выполнить практическую работу по математике. Ему предложили на выбор 17 тем по алгебре и 13 тем по геометрии. Сколькими способами он может выбрать одну тему для практической работы? 2)Имеется 5 билетов денежно-вещевой лотереи, 6 билетов спортлото и 10 билетов автомотолотереи. Сколькими способами можно выбрать один билет из спортлото или автомотолотереи? 3)Переплетчик должен переплести 12 различных книг в красный, зеленый и коричневые переплеты. Сколькими способами он может это сделать? 4)Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево? 5)20 человек знают английский и 10 - немецкий, из них 5 знают и английский, и немецкий. Сколько Человек всего?
Комбинаторные соединения — это такие комбинации из каких-либо элементов.
Типы соединений:
· Перестановки
· Размещения
· Сочетания
Существуют две схемы выбора элементов:
· Без повторений
· С повторениями
В комбинаторных соединениях может играть существенную роль или порядок элементов или их состав, или и порядок и состав.
В зависимости от этого комбинаторные соединения имеют определённое название.
ФАКТОРИАЛ ЧИСЛА
Факториал числа — это произведение всех натуральных чисел до этого числа включительно.
Обозначается с восклицательным знаком в конце.
n! = 1 · 2 · 3 · 4 · … · (n-2) · (n-1) · n
Случай 0! определен и имеет значение 0!=1, соответствующее комбинаторной интерпретации комбинации нуля объектов, другими словами, есть единственная комбинация нуля элементов, а именно: пустое множество.
Ниже приведены значения факториалов от 0 до 10.
0! = 1
1! = 1
2! = 1 · 2 = 2
3! = 1 · 2 · 3 = 6
4! = 1 · 2 · 3 · 4 = 24
5! = 1 · 2 · 3 · 4 · 5 = 120
6! = 1 · 2 · 3 · 4 · 5 · 6 = 720
7! = 1 · 2 · 3 · 4 · 5 · 6 · 7 = 5040
8! = 1 · 2 · 3 · 4 · 5 · 6 · 7 · 8 = 40320
9! = 1 · 2 · 3 · 4 · 5 · 6 · 7 · 8 · 9 = 362880
10! = 1 · 2 · 3 · 4 · 5 · 6 · 7 · 8 · 9 · 10 = 3628800
ПЕРЕСТАНОВКИ
Перестановки без повторений — комбинаторные соединения, которые могут отличаться друг от друга лишь порядком входящих в них элементов.
формула для нахождения количества перестановок без повторений:
Перестановки с повторениями — комбинаторные соединения, в которых среди образующих элементов имеются одинаковые.В таких соединяниях участвуют несколько типов объектов, причём имеется некоторое количество объектов каждого типа. Поэтому в выборках встречаются одинаковые.
формула для нахождения количества перестановок с повторениями:
Пример. Предположим, что есть книжная полка.
На неё хотят положить 10 книг.
Положить их туда можно различными способами (например, сначала первая книга, потом вторая... или сначала десятая, потом третья...)
Так вот, каждый такой способ и будет перестановкой.
РАЗМЕЩЕНИЯ
Размещения без повторений — комбинаторные соединения, составленные из n элементов по m. При этом два соединения считаются различными, если они либо отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке.
формула для нахождения количества размещений без повторений:
Размещения с повторениями — комбинаторные соединения, составленные из n элементов по m. При этом каждый из n элементов может содержаться сколько угодно раз или вообще отсутствовать.
формула для нахождения количества размещений с повторениями: 
Предположим, что в учебном классе 20 учеников.
Они выполняют контрольную работу.
После проверки, оказывается, что один выполнил лучше всех, а другой хуже всех.
Такая пара учеников(один лучший, другой худший) будет являться размещением из 20-ти учеников по 2.
СОЧЕТАНИЯ
Сочетания без повторений — комбинаторные соединения из n элементов по m, составленные из этих элементов и отличающиеся друг от друга только составом.
формула для нахождения количества сочетаний без повторений:
Сочетания с повторениями — комбинаторные соединения из n элементов по m, составленные из этих элементов без учета порядка с возможностью многократного повторения предметов.
формула для нахождения количества сочетаний с повторениями:
Пример. Предположим, что в коробке лежат 10 разноцветных шаров.
Вынимаются 4 шара.
Эти 4 шара будут являться сочетанием из 10 шаров по 4.