Г. Кызыла рт XII научно-практическая конференция учащихся Комбинаторика и комбинаторные задачи
Глава II Решение комбинаторных задач
Download 154 Kb.
|
kombinatorika
|
Глава II
Решение комбинаторных задач 1. Основные понятия и правила комбинаторики Термин «комбинаторика» происходит от латинского слова «combina», что в переводе на русский означает – «сочетать», «соединять». Комбинаторика - раздел математики, изучающий вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Комбинаторные методы лежат в основе решения многих задач теории вероятностей и ее приложений. Задачу можно назвать комбинаторной, если ее решением является перебор элементов некоторого конечного множества. Особая примета комбинаторных задач – вопрос, который можно сформулировать таким образом, что он начинался бы словами: • Сколькими способами…? • Сколько вариантов…? Для того, чтобы решить задачу по комбинаторике, необходимо сначала понять её смысл, то есть, представить мысленно процесс или действие, описанное в задаче. Нужно чётко определить тип соединений в задаче, а для этого надо, составив несколько различных комбинаций, проверить повторяются ли элементы, меняется ли их состав, важен ли порядок элементов. Если же комбинаторная задача содержит ряд ограничений, налагающихся на соединения, то нужно понять, как влияют или не влияют эти ограничения на соединения. В том случае, если трудно сразу определить какие-либо важные моменты задачи, то не плохо было бы попытаться разобраться в более лёгкой задаче, например в той, в которой не учитываются ограничения, если они есть в исходной задаче, или же в задаче, в которой рассматривается меньшее количество элементов, тогда проще будет понять принцип образования выборок. Когда комбинаторная задача состоит из различных комбинаций элементарных задач, то нужно просто разбить задачу на подзадачи. Комбинаторные задачи бывают самых разных видов. Однако, большинство задач решается с помощью двух основных правил — правила суммы и правила произведения. Правило суммы. Если некоторый объект A можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор «либо А, либо В» можно осуществить (m+n) способами. Например: Имеется 8 шаров: в первый ящик положили 5 шаров, а во второй 3 шара. Сколькими способами можно вытащить 1 шар? Решение: из первого ящика шар можно вытащить 5-ю способами, а из второго 3-мя. Значит, всего 5+3=8 способов. При использовании правила суммы надо следить, чтобы ни один из способов выбора объекта А не совпадал с каким-либо способом выбора объекта В. Если такие совпадения есть, правило суммы утрачивает силу, и мы получаем лишь (m + n - k) способов выбора, где k—число совпадений. Правило произведения. Если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары (А,В) в указанном порядке можно осуществить mn способами. При этом число способов выбора второго элемента не зависит от того, как именно выбран первый элемент. Например: В первом ящике 5 зелёных шаров, а во втором 3 красных шара. Сколькими способами можно вытащить 1 зелёный и 1 красный шар? Решение: зелёный шар можно выбрать 5-ю способами, а красный – 3-мя. Значит, 1 зелёный и 1 красный шар можно выбрать 3х5 = 15 способами. Так же комбинаторные задачи можно решить методом перебора. Например: Сколько двузначных чисел можно составить, используя цифры 1, 4 и 7? Решение. Для того чтобы не пропустить и не повторить ни одно из чисел, надо выписывать их в порядке возрастания. Сначала вписываем числа, начинающиеся с цифры 1, затем с цифры 4 и, наконец, с цифры 7. Получаем следующий расклад.
Таким образом, из трех данных цифр можно составить всего 9 различных двузначных чисел. Существует единый подход к решению самых разных комбинаторных задач с помощью составления специальных схем. Внешне такая схема напоминает дерево, отсюда название – дерево возможных вариантов. Решение комбинаторных задач методом составления дерева вариантов с применением правила умножения. Так, например, “дерево возможностей” помогает решать разнообразные задачи, касающиеся перебора вариантов происходящих событий. Каждый путь по этому “дереву” соответствует одному из способов выбора, число способов выбора равно числу точек в нижнем ряду “дерева”. Правило умножения заключается в том, что для того, чтобы найти число всех возможных исходов независимого проведения двух испытаний А и В, следует перемножить число всех исходов испытания А и число всех исходов испытания В. Например: Сколько двузначных чисел можно составить, используя цифры 1, 5 и 8? * П ервая цифра 1 5 8 Вторая цифра 1 5 8 1 5 8 1 5 8 Число 11 15 18 51 55 58 81 85 88 Э та схема действительно похожа на дерево, правда, «вверх ногами» и без ствола. Знак «*» изображает корень дерева, ветви дерева – различные варианты решения. Чтобы получить двузначное число, надо сначала выбрать первую его цифру, а для нее есть три варианта: 1, 5 или 8. Поэтому из точки * проведены три отрезка и на концах поставлены цифры 1, 5 и 8. Теперь надо выбрать вторую цифру, а для этого также есть три варианта: 1, 5 или 8. Поэтому от каждой первой цифры проведено по три отрезка, на концах которых снова записано 1, 5 или 8. Итак, получено всего 9 различных двузначных чисел. Других двузначных чисел из этих трех цифр составить невозможно. В задачах по комбинаторике часто применяется такое понятие как факториал (в переводе с английского “factor” - “множитель”). Факториал числа — это произведение всех натуральных чисел до этого числа включительно. Обозначается с восклицательным знаком в конце. n! = 1 · 2 · 3 · 4 · … · (n-2) · (n-1) · n Случай 0! определен и имеет значение 0!=1, соответствующее комбинаторной интерпретации комбинации нуля объектов, другими словами, есть единственная комбинация нуля элементов, а именно: пустое множество. Ниже приведены значения факториалов от 0 до 10. 0! = 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 Свойство факториала: (n + 1)! = (n + 1) · n! Например: (5 + 1)! = (5 + 1) · 5! Действительно 6! = (1 · 2 · 3 · 4 · 5) · 6 = 720 А значение (1 · 2 · 3 · 4 · 5) = 5! = 120 В комбинаторике решаются задачи, связанные с рассмотрением множеств и составлением различных комбинаций из элементов этих множеств. В зависимости от правил составления можно выделить три типа комбинаций: перестановки, размещения, сочетания. 2. Примеры решения задач 1. В школьной столовой на первое можно заказать борщ, солянку, грибной суп, на второе - мясо с макаронами, рыбу с картошкой, курицу с рисом, а на третье - чай и компот. Сколько различных обедов можно составить из указанных блюд? 1 способ. Перечислим возможные варианты
18 вариантов. 2 способ. Дерево возможностей. 3 способ. Используя правило умножения, получаем: 3х3х2=18 2. Свете на день рождения подарили 4 плюшевых игрушки, 2 мяча и 5 кукол. Мама положила все игрушки в большую коробку. Сколькими способами Света сможет достать из коробки 1 плюшевую игрушку, 1 мяч и 1 куклу? 1 способ. Обозначим мячи - М1, М2, игрушки- И1,И2,И3, И4, куклы- К1,К2, К3, К4, К5. Перечислим возможные варианты: М1-И1-К1, М1-И1-К2, М1-И1-К3, М1-И1-К4, М1-И1-К5, М1-И2-К1, М1-И2-К2, М1-И2-К3, М1-И2-К4, М1-И2-К5, М1-И3-К1, М1-И3-К2, М1-И3-К3, М1-И3-К4, М1-И3-К5, М1-И4-К1, М1-И4-К2, М1-И4-К3, М1-И4-К4, М1-И4-К5 М2-И1-К1, М2-И1-К2, М2-И1-К3, М2-И1-К4, М2-И1-К5, М2-И2-К1, М2-И2-К2, М2-И2-К3, М2-И2-К4, М2-И2-К5, М2-И3-К1, М2-И3-К2, М2-И3-К3, М2-И3-К4, М2-И3-К5, М2-И4-К1, М2-И4-К2, М2-И4-К3, М2-И4-К4, М2-И4-К5 Ответ: 40 вариантов. 2 способ. Используя правило умножения, получаем: 2х4х5= 40 3. Сколько четных двузначных чисел можно составить из цифр 0, 2, 3, 6, 7, 9? 1 способ. Перечислим возможные варианты.
2 способ. Дерево возможностей. 3 способ. Используя правило умножения, получаем: 5х3=15 . 4. Саша, Петя, Денис, Оля, Настя часто ходят в кафе. Каждый раз, обедая там, они рассаживаются по-разному. Сколько дней друзья смогут это сделать без повторения? 1 способ. Пронумеруем стулья, на которых должен сесть каждый, и будем считать, что они рассаживаются поочередно: №1 - Саша - есть возможность выбрать из 5 вариантов (стульев) №2 - Петя - 4 варианта №3- Денис - 3 варианта №4- Оля - 2 варианта №5 - Настя- 1 вариант Используя правило умножения, получаем: 5х4х3х2х1=120 2 способ. Решаем, используя понятие факториала: 5!=120 6. Из учащихся пяти 11 классов нужно выбрать двоих дежурных. Сколько пар дежурных можно составить (ученики в паре не должны быть из одного класса)? 1 способ. Перечислим возможные варианты состава пары: 11А-11Б, 11А-11В, 11А-11Г, 11А-11Д, 11Б-11В, 11Б-11Г, 11Б-11Д, 11В-11Г, 11В-11Д, 11Г-11Д Download 154 Kb. Do'stlaringiz bilan baham: 
|