Лабораторная работа 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 ³ = 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 шаров.

Но как мы можем написать, это математически? Ответ: Мы используем " функцию факториала "

	Функция факториала (символ:!)  означает умножить ряд убывающих натуральных чисел. Примеры: 4! = 4 × 3 × 2 × 1 = 24 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040 1! = 1
Обратите внимание: общепринято, что 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  2 1 3  2 3 1  3 1 2  3 2 1	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