Тема: элементы комбинаторики

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

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

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

Приведем примеры комбинаторных задач:
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) Вычислите:
Вычислите:
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 груши, то выбрать один плод можно 7 + 4 способами.
2). Правило произведения: Пусть требуется выполнить одно за другим k действий. Если первое действие можно выполнить способами, второе действие - способами, третье действие - способами и так далее, все k действий вместе могут быть выполнены способами.
оглавление

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

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

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

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

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