Тема: элементы комбинаторики Разработала: Касьянова Л. В. Преподаватель математики ГУ НПО Технологический профессиональный лицей. г. Великий Новгород

ЦЕЛИ: Познакомиться с основными понятиями комбинаторики и методами решения комбинаторных задач.

СТРУКТУРА: Комбинаторика: содержание материала примеры Множества и операции над ними: содержание материала упражнения Основные законы комбинаторики: содержание материала упражнения Основные формулы комбинаторики: содержание материала упражнения Проверь себя

Комбинаторика – один из разделов математики, играющий важную роль при решении некоторых современных проблем теории вероятностей, кибернетики, математической логики, теории чисел. Знание комбинаторики необходимо представителям самых разных специальностей. С комбинаторными задачами приходится иметь дело физикам, химикам, биологам, лингвистам, специалистам по теории кодов. Здесь мы познакомимся с основными понятиями и методами комбинаторики. Для решения многих практических задач приходится выбирать из некоторой совокупности объектов элементы, обладающие тем или иным свойством, располагать эти элементы в определенном порядке и т.д. Поскольку в этих задачах идет речь о тех или иных комбинациях объектов, их называют комбинаторными задачами. Область математики, в которой изучаются комбинаторные задачи, называют комбинаторикой. оглавление примеры

Приведем примеры комбинаторных задач: 1. Узнать, сколькими способами можно из 7 мальчиков и 9 девочек выбрать команду для эстафеты, если в команду должны войти 4 мальчика и 4 девочки. 2. Сколькими способами могут быть распределены золотая, серебряная и бронзовая медами на чемпионате мира по футболу? оглавление

В жизни человеку часто приходится объединять предметы в группы и для каждой группы придумывать особые названия: стадо коров, караван верблюдов, совокупность точек и т.д. Вместо слов «стадо», «караван», «совокупность» в математике употребляют слово множество. Множество может быть составлено из каких угодно предметов, при этом каждый предмет, входящий в данное множество, называют элементом множества. Множество обозначают заглавными буквами латинского алфавита, а элемент, входящий в множество записывают в фигурных скобках. Например, запись А = { 3; 6; 9 } говорит, что множество А состоит из трех элементов: чисел 3, 6 и 9. Тот факт, что элемент x принадлежит множеству А, записывают так:, в противном случае пишут. оглавление

Множество может содержать любое количество элементов. Если множество содержит конечное число элементов, то оно называется конечным множеством. Если же число элементов множества бесконечно, то и множество называют бесконечным. Если множество не содержит ни одного элемента, то такое множество называется пустым и обозначается O. Если множества состоят из одних и тех же элементов, то такие множества называются равными. Например: {12; 13; 14; 15 } = {15; 14; 13;12 }. оглавление

Рассмотрим операции пересечения, объединения и вычитания множеств: Объединением множеств А и В называют множество, состоящее их элементов которые принадлежат хотя бы одному из множеств А, В. оглавление

Пересечением множеств А и В называют множество, состоящее из элементов, которые принадлежат как множеству А, так и множеству В. оглавление

Разностью множеств А и В, называют множество А \ В, состоящее из всех элементов множества А, которые не принадлежат множеству В. оглавление упражнения

Упражнения: Даны множества А = {1;2;3;4;5} и B = {3;4;5;6;7}. Найти: 1) 2) 3) Ответы: 1) 2) 3) оглавление

Часто приходится рассматривать упорядоченные множества, т.е. множества, в которых каждый элемент занимает свое, вполне определенное место. Упорядочить множество – это значит поставить, какой-либо элемент множества на первое место, какой-либо другой элемент – на второе место и т.д. Упорядоченное множество, иногда принято записывать в круглых скобках. Упорядочить множество можно различными способами. оглавление

Например: представьте себе две геометрические фигуры: квадрат и треугольник. Если говорить о порядке их расположения, то можно найти два способа: сначала квадрат, потом треугольник (рис.1) или сначала треугольник, а потом квадрат (рис. 2) Рис. 1 Рис. 2 оглавление

Точно также множество, состоящее их трех элементов a, b, c можно упорядочить шестью способами: (a b c); (b a c); (a c b); (b c a); (c a b); (c b a). Установленный в конечном множестве порядок расположения его элементов называется перестановкой. Число перестановок обозначается латинской буквой Р. Значит, - число перестановок из двух элементов равно 2, - число перестановок из трех элементов равняется 6. оглавление

Можно доказать, что число перестановок из четырех элементов равно 24,т.е. Аналогично и т.д. Тогда число перестановок из любого количества k элементов можно найти по формуле: Произведение натуральных чисел от 1 до данного натурального числа k называется факториалом числа k и обозначается k! Например: оглавление упражнения

Если каждый элемент множества А является в то же время и элементом множества В, то говорят, что А – часть или подмножество множества В. В этом случае пишут. Считают также, что пустое множество является подмножеством любого множества, т.е.. И Любое множество является подмножеством самого себя, т.е. оглавление

