Основные понятия комбинаторики

Тема: Основные понятия комбинаторики

КОМБИНАТОРИКА

В сказках, старинных русских сказаниях повествуется, как богатырь или другой добрый молодец, доехав до распутья, читает на камне: «Вперед поедешь – голову сложишь, направо поедешь – коня потеряешь, налево поедешь – меча лишишься». С какой проблемой сталкивается добрый молодец на перепутье? Конечно, с проблемой выбора дальнейшего пути движения.

А дальше уже говорится, как он выходит из того положения, в которое попал в результате выбора. Но выбирать разные пути или варианты приходится и современному человеку. Это сделать очень трудно не потому, что его нет или оно одно и поэтому его трудно найти, а приходится выбирать из множества возможных вариантов, различных способов, комбинаций. И нам всегда хочется, чтобы этот выбор был наилучшим.

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

Комбинаторика позволяет ответить на вопросы: сколькими способами, сколько вариантов и так далее. Слово «комбинаторика» происходит от латинского слова combinare, которое означает «соединять, сочетать».

Комбинаторика – раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов.

Термин «комбинаторика» был введён знаменитым Готфридом Вильгельмом Лейбницем, - всемирно известным немецким учёным.

Комбинаторика - важный раздел математики, знание которого необходимо представителям самых разных специальностей. С комбинаторными задачами приходится иметь дело физикам, химикам, биологам, лингвистам, специалистам по кодам и др.

Комбинаторные методы лежат в основе решения многих задач теории

вероятностей и ее приложений.

При решении комбинаторных задач можно использовать разные методы.

Правило суммы

• Если некоторый объект A можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор «либо А, либо В» можно осуществить (m + n) способами

• При использовании правила суммы надо следить, чтобы ни один из способов выбора объекта А не совпадал с каким-либо способом выбора объекта В

• Если такие совпадения есть, правило суммы утрачивает силу, и мы получаем лишь (m + n - k) способов выбора, где k – число совпадений.

Пример: В коробке находится 10 шаров: 3 белых, 2 черных, 1 синий и 4 красных. Сколькими способами можно взять из ящика цветной шар?

Решение:

Цветной шар – это синий или красный, поэтому применим правило суммы:

1 + 4 = ?

Правило произведения

Если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары (А,В) в указанном порядке можно осуществить mn способами.

При этом число способов выбора второго элемента не зависит от того, как именно выбран первый элемент.

Пример: Сколько может быть различных комбинаций выпавших граней при бросании двух игральных костей?

Решение:

На первой кости может быть: 1,2,3,4,5 и 6 очков, т.е. 6 вариантов.

На второй – 6 вариантов.

Всего: 6 ∙ 6=36 вариантов.

Правила суммы и произведения верны для любого количества объектов

Выберите правило и заполните таблицу

№1. Из города А в город В ведут 6 дорог, а из города В в город С – 3 дороги. Сколькими способами можно проехать из города А в город С?

№2. На книжной полке стоят 3 книги по алгебре, 7 по геометрии и 2 по литературе. Сколькими способами можно взять с полки одну книгу по математике?

№3. В меню имеется 4 первых блюда, 3 – вторых, 2 – десерта. Сколько различных обедов можно из них составить?

n! – эн факториал

Определение.

Произведение подряд идущих первых n натуральных чисел обозначают n! и называют «эн факториал»

n! = 1•2•3•…• (n-1) • n

Примеры:

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

Перестановки

Перестановками без повторений из n элементов по n называются комбинации, отличающиеся друг от друга только порядком расположения элементов. Число перестановок обозначается P_n

P_n = n!

Пример:

Сколько четырёхзначных чисел можно записать с помощью цифр 1,2,3,4, если каждая цифра входит в число только один раз?

Решение:

P_n = 4! = 1 ∙ 2 ∙ 3∙ 4 = 24

Размещения

Комбинации из n-элементов по k, отличающиеся друг от друга составом и порядком, называются размещениями.

=

Пример:

В звене 12 человек. Требуется выбрать звеньевого, санитара, командира. Сколькими способами это можно сделать?

Решение: сначала выбирают звеньевого, затем санитара, и наконец командира. Каждый может быть выбран звеньевым, поэтому существует 12 возможностей, для выбора санитара остаётся 11 возможностей, а выбор командира уже 10 способов. Следовательно, всего получается 12 ∙ 11 ∙ 10 = 1320 способов, что бы выбрать трёх учеников из 12 т.е.

= 12 ∙ 11 ∙ 10 = 1320

Сочетания

Комбинации из n-элементов по k, отличающиеся только составом элементов, называются сочетаниями из n -элементов по k.

=

Пример:

На тренировке занимаются 10 баскетболистов. Сколько различных стартовых пятёрок может образовать тренер?

Решение: так как при составлении стартовой пятёрки тренера интересует только состав пятёрки, то достаточно определить число сочетаний из 10 элементов по 5:

= = 252

Различие между перестановками, размещениями, сочетаниями

• В случае перестановок берутся все элементы и изменяется только их местоположение.

• В случае размещений берётся только часть элементов и важно расположение элементов друг относительно друга.

• В случае сочетаний берётся только часть элементов и не имеет значения расположение элементов друг относительно друга.

Решите самостоятельно

1. Сколько слов можно образовать из букв слова фрагмент, если слова должны состоять из 3 букв?

2. Студенту необходимо сдать 4 экзамена в течение десяти дней. Сколькими способами можно составить ему расписание экзаменов?

3. Сколькими способами из восьми человек можно избрать комиссию, состоящую из пяти членов?

4. Сколько существует различных автомобильных номеров, которые состоят из 5 цифр, если первая из них не равна нулю?