Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лабораторная работа 7
ЭЛЕМЕНТЫ КОМБИНАТОРИКИ
|
Если порядок не имеет значения, это сочетание. |
|
|
Если порядок важен это перестановка. |
|
Таким образом, мы можем называть это "Перестановочный замок"! |
Другими словами
Перестановка представляет собой упорядоченное сочетание.
Перестановки
Существуют два основных типа перестановки:
С повторением: такие, как замок выше. Код может быть "333".
Без повторений: например, первые три человека в соревнованиях по бегу. Вы не можете быть и первым и вторым одновременно
1. Перестановки с повторениями
Они самые простые для расчета.
Когда у вас есть n вещей на выбор ... У вас есть n шансов каждый раз!
При выборе r из них, перестановки:
n × n × ... (r раз)
(Другими словами, имеется n возможностей для первого выбора, потом есть n возможностей для второго выбора, и так далее, умножая их каждый раз.)
Что легче записать используя степень г:
n × n × ... (r раз) = n r
Пример: в замке выше, есть 10 номеров на выбор (0,1, .. 9) и вы выбираете 3 из них:
10 × 10 × ... (3 раза) = 10 3 = 1000 перестановок
Таким образом, формула перестановок с повторениями:
|
n r |
|
где n это количество вещей на выбор, и вы выбираете r из них |
2. Перестановки без повторений
В этом случае, вы должны сокращать количество возможных вариантов каждый раз.
|
Например, в каком порядке могут быть вытянуты 16 шаров из урны? После выбора, говорим, число "14" вы не можете выбрать его снова. |
Итак, ваш первый выбор будет иметь 16 вариантов, и ваш следующий выбор в таком случае будет иметь 15 вариантов, далее 14, 13 и т.д. А общее число перестановок будет выглядеть так:
16 × 15 × 14 × 13 × ... = 20.922.789.888.000
Но, возможно, вы не хотите выбрать их все, а только 3 из них, тогда:
16 × 15 × 14 = 3360
Другими словами, существует 3360 различных вариантов, которыми 3 шара могут быть выбраны из 16 шаров.
Но как мы можем написать, это математически? Ответ: Мы используем " функцию факториала "
|
Функция факториала (символ:!) означает умножить ряд убывающих натуральных чисел. Примеры:
|
|
|
Обратите внимание: общепринято, что 0! = 1. |
Итак, если вы хотите выбрать все бильярдные шары, перестановка будет выглядеть так:
16! = 20.922.789.888.000
Но если вы хотите выбрать только 3, то вы должны остановиться после 14. Как это сделать? Существует следующий способ ... Вы делите на 13! ...
|
16 × 15 × 14 × 13 × 12 ... |
= 16 × 15 × 14 = 3360 |
|
|
13 × 12 ... |
16! / 13! = 16 × 15 × 14
Формула перестановок без повторений выглядит следующим образом:
|
где n это количество вещей на выбор, и вы выбираете r из них |
Примеры:
Сколькими способами может первое и второе место быть присуждено из 10 человек?
|
10! |
= |
10! |
= |
3628800 |
= 90 |
|
(10-2)! |
8! |
40320 |
(То же, что и 10 × 9 = 90)
Обозначение
Вместо того чтобы писать всю формулу, люди используют различные обозначения, такие как эти:
Пример: P (10,2) = 90
Сочетания
Есть также два типа сочетаний (запомните, порядок не имеет значения):
с повторениями: например, монеты в кармане (5,5,5,10,10)
без повторений: например, лотерейные номера (2,14,15,27,30,33)
1. Сочетания без повторений
Принцип работы лотереи. Взяты номера каждый один раз, и если у вас есть счастливые номера (независимо от того, в каком порядке) вы выиграли!
Самый простой способ объяснить это состоит в следующем:
Возвращаясь к нашему примеру с бильярдными шарами, скажем, что вы просто хотите знать, какие 3 бильярдных шара были выбраны, порядок вас не интересует.
Мы уже знаем, что 3 из 16 дает нам 3360 перестановок. Порядок нас не интересует.
Например, скажем шары 1, 2 и 3 были выбраны. Существуют такие варианты:
|
Порядок важен |
Порядок значения не имеет |
|
1 2 3 |
1 2 3 |
Таким образом, перестановок будет в шесть раз больше.
На самом деле есть простой способ решить, сколько существует возможных комбинаций из "1 2 3", и мы уже говорили об этом. Ответ на этот вопрос:
3! = 3 × 2 × 1 = 6
(Другой пример: 4 вещи, могут быть размещены в 4 = 4 × 3 × 2 × 1 = 24 различными способами)
Итак, все, что нам нужно сделать, это преобразовать нашу формулу для перестановок уменьшив её, сколькими способами объекты могут быть выбраны если порядок имеет значение:
Таким образом формула сочетаний без повторений имеет вид:
|
где n это количество вещей на выбор, и вы выбираете r из них |
Также известна формула как "биномиальный коэффициента"
Обозначение
Так же как и "большие скобки", люди также используют эти обозначения:
Пример
Итак, наш пример с бильярдным шаром (теперь без порядка) является:
|
16! |
= |
16! |
= |
20.922.789.888.000 |
= 560 |
|
3! (16-3)! |
3! × 13! |
6 × 6227020800 |
Или вы могли бы сделать это таким образом:
|
16 × 15 × 14 |
= |
3360 |
= 560 |
|
3 × 2 × 1 |
6 |
Так что помните, сделайте перестановку, затем уменьшить еще на " r!"
... или, еще лучше ...
Помните Формулу!
Треугольник Паскаля
Вы также можете использовать треугольник Паскаля чтобы найти значения. Спуститесь в строке " n " (верхняя строка = 0), а затем на " r " место и значения есть ответ. Вот отрывок, отражающий строку 16:
1 14 91 364 ...
1 15 105 455 1365 ...
1 16 120 560 1820 4368 ...
2. Сочетания с повторением
Скажем, есть пять вкусов мороженого: банан, шоколад, лимон, клубника и ваниль. Вы можете выбрать три шарика. Сколько вариаций будет?
Давайте использовать буквы для вкуса: {B, C, L, S, V}. Пример выбора будет
• {C, C, C} (3 шарика шоколада)
• {B, L, V} (по одному из банана, лимона и ванили)
• {B, V, V} (один из банана, две из ванили)
(Уточним: Есть n = 5 вещей на выбор, и вы выбираете r = 3 из них.
Очередность значения не имеет, и вы можете повторить!)
Трудно описать как это рассчитать, однако объяснить принцип можно.
|
Представьте мороженное находящееся в контейнерах, можно сказать, "Движемся минуя первый контейнер, а затем берем 3 шарика, а затем движемся еще по 3 контейнерам до конца", и у вас будет 3 шарика шоколада! |
|
Теперь вы можете записать это как (Стрелка означает движение, круг означает – берем мороженное).
Приведенные примеры будут записаны следующим образом:
|
{C, C, C} (3 шарика шоколад): |
|
|
{B, L, V} (по одному из банана, лимона и ванили): |
|
|
{B, V, V} (один из банана, две из ваниль): |
Итак, вместо того чтобы беспокоиться о различных вкусах, у нас есть более простая проблема: «как много различных способов существует что бы организовать стрелки и круги"
Обратите внимание, что всегда есть 3 круга (3 шарика мороженого) и 4 стрелки (нужно двигаться 4 раза, чтобы перейти от 1-го до 5-го контейнера).
Так что есть r + (n-1) позиций, и мы хотим выбрать r из них.
Это все равно что сказать "у нас есть r + (n-1) бильярдных шаров и хотите выбрать r из них". Другими словами, это теперь как задача с бильярдными шарами, но со слегка измененными числами. И формулу можно написать так:
|
где n это количество вещей на выбор, и вы выбираете r из них |
Интересно, что мы могли бы посмотреть на стрелки вместо кругов, и мы бы тогда говорили, "у нас есть r + (n-1) позиции и хотите выбрать (n-1) из них, чтобы получить стрелки», а Ответ будет таким же ...
Так, что относительно нашего примера, каков ответ?
|
(5 +3-1)! |
= |
7! |
= |
5040 |
= 35 |
|
3! (5-1)! |
3! × 4! |
6 × 24 |
Задание
Решить все задачи!