Каждое упорядоченное подмножество множества А называют размещением. Например: сколькими способами можно выбрать четырех человек на различные должности из девяти кандидатов на эти должности. Так как каждый выбор 4 человек из 9 имеющихся должен иметь определенный порядок распределения их на должности, то мы имеем задачу составления размещений из 9 по 4. Число размещений из 9 по 4 обозначается:. Очевидно, что первого человека можно выбрать 9 способами: каждый из 9 претендентов может занять первую должность. Второго человека выбирают из оставшихся 8. И чтобы выбрать этих двух человек понадобится способов. Третьего человека выбираем из 7 претендентов и последнего из 6. Значит, чтобы из 9 претендентов выбрать 4 нам понадобится способа, т.е. оглавление

Можно заметить, что тот же результат буден получен, если размещения связать с перестановками, т.е. Рассуждая аналогичным образом можно доказать, что число размещений из m элементов по n (очевидно, что ) вычисляется по формуле: оглавление упражнения

Размещения – это упорядоченные подмножества данного множества, которые отличаются друг от друга не только выбором элементов, но и порядком их расположения. Произвольные неупорядоченные подмножества данного множества называются сочетаниями. Различные сочетания отличаются друг от друга только составом (выбором) элементов. Количество сочетаний (или число сочетаний) обозначается латинской буквой С и соответствующими индексами. Число сочетаний из m элементов по n вычисляется по формуле: или оглавление

Например: в классе 10 юношей-допризывников. Сколькими способами они могут выбрать четверых для участия в слете ДОСААФ? Для ответа на этот вопрос нам надо найти число сочетаний из 10 элементов по 4, т.к. порядок в котором будут избраны 4 делегата на слет, безразличен: оглавление упражнения

Упражнения: 1) Вычислите: 2) Вычислите: 3) Сколькими способами можно рассадить 8 человек на восьми свободных стульях? решение оглавление теория

Решение: 1) = «

Решение: 2) = = «

Решение: 3)Чтобы вычислить сколько способов существует для того чтобы рассадить 8 человек на восьми свободных стульях надо найти число перестановок : «

Упражнения: 1) Вычислите: 2)Вычислите: 3) Решите уравнение: 4) Сколькими способами могут быть присуждены золотая, серебряная и бронзовая медами трем участникам из 11? решение оглавление теория решение

Решение: 1) = = «

Решение: 2) = «

Решение: 3) Решить уравнение, значит найти значение переменной х. Т.е., тогда ;, учитывая, х - натуральное число, получаем х = 1 Ответ: х = 1 «

Решение: 4) Каждый выбор трех медалистов из 11 участников отличается друг от друга составом и порядком расположения участников, то надо вычислить число размещений из 11 по 3: = «

Упражнения: 1) Вычислите: 2) Вычислите: 3) Сколько прямых можно провести через 7 точек, из которых никакие три не лежат на одной прямой? решение оглавление теория

Решение: 1) = = «

Решение: 2) = «

Решение: 3) Каждые две точки определяют одну прямую, и при этом не играет роли в каком порядке они взяты. Поэтому число прямых равно числу сочетаний из 7 по 2, т.е. = «

Проверь себя! 1). Сколькими способами можно разместить 6 человек на одной скамейке? 2). Учащиеся изучают 10 различных предметов. Сколькими способами можно составить расписание уроков на один день, чтобы при этом было 6 различных предметов? 3). Сколькими способами можно выбрать делегацию в составе 5 человек из 12 человек? оглавление

Для решения многих комбинаторных задач и доказательства формул применяются следующие правила комбинаторики: 1). Правило суммы: Если элемент можно выбрать m способами, а элемент - n способами, причем любой выбор элемента отличен от любого выбора элемента, то выбор или можно сделать m + n способами. Например: если на блюде лежат 7 яблок и 4 груши, то выбрать один плод можно способами. 2). Правило произведения: Пусть требуется выполнить одно за другим k действий. Если первое действие можно выполнить способами, второе действие - способами, третье действие - способами и так далее, все k действий вместе могут быть выполнены способами. оглавление

Например: Из Киева до Чернигова можно добраться пароходом, поездом, автобусом, самолетом; из Чернигова до Новгорода- Северского – пароходом и автобусом. Сколькими способами можно осуществить путешествие по маршруту Киев – Чернигов – Новгород-Северский? Так как, выбрав один из четырех возможных способов путешествия из Киева до Чернигова, имеем два возможных способа путешествия от Чернигова до Новгорода-Севеверского, то число разных путей из Киева до Новгорода-Северского равно пароход автобус пароход Киев самолет Чернигов автобус Новгород-Северский поезд оглавление

3). Метод математической индукции: Если некоторое утверждение относительно натурального числа n верно для n=1 и из того, что оно верно для n=k, следует, что оно верно и для числа n=k+1, то это утверждение верно для любого натурального числа n. Как видно из определения, доказательство методом математической индукции состоит из двух частей: - проверка справедливости утверждения для n=1 - доказательство для n=k+1, если предполагать, что оно верно для n=k, где k произвольное натуральное число. оглавление

Например: докажите, что сумма первых n нечетных чисел равна, т.е …+(2n-1)= Решение: -проверим справедливость формулы для n=1. Получим, что и - предположим, что формула верна для n=k, т.е., тогда, так как следующим за 2k-1 нечетным числом будет число 2k+1, получим Итак, что и требовалось доказать. оглавление упражнения

Упражнения: 1) докажите, что сумма первых чисел натурального ряда равна. решение оглавление теория

Доказать, что Решение: - при n = 1 формула верна: - предположим, что формула верна для n = k, т.е., тогда Итак:, что и требовалось доказать. «