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

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

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

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

Комбинаторика - важный раздел математики,

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

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

вероятностей и

ее приложений.

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

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

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

В коробке находится 10 шаров: 3 белых, 2 черных, 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-1)! • n

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

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

P n = n!

Пример: Из чисел 1, 5, 9 составить трёхзначное число без повторяющихся цифр

Всего 2•3=6 комбинаций.

9

1

5

519

591

915

951

195

159

2 комбинации

2 комбинации

2 комбинации

Размещения

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

Пример: Даны числа 1, 2, 3, 4. Сколько можно составить двузначных чисел?

Сочетания

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

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

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

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

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

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

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

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

15