Формулы перестановки сочетания размещения: Перестановки, размещения и сочетания. Формулы.

Введение. Множества и выборки.

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

Для работы нам понадобятся кое-какие вспомогательные сведения. Начнём с такого фундаментального математического понятия как множество. Подробно понятие множества было раскрыто в теме «Понятие множества. Способы задания множеств» .

Очень краткий рассказ про множества : показать\скрыть

Если вкратце: множеством именуют некую совокупность объектов. Записывают множества в фигурных скобках. Порядок записи элементов роли не играет; повторения элементов не допускаются. Например, множество цифр числа 11115555999 будет таким: $\{1,5,9 \}$. Множество согласных букв в слове «тигрёнок» таково: $\{т, г, р, н, к\}$. Запись $5\in A$ означает, что элемент 5 принадлежит множеству $A=\{1,5,9 \}$. Количество элементов в конечном множестве называют мощностью этого множества и обозначают $|A|$. Например, для множества $A=\{1,5,9 \}$, содержащего 3 элемента, имеем: $|A|=3$.

Рассмотрим некое непустое конечное множество $U$, мощность которого равна $n$, $|U|=n$ (т.е. в множестве $U$ имеется $n$ элементов). Введём такое понятие, как выборка (некоторые авторы именуют её кортежем). Под выборкой объема $k$ из $n$ элементов (сокращённо $(n,k)$-выборкой) будем понимать набор элементов $(a_1, a_2,\ldots, a_k)$, где $a_i\in U$. Выборка называется упорядоченной, если в ней задан порядок следования элементов. Две упорядоченные выборки, различающиеся лишь порядком элементов, являются различными. Если порядок следования элементов выборки не является существенным, то выборку именуют неупорядоченной.

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

Для примера рассмотрим множество $U=\{a,b,c,d,e\}$. Множество $U$ содержит 5 элементов, т.е. $|U|=5$. Выборка без повторений может быть такой: $(a,b,c)$. Данная выборка содержит 3 элемента, т.е. объём этой выборки равен 3. Иными словами, это $(5,3)$-выборка.

Выборка с повторениями может быть такой: $(a,a,a,a,a,c,c,d)$. Она содержит 8 элементов, т.е. объём её равен 8. Иными словами, это $(5,8)$-выборка.

Рассмотрим ещё две $(5,3)$-выборки: $(a,b,b)$ и $(b,a,b)$. Если мы полагаем наши выборки неупорядоченными, то выборка $(a,b,b)$ равна выборке $(b,a,b)$, т.е. $(a,b,b)=(b,a,b)$. Если мы полагаем наши выборки упорядоченными, то $(a,b,b)\neq(b,a,b)$.

Рассмотрим ещё один пример, немного менее абстрактный:) Предположим, в корзине лежат шесть конфет, причём все они различны. Если первой конфете поставить в соответствие цифру 1, второй конфете — цифру 2 и так далее, то с конфетами в корзине можно сопоставить такое множество: $U=\{1,2,3,4,5,6\}$. Представьте, что мы наугад запускаем руку в корзинку с целью вытащить три конфеты. Вытащенные конфеты — это и есть выборка. Так как мы вытаскиваем 3 конфеты из 6, то получаем (6,3)-выборку. Порядок расположения конфет в ладони совершенно несущественен, поэтому эта выборка является неупорядоченной. Ну, и так как все конфеты различны, то выборка без повторений. Итак, в данной ситуации говорим о неупорядоченной (6,3)-выборке без повторений.

Теперь подойдём с иной стороны. Представим себе, что мы находимся на фабрике по производству конфет, и на этой фабрике производятся конфеты четырёх сортов. Множество $U$ в этой ситуации таково: $U=\{1,2,3,4 \}$ (каждая цифра отвечает за свой сорт конфет). Теперь вообразим, что все конфеты ссыпаются в единый жёлоб, около которого мы и стоим. И, подставив ладони, из этого потока отбираем 20 конфет. Конфеты в горсти – это и есть выборка. Играет ли роль порядок расположения конфет в горсти? Естественно, нет, поэтому выборка неупорядоченная. Всего 4 сорта конфет, а мы отбираем двадцать штук из общего потока — повторения сортов неизбежны. При этом выборки могут быть самыми различными: у нас даже могут оказаться все конфеты одного сорта. Следовательно, в этой ситуации мы имеем дело с неупорядоченной (4,20)-выборкой с повторениями.

Рассмотрим ещё пару примеров. Пусть на кубиках написаны различные 7 букв: к, о, н, ф, е, т, а. Эти буквы образуют множество $U=\{к,о,н,ф,е,т,а\}$. Допустим, из данных кубиков мы хотим составить «слова» из 5 букв. Буквы этих слов (к примеру, «конфе», «тенко» и так далее) образуют (7,5)-выборки: $(к,о,н,ф,е)$, $(т,е,н,к,о)$ и т.д. Очевидно, что порядок следования букв в такой выборке важен. Например, слова «нокфт» и «кфтон» различны (хотя состоят из одних и тех же букв), ибо в них не совпадает порядок букв. Повторений букв в таких «словах» нет, ибо в наличии только семь кубиков. Итак, набор букв каждого слова представляет собой упорядоченную (7,5)-выборку без повторений.

Еще один пример: мы составляем всевозможные восьмизначные числа из четырёх цифр 1, 5, 7, 8. Например, 11111111, 15518877, 88881111 и так далее.{k}=\frac{n!}{(n-k)!} \end{equation}

Что обозначает знак «!»? : показать\скрыть

Запись «n!» (читается «эн факториал») обозначает произведение всех чисел от 1 до n, т.е.

$$ n!=1\cdot2\cdot 3\cdot \ldots\cdot n $$

По определению полагается, что $0!=1!=1$. Для примера найдём 5!:

$$ 5!=1\cdot 2\cdot 3\cdot 4\cdot 5=120. $$

Пример №1

Алфавит состоит из множества символов $E=\{+,*,0,1,f\}$. Определим количество таких трёхсимвольных слов в этом алфавите, которые не содержат повторяющихся букв.

Под трёхсимвольными словами будем понимать выражения вида «+*0» или «0f1». В множестве $E$ пять элементов, поэтому буквы трехсимвольных слов образуют (5,3)-выборки. Первый вопрос: эти выборки упорядочены или нет? Слова, которые отличаются лишь порядком букв, полагаются различными, поэтому порядок элементов в выборке важен. Значит, выборка является упорядоченной. Второй вопрос: допускаются повторения или нет? Ответ на этот вопрос даёт условие: слова не должны содержать повторяющихся букв.{n}=\frac{n!}{(n-n)!}=\frac{n!}{0!}=\frac{n!}{1}=n! $$

Пример №3

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

Пусть первому мороженому соответствует цифра 1, второму — цифра 2 и так далее. Мы получим множество $U=\{1,2,3,4,5\}$, которое будет представлять содержимое морозилки. Порядок съедения может быть таким: $(2,1,3,5,4)$ или таким: $(5,4,3,1,2)$. Каждый подобный набор есть (5,5)-выборка. Она будет упорядоченной и без повторений. Иными словами, каждая такая выборка есть перестановка из 5 элементов исходного множества. Согласно формуле (3) общее количество этих перестановок таково:

$$ P_5=5!=120. $$

Следовательно, существует 120 порядков выбора очередности съедения.

Ответ : 120.

Перестановки с повторениями

Перестановка с повторениями – упорядоченная $(n,k)$-выборка с повторениями, в которой элемент $a_1$ повторяется $k_1$ раз, $a_2$ повторяется $k_2$ раза так далее, до последнего элемента $a_r$, который повторяется $k_r$ раз. При этом $k_1+k_2+\ldots+k_r=k$.

Общее количество перестановок с повторениями определяется формулой:

\begin{equation}P_{k}(k_1,k_2,\ldots,k_r)=\frac{k!}{k_1!\cdot k_2!\cdot \ldots \cdot k_r!} \end{equation}

Пример №4

Слова составляются на основе алфавита $U=\{a,b,d\}$. Сколько различных слов из семи символов может быть составлено, если в этих словах буква «a» должна повторяться 2 раза; буква «b» — 1 раз, а буква «d» — 4 раза?

Вот примеры искомых слов: «aabdddd», «daddabd» и так далее. Буквы каждого слова образуют (3,7)-выборку с повторениями: $(a,a,b,d,d,d,d)$, $(d,a,d,d,a,b,d)$ и т.д. Каждая такая выборка состоит из двух элементов «a», одного элемента «b» и четырёх элементов «d». Иными словами, $k_1=2$, $k_2=1$, $k_3=4$. Общее количество повторений всех символов, естественно, равно объёму выборки, т.е. $k=k_1+k_2+k_3=7$. Подставляя эти данные в формулу (4), будем иметь:

$$ P_7(2,1,4)=\frac{7!}{2!\cdot 1!\cdot 4!}=105. $$

Следовательно, общее количество искомых слов равно 105.{k}=\frac{n!}{(n-k)!\cdot k!} \end{equation}

Пример №5

В корзине размещены карточки, на которых написаны целые числа от 1 до 10. Из корзины вынимают 4 карточки и суммируют числа, написанные на них. Сколько различных наборов карточек можно вытащить из корзины?

Итак, в данной задаче исходное множество таково: $U=\{1,2,3,4,5,6,7,8,9,10\}$. Из этого множества мы выбираем четыре элемента (т.е., четыре карточки из корзины). Номера вытащенных элементов образуют (10,4)-выборку. Повторения в этой выборке не допускаются, так как номера всех карточек различны. Вопрос вот в чём: порядок выбора карточек играет роль или нет? Т.е., к примеру, равны ли выборки $(1,2,7,10)$ и $(10,2,1,7)$ или не равны? Тут нужно обратиться к условию задачи. Карточки вынимаются для того, чтобы потом найти сумму элементов. А это значит, что порядок карточек не важен, так как от перемены мест слагаемых сумма не изменится. Например, выборке $(1,2,7,10)$ и выборке $(10,2,1,7)$ будет соответствовать одно и то же число $1+2+7+10=10+2+1+7=20$.{k}=\frac{(n+k-1)!}{(n-1)!\cdot k!} \end{equation}

Пример №6

Представьте себе, что мы находимся на конфетном заводе, — прямо возле конвейера, по которому движутся конфеты четырёх сортов. Мы запускаем руки в этот поток и вытаскиваем двадцать штук. Сколько всего различных «конфетных комбинаций» может оказаться в горсти?

Если принять, что первому сорту соответствует число 1, второму сорту — число 2 и так далее, то исходное множество в нашей задаче таково: $U=\{1,2,3,4\}$. Из этого множества мы выбираем 20 элементов (т.е., те самые 20 конфет с конвейера). Пригоршня конфет образует (4,20)-выборку. Естественно, повторения сортов будут. Вопрос в том, играет роль порядок расположения элементов в выборке или нет? Из условия задачи следует, что порядок расположения элементов роли не играет. Нам нет разницы, будут ли в горсти располагаться сначала 15 леденцов, а потом 4 шоколадных конфеты, или сначала 4 шоколадных конфеты, а уж потом 15 леденцов. Итак, мы имеем дело с неупорядоченной (4,20) выборкой с повторениями.{20}=\frac{(4+20-1)!}{(4-1)!\cdot 20!}=\frac{23!}{3!\cdot 20!}=1771. $$

Следовательно, общее количество искомых комбинаций равно 1771.

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

Основная формула комбинаторики

Пусть имеется k групп элементов, причем i-я группа состоит из n i элементов. Выберем по одному элементу из каждой группы. Тогда общее число N способов, которыми можно произвести такой выбор, определяется соотношением N=n 1 *n 2 *n 3 *…*n k .

Пример 1. Поясним это правило на простом примере. Пусть имеется две группы элементов, причем первая группа состоит из n 1 элементов, а вторая — из n 2 элементов. Сколько различных пар элементов можно составить из этих двух групп, таким образом, чтобы в паре было по одному элементу от каждой группы? Допустим, мы взяли первый элемент из первой группы и, не меняя его, перебрали все возможные пары, меняя только элементы из второй группы. Таких пар для этого элемента можно составить n 2 . Затем мы берем второй элемент из первой группы и также составляем для него все возможные пары. Таких пар тоже будет n 2 . Так как в первой группе всего n 1 элемент, всего возможных вариантов будет n 1 *n 2 .

Пример 2. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если цифры могут повторяться?
Решение: n 1 =6 (т.к. в качестве первой цифры можно взять любую цифру из 1, 2, 3, 4, 5, 6), n 2 =7 (т.к. в качестве второй цифры можно взять любую цифру из 0, 1, 2, 3, 4, 5, 6), n 3 =4 (т.к. в качестве третьей цифры можно взять любую цифру из 0, 2, 4, 6).
Итак, N=n 1 *n 2 *n 3 =6*7*4=168.

В том случае, когда все группы состоят из одинакового числа элементов, т.е. n 1 =n 2 =…n k =n можно считать, что каждый выбор производится из одной и той же группы, причем элемент после выбора снова возвращается в группу. Тогда число всех способов выбора равно n k . Такой способ выбора в комбинаторики носит название выборки с возвращением.

Пример 3. Сколько всех четырехзначных чисел можно составить из цифр 1, 5, 6, 7, 8?
Решение. Для каждого разряда четырехзначного числа имеется пять возможностей, значит N=5*5*5*5=5 4 =625.

Рассмотрим множество, состоящие из n элементов. Это множество в комбинаторике называется генеральной совокупностью .

Число размещений из n элементов по m

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

Пример 4. Различными размещениями из трех элементов {1, 2, 3} по два будут наборы (1, 2), (2, 1), (1, 3), (3, 1), (2, 3),(3, 2). Размещения могут отличаться друг от друга как элементами, так и их порядком.

Число размещений в комбинаторике обозначается A n m и вычисляется по формуле:

Замечание: n!=1*2*3*…*n (читается: «эн факториал»), кроме того полагают, что 0!=1.

Пример 5 . Сколько существует двузначных чисел, в которых цифра десятков и цифра единиц различные и нечетные?
Решение: т.к. нечетных цифр пять, а именно 1, 3, 5, 7, 9, то эта задача сводится к выбору и размещению на две разные позиции двух из пяти различных цифр, т.е. указанных чисел будет:

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

Пример 6 . Для множества {1, 2, 3}сочетаниями являются {1, 2}, {1, 3}, {2, 3}.

Число сочетаний из n элементов по m

Число сочетаний обозначается C n m и вычисляется по формуле:

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

Решение: Число способов равно числу сочетаний из шести книжек по две, т.е. равно:

Перестановки из n элементов

Определение 3. Перестановкой из n элементов называется любой упорядоченный набор этих элементов.

Пример 7a. Всевозможными перестановками множества, состоящего из трех элементов {1, 2, 3} являются: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3), (3, 2, 1), (3, 1, 2).

Число различных перестановок из n элементов обозначается P n и вычисляется по формуле P n =n!.

Пример 8. Сколькими способами семь книг разных авторов можно расставить на полке в один ряд?

Решение: эта задача о числе перестановок семи разных книг. Имеется P 7 =7!=1*2*3*4*5*6*7=5040 способов осуществить расстановку книг.

Обсуждение. Мы видим, что число возможных комбинаций можно посчитать по разным правилам (перестановки, сочетания, размещения) причем результат получится различный, т.к. принцип подсчета и сами формулы отличаются. Внимательно посмотрев на определения, можно заметить, что результат зависит от нескольких факторов одновременно.

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

Во-вторых, результат зависит от того, какой величины наборы элементов нам нужны.

И последнее, важно знать, является ли для нас существенным порядок элементов в наборе. Поясним последний фактор на следующем примере.

Пример 9. На родительском собрании присутствует 20 человек. Сколько существует различных вариантов состава родительского комитета, если в него должны войти 5 человек?
Решение: В этом примере нас не интересует порядок фамилий в списке комитета. Если в результате в его составе окажутся одни и те же люди, то по смыслу для нас это один и тот же вариант. Поэтому мы можем воспользоваться формулой для подсчета числа сочетаний из 20 элементов по 5.

Иначе будут обстоять дела, если каждый член комитета изначально отвечает за определенное направление работы. Тогда при одном и том же списочном составе комитета, внутри него возможно 5! вариантов перестановок , которые имеют значение. Количество разных (и по составу, и по сфере ответственности) вариантов определяется в этом случае числом размещений из 20 элементов по 5.

Задачи для самопроверки
1. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если цифры могут повторяться?

2. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?

3. В классе десять предметов и пять уроков в день. Сколькими способами можно составить расписание на один день?

4. Сколькими способами можно выбрать 4 делегата на конференцию, если в группе 20 человек?

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

6. Из трех математиков и десяти экономистов надо составить комиссию, состоящую из двух математиков и шести экономистов. Сколькими способами это можно сделать?

Сочетание размещение перестановка формулы. Основные формулы комбинаторики. Комбинаторика: формула перестановки, размещения

В данной статье речь пойдет об особом разделе математики под названием комбинаторика. Формулы, правила, примеры решения задач — все это вы сможете найти здесь, прочитав статью до самого конца.

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

Комбинаторные конфигурации

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

• размещение;
• перестановка;
• сочетание;
• композиция числа;
• разбиение числа.

О первых трех мы поговорим более подробно далее, а вот композиции и разбиению мы уделим внимание в данном разделе. Когда говорят о композиции некого числа (допустим, а), то подразумевают представление числа а в виде упорядоченной суммы неких положительных чисел. А разбиение — это неупорядоченная сумма.

Разделы

Прежде чем мы перейдем непосредственно к формулам комбинаторики и рассмотрению задач, стоит обратить внимание на то, что комбинаторика, как и другие разделы математики, имеет свои подразделы. К ним относятся:

• перечислительная;
• структурная;
• экстремальная;
• теория Рамсея;
• вероятностная;
• топологическая;
• инфинитарная.

В первом случае речь идет об исчисляющей комбинаторике, задачи рассматривают перечисление или подсчет разных конфигураций, которые образованы элементами множеств. На данные множества, как правило, накладываются какие-либо ограничения (различимость, неразличимость, возможность повтора и так далее). А количество этих конфигураций подсчитывается при помощи правила сложения или умножения, о которых мы поговорим немного позже. К структурной комбинаторике относятся теории графов и матроидов. Пример задачи экстремальной комбинаторики — какова наибольшая размерность графа, который удовлетворяет следующим свойствам… В четвертом пункте мы упомянули теорию Рамсея, которая изучает в случайных конфигурациях наличие регулярных структур. Вероятностная комбинаторика способна нам ответить на вопрос — какова вероятность того, что у заданного множества присутствует определенное свойство. Как нетрудно догадаться, топологическая комбинаторика применяет методы в топологии. И, наконец, седьмой пункт — инфинитарная комбинаторика изучает применение методов комбинаторики к бесконечным множествам.

Правило сложения

Среди формул комбинаторики можно найти и довольно простые, с которыми мы достаточно давно знакомы. Примером является правило суммы. Предположим, что нам даны два действия (С и Е), если они взаимоисключаемы, действие С выполнимо несколькими способами (например а), а действие Е выполнимо b-способами, то выполнить любое из них (С или Е) можно а+b способами.

В теории это понять достаточно трудно, постараемся донести всю суть на простом примере. Возьмем среднюю численность учеников одного класса — допустим, это двадцать пять. Среди них пятнадцать девочек и десять мальчиков. Ежедневно в классе назначается один дежурный. Сколько есть способов назначить дежурного по классу сегодня? Решение задачи достаточно простое, мы прибегнем к правилу сложения. В тексте задачи не сказано, что дежурными могут быть только мальчики или только девочки. Следовательно, им может оказаться любая из пятнадцати девочек или любой из десяти мальчиков. Применяя правило суммы, мы получаем достаточно простой пример, с которым без труда справится школьник начальных классов: 15 + 10. Подсчитав, получаем ответ: двадцать пять. То есть существует всего двадцать пять способов назначить на сегодня дежурного класса.

Правило умножения

К основным формулам комбинаторики относится и правило умножения. Начнем с теории. Допустим, нам необходимо выполнить несколько действий (а): первое действие выполняется с1 способами, второе — с2 способами, третье — с3 способами и так далее до последнего а-действия, выполняемого са способами. Тогда все эти действия (которых всего у нас а) могут быть выполнены N способами. Как высчитать неизвестную N? В этом нам поможет формула: N = с1 * с2 * с3 *…* са.

Опять же, в теории ничего не понятно, переходим к рассмотрению простого примера на применение правила умножения. Возьмем все тот же класс из двадцати пяти человек, в котором учится пятнадцать девочек и десять мальчиков. Только на этот раз нам необходимо выбрать двух дежурных. Ими могут быть как только мальчики или девочки, так и мальчик с девочкой. Переходим к элементарному решению задачи. Выбираем первого дежурного, как мы решили в прошлом пункте, у нас получается двадцать пять возможных вариантов. Вторым дежурным может быть любой из оставшихся человек. У нас было двадцать пять учеников, одного мы выбрали, значит вторым дежурным может быть любой из оставшихся двадцати четырех человек. Наконец, применяем правило умножения и получаем, что двоих дежурных можно избрать шестью сотнями способов. Мы данное число получили умножением двадцати пяти и двадцати четырех.

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

Сейчас мы рассмотрим еще одну формулу комбинаторики. В данном разделе статьи мы поговорим о перестановках. Рассмотреть проблему предлагаем сразу же на примере. Возьмем бильярдные шары у нас их n-ое количество. Нам нужно подсчитать: сколько есть вариантов расставить их в ряд, то есть составить упорядоченный набор.

Начнем, если у нас нет шаров, то и вариантов расстановки у нас так же ноль. А если у нас шар один, то и расстановка тоже одна (математически это можно записать следующим образом: Р1 = 1). Два шара можно расставить двумя разными способами: 1,2 и 2,1. Следовательно, Р2 = 2. Три шара можно расставить уже шестью способами (Р3=6): 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,2,1; 3,1,2. А если таких шаров не три, а десять или пятнадцать? Перечислять все возможные варианты очень долго, тогда нам на помощь приходит комбинаторика. Формула перестановки поможет нам найти ответ на интересующий нас вопрос. Pn = n *P (n-1). Если попытаться упростить формулу, то получаем: Pn = n* (n — 1) *…* 2 * 1. А это и есть произведение первых натуральных чисел. Такое число называется факториалом, а обозначается как n!

Рассмотрим задачу. Вожатый каждое утро выстраивает свой отряд в шеренгу (двадцать человек). В отряде есть три лучших друга — Костя, Саша и Леша. Какова вероятность того, что они будут стоять рядом? Чтобы найти ответ на вопрос, нужно вероятность «хорошего» исхода поделить на общее количество исходов. Общее число перестановок составляет 20! = 2,5 квинтиллиона. Как посчитать количество «хороших» исходов? Предположим, что Костя, Саши и Леша — это один сверхчеловек. Тогда мы имеем всего восемнадцать субъектов. Число перестановок в данном случае равняется 18 = 6,5 квадриллионов. При всем этом, Костя, Саша и Леша могут произвольно перемещаться между собой в своей неделимой тройке, а это еще 3! = 6 вариантов. Значит всего «хороших» расстановок у нас 18! * 3! Нам остается только найти искомую вероятность: (18! * 3!) / 20! Что равняется примерно 0,016. Если перевести в проценты, то это получается всего 1,6%.

Размещение

Сейчас мы рассмотрим еще одну очень важную и необходимую формулу комбинаторики. Размещение — это наш следующий вопрос, который предлагаем вам рассмотреть в данном разделе статьи. Мы идем на усложнение. Предположим, что мы хотим рассмотреть возможные перестановки, только не из всего множества (n), а из меньшего (m). То есть мы рассматриваем перестановки из n предметов по m.

Основные формулы комбинаторики стоит не просто заучивать, а понимать их. Даже несмотря на то, что они усложняются, так как у нас не один параметр, а два. Предположим, что m = 1, то и А = 1, m = 2, то А = n * (n — 1). Если далее упрощать формулу и перейти на запись при помощи факториалов, то получится вполне лаконичная формула: А = n! / (n — m)!

Сочетание

Мы рассмотрели практически все основные формулы комбинаторики с примерами. Теперь перейдем к заключительному этапу рассмотрения базового курса комбинаторики — знакомство с сочетанием. Сейчас мы будем выбирать m предметов из имеющихся у нас n, при этом всем мы будем выбирать всеми возможными способами. Чем же тогда это отличается от размещения? Мы не будем учитывать порядок. Этот неупорядоченный набор и будет являться сочетанием.

Сразу введем обозначение: С. Берем размещения m шариков из n. Мы перестаем обращать внимание на порядок и получаем повторяющиеся сочетания. Чтобы получить число сочетаний нам надо поделить число размещений на m! (m факториал). То есть С = А / m! Таким образом, способов выбрать из n шаров немножко, равняется примерно столько, сколько выбрать почти все. Этому есть логическое выражение: выбрать немножко все равно, что выкинуть почти все. Еще в данном пункте важно упомянуть и то, что максимальное число сочетаний можно достигнуть при попытке выбрать половину предметов.

Как выбрать формулу для решения задачи?

Мы подробно рассмотрели основные формулы комбинаторики: размещение, перестановка и сочетание. Теперь наша задача — облегчить выбор необходимой формулы для решения задачи по комбинаторике. Можно воспользоваться следующей довольно простой схемой:

1. Задайте себе вопрос: порядок размещения элементов учитывается в тексте задачи?
2. Если ответ нет, то воспользуйтесь формулой сочетания (С = n! / (m! * (n — m)!)).
3. Если ответ нет, то необходимо ответить на еще один вопрос: все ли элементы входят в комбинацию?
4. Если ответ да, то воспользуйтесь формулой перестановки (Р = n!).
5. Если ответ нет, то воспользуйтесь формулой размещения (А = n! / (n — m)!).

Пример

Мы рассмотрели элементы комбинаторики, формулы и некоторые другие вопросы. Теперь перейдем к рассмотрению реальной задачи. Представьте, что перед вами лежат киви, апельсин и банан.

Вопрос первый: сколькими способами их можно переставить? Для этого воспользуемся формулой перестановок: Р = 3! = 6 способов.

Вопрос второй: сколькими способами можно выбрать один фрукт? Это очевидно, у нас всего три варианта — выбрать киви, апельсин или банан, но применим формулу сочетаний: С = 3! / (2! * 1!) = 3.

Вопрос третий: сколькими способами можно выбрать два фрукта? Какие есть у нас вообще варианты? Киви и апельсин; киви и банан; апельсин и банан. То есть три варианта, но это легко проверить при помощи формулы сочетания: С = 3! / (1! * 2!) = 3

Вопрос четвертый: сколькими способами можно выбрать три фрукта? Как видно, выбрать три фрукта можно одним-единственным способом: взять киви, апельсин и банан. С = 3! / (0! * 3!) = 1.

Вопрос пятый: сколькими способами можно выбрать хотя бы один фрукт? Это условие подразумевает, что мы можем взять один, два или все три фрукта. Следовательно, мы складываем С1 + С2 + С3 =3 + 3 + 1 = 7. То есть у нас есть семь способов взять со стола хотя бы один фрукт.

Число размещений без повторений из n по k n k различными координатами.

Число размещений без повторений находится по формуле:

Пример: Сколькими способами можно построить 3-значное число с различными цифрами, не содержащее цифры 0?

Количество цифр
, размерность вектора с различными координатами

Число размещений с повторениями

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

Число размещений с повторениями находится по формуле:

.

Пример: Сколько слов длины 6 можно составить из 26 букв латинского алфавита?

Количество букв
, размерность вектора

Число перестановок без повторений

Число перестановок без повторений из n элементов – это число способов, сколькими можно расположить на n различных местах n различных элементов.

Число перестановок без повторений находится по формуле:

.

Замечание: Мощность искомого множества А удобно искать по формуле:
, гдех – число способов выбрать нужные места; у – число способов расположить на них нужные элементы; z – число способов расположить остальные элементы на оставшихся местах.

Пример. Сколькими способами можно расставить на книжной полке 5 различных книг? В скольких случаях две определенные книги А и В окажутся рядом?

Всего способов расставить 5 книг на 5-ти местах – равно = 5! = 120.

В задаче х – число способов выбрать два места рядом, х = 4; у – число способов расположить две книги на двух местах, у = 2! = 2; z – число способов расположить остальные 3 книги на оставшихся 3-х местах, z = 3! = 6. Значит
= 48.

Число сочетаний без повторений

Число сочетаний без повторений из n по k – это число способов, сколькими можно из n различных элементов выбрать k штук без учета порядка.

Число сочетаний без повторений находится по формуле:

.

Свойства:

1)
; 2)
; 3)
;

4)
; 5)
; 6)
.

Пример. В урне 7 шаров. Из них 3 белых. Наугад выбирают 3 шара. Сколькими способами это можно сделать? В скольких случаях среди них будет ровно один белый.

Всего способов
. Чтобы получить число способов выбрать 1 белый шар (из 3-х белых) и 2 черных шара (из 4-х черных), надо перемножить
и
Таким образом искомое количество способов

Упражнения

1. Из 35 учащихся класс по итогам года имели “5” по математике – 14 человек; по физике – 15 человек; по химии – 18 человек; по математике и физике – 7 человек; по математике и химии – 9 человек; по физике и химии – 6 человек; по всем трем предметам – 4 человек. Сколько человек имеют “5” по указанным предметам? Сколько человек не имеет “5” по указанным предметам? Имеет “5” только по математике? Имеет “5” только по двум предметам?

2. В группе из 30 студентов каждый знает, по крайней мере, один иностранный язык – английский или немецкий. Английский знают 22 студента, немецкий – 17. Сколько студентов знают оба языка? Сколько студентов знают немецкий язык, но не знают английский?

3. В 20 комнатах общежития института Дружбы Народов живут студенты из России; в 15 – из Африки; в 20 – из стран Южной Америки. Причем в 7 – живут россияне и африканцы, в 8 – россияне и южноамериканцы; в 9 – африканцы и южноамериканцы; в 3 – и россияне, и южноамериканцы, и африканцы. В скольких комнатах живут студенты: 1) только с одного континента; 2) только с двух континентов; 3) только африканцы.

4. Каждый из 500 студентов обязан посещать хотя бы один из трех спецкурсов: по математике, физике и астрономии. Три спецкурса посещают 10 студентов, по математике и физике – 30 студентов, по математике и астрономии – 25; спецкурс только по физике – 80 студентов. Известно также, что спецкурс по математике посещают 345 студентов, по физике – 145, по астрономии – 100 студентов. Сколько студентов посещают спецкурс только по астрономии? Сколько студентов посещают два спецкурса?

5. Староста курса представил следующий отчет по физкультурной работе. Всего – 45 студентов. Футбольная секция – 25 человек, баскетбольная секция – 30 человек, шахматная секция – 28 человек. При этом, 16 человек одновременно посещают футбольную и баскетбольную секции, 18 – футбольную и шахматную, 17 – баскетбольную и шахматную, 15 человек посещают все три секции. Объясните, почему отчет не был принят.

6. В аквариуме 11 рыбок. Из них 4 красных, остальные золотые. Наугад выбирают 4 рыбки. Сколькими способами это можно сделать? Найти число способов сделать это так, чтобы среди них будет: 1) ровно одна красная; 2) ровно 2 золотых; 3) хотя бы одна красная.

7. В списке 8 фамилий. Из них 4 – женские. Сколькими способами их можно разделить на две равные группы так, чтоб в каждой была женская фамилия?

8. Из колоды в 36 карт выбирают 4 . Сколько способов сделать это так, чтобы: 1) все карты были разных мастей; 2) все карты были одной масти; 3) 2 красные и 2 черные.

9. На карточках разрезной азбуки даны буквы К, К, К, У, У, А, Е, Р. Сколько способов сложить их в ряд так, что бы получилось «кукареку».

10. Даны карточки разрезанной азбуки с буквами О, Т, О, Л, О, Р, И, Н, Г, О, Л, О, Г. Сколько способов сложить их так, что бы получилось слово «отолоринголог».

11. Даны карточки нарезной азбуки с буквами Л, И, Т, Е, Р, А, Т, У, Р, А. Сколько способов сложить их в ряд так, что бы получилось слово «литература».

12. 8 человек становятся в очередь. Сколько способов сделать это так, что бы два определенных человека А и Б оказались: 1) рядом; 2) на краях очереди;

13. 10 человек садятся за круглый стол на 10 мест. Сколькими способами это можно сделать так, чтоб рядом оказались: 1) два определенных человека А и Б; 2) три определенных человека А, Б и С.

14. Из 10 арабских цифр составляют 5-значный код. Сколькими способами это можно сделать так, чтобы: 1) все цифры были разными; 2) на последнем месте четная цифра.

15. Из 26 букв латинского алфавита (среди них 6 гласных) составляется шестибуквенное слово. Сколькими способами это можно сделать так, чтобы в слове были: 1) ровно одна буква «а»; 2) ровно одна гласная буква; ровно две буквы «а»; в) ровно две гласные.

16. Сколько четырехзначных чисел делятся на 5?

17. Сколько четырехзначных чисел с различными цифрами делятся на 25?

19. Брошены 3 игральные кости. В скольких случаях выпала: 1) ровно 1 «шестерка»; 2) хотя бы одна «шестерка».

20. Брошены 3 игральные кости. В скольких случаях будет: 1) все разные; 2) ровно два одинаковых числа очков.

21. Сколько слов с различными буквами можно составить из алфавита а, в, с, d. Перечислить их все в лексикографическом порядке: abcd, abcd….

Комбинаторика — это раздел математики, основной задачей которой является подсчёт числа вариантов, возникающих в той или иной ситуации. При решении задач с использованием классического определения вероятности нам понадобятся некоторые формулы комбинаторики.

Размещения .

Определение 1. Размещением без повторений из n элементов по k называется всякое упорядоченное подмножество данного множества M={a 1 ,a 2 ,¼,a n }, содержащее k элементов.

Отметим, что из определения сразу следует, что, во-первых, все элементы в размещении без повторений различны (в противном случае найдется два одинаковых элемента), во-вторых, k£ n , в-третьих, два различных размещения без повторений различаются либо составом входящих в них элементов, либо порядком их расположения. То есть порядок следования существенен.

Теорема 1. Число различных размещений без повторений из n элементов по k (k£ n) равно

Доказательство.

Пусть M ={a 1 ,a 2 ,¼,a n }. Требуется определить число различных строк вида (x 1 ,x 2 ,¼,x k ), где все элементы x 1 ,x 2 ,¼,x k ÎM и различны. Первый элемент x 1 можно выбрать n способами. Если x 1 уже выбран, то для выбора x 2 осталось n-1 элементов. Аналогично, x 3 можно выбрать n -2 способами и т.д. Последний элемент x k можно выбрать n-k+1 способами. Перемножая эти числа, получим формулу (4).Теорема доказана.

Пример 1. В классе 12 учебных предметов и в понедельник 5 разных уроков. Сколькими способами может быть составлено расписание занятий на понедельник?

Число всевозможных вариантов расписания есть, очевидно, число различных размещений из 12 элементов по 5, то есть

Важным частным случаем, является случай, когда n=k , то есть когда в строке (x 1 ,x 2 ,¼,x n) участвуют все элементы множества M . Строки без повторений, составленные из n элементов множества M называют перестановками из n элементов. Напомним, что в математике через n! обозначают произведение всех натуральных чисел от 1 до n, то есть ¼и по определению считают, что 0!=1.

Следствие 1 . Пользуясь формулой (4), находим, что число различных перестановок P n из n элементов равно P n = n !.

Определение 2. Размещением с повторениями из n элементов по k называется любая упорядоченная строка из k элементов множества M={a 1 ,a 2 ,¼,a n }, некоторые из которых могут повторяться.

Например, слово “мама” есть размещение с повторениями из 2-х элементов M ={м, а} по 4.

Теорема 2. Число различных размещений с повторениями из n элементов по k

Доказательство.

Первый элемент в строку из k элементов может быть выбран n способами, поскольку |M|=n. Точно также 2-й, 3-й, …,k-й элементы могут быть выбраны n способами. Перемножая эти числа, получим

k раз

Теорема доказана.

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

В этой задаче M ={1, 2, 3, 4, 5}, n=5, k=2.Поэтому ответом является число

Пример 3. Сколькими способами k пассажиров могут распределиться по n вагонам, если для каждого пассажира существенным является только номер вагона, а не занимаемое им в вагоне место?

Перенумеруем всех пассажиров. Пусть x 1 — номер вагона, выбранного первым пассажиром, x 2 — номер вагона второго пассажира, …, x k — номер вагона k -го пассажира. Строка (x 1 ,x 2 ,¼,x k ) полностью характеризует распределение пассажиров по вагонам. Каждое из чисел x 1 ,x 2 ,¼,x k может принимать любое целое значение от 1 до n. Поэтому в этом примере

M ={1, 2,…,n} и различных распределений по вагонам будет столько же, сколько строк длиной k можно составить из элементов множества M , то есть

Отметим ещё раз, что в размещениях с повторениями и без повторений важен порядок следования элементов. Если порядок следования элементов не существенен, то в этом случае говорят о сочетаниях.

Сочетания (без повторения ).

Определение 3. Пусть M={a 1 ,a 2 ,¼,a n }. Любое подмножество X мно-жества M , содержащее k элементов, называется сочетанием k элементов из n.

Отметим сразу, что в этом определении порядок следования элементов множества X несущественен и, что k£n , поскольку k=½X½, n=½M½ и XÍM .

Теорема 3. Число различных сочетаний k элементов из n равно

. (6)

Доказательство.

Каждое сочетание k элементов из n порождает k! различных размещений без повторений из n по k с помощью различных перестановок (см. следствие 1). Таким образом, все сочетаний из k элементов из n после различных k! перестановок порождают все размещений без повторений из n по k . Поэтому . Следовательно,

Цель занятия: уметь применять основные формулы комбинаторики и знать условия применения этих формул; знать свойства биномиальных коэффициентов и уметь определять разложение бинома при конкретных значениях n.

План занятия:

1. Число размещений.

2. Число перестановок.

3. Число сочетаний.

4. Повторения.

5. Бином Ньютона. Треугольник Паскаля.

Методические указания по изучению темы

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

Комбинаторика – область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из элементов, принадлежащих данному множеству. Термин «комбинаторика» происходит от латинского слова combina – сочетать, соединять.

Пусть есть некоторое множество из n элементов: x 1, x 2, x 3, …, x n .

Из этого множества можно образовать различные подмножества, то есть выборки, каждая из которых содержит m элементов (0 ≤ m ≤ n). Различают упорядоченные выборки (размещения), перестановки и неупорядоченные выборки (сочетания).

Размещения

Размещениями n различных элементов по m элементов, которые отличаются либо составом элементов, либо их порядком.

Число размещений из n элементов по m элементов обозначают (А – первая буква французского слова arrangement, что означает размещение, приведение в порядок) и вычисляют по формуле:

Понятие факториала

Произведение n натуральных чисел от 1 до n обозначается символом n ! (n факториал), то есть

Например, 2!=

5!=

Заметим, что удобно рассчитывать 0!, полагая по определению, 0!=1.

Примеры:

Из последних двух формул следует, что

Пример.

В однокруговом турнире по футболу участвуют 8 команд. Сколько существует вариантов призовой тройки?

Решение : Так как порядок команд в призовой тройке важен, то мы имеем дело с размещениями. Тогда

(вариантов).

Пример.

Сколькими способами можно выбрать три лица на три различные должности из десяти кандидатов?

Решение:

(способов).

Пример.

Сколько можно составить телефонных номеров из 5 цифр так, чтобы в каждом отдельно взятом номере все цифры были различными?

(телефонных номеров).

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

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

Число всех возможных перестановок из n элементов обозначают P n (P – первая буква французского слова permutation, что означает перестановка) и вычисляют по формуле:

Пример.

В финальном забеге на 100 метров участвуют 8 спортсменов. Сколько существует вариантов протокола забега?

Решение:

В данном случае речь идёт обо всех перестановках из 8 элементов. Тогда (вариантов)

Пример.

Сколькими различными способами могут разместиться на скамейке10 человек?

Решение:

(способов)

Пример.

Сколькими способами можно разместить 7 лиц за столом, на котором поставлено 7 столовых приборов?

Решение:

(способов).

Сочетания

Сочетаниями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются хотя бы одним элементом.

Число сочетаний вычисляют по формуле: (С — первая буква французского слова combinasion).

Пример.

Сколькими способами можно выбрать три лица на три одинаковые должности из десяти кандидатов?

Решение :

(способов).

Пример.

Сколькими способами можно выбрать три детали из ящика, содержащего 15 деталей?

Решение:

(способов).

Другой вид формул числа размещений и числа сочетаний

; , то есть .

Свойства числа сочетаний:

5)

При решении задач комбинаторики используют следующие правила:

Правило суммы. Если некоторый объект А может быть выбран из совокупности объектов n способами, а другой объект В – k способами, то объект «либо А, либо В» можно выбрать n+k способами.

Правило произведения. Если некоторый объект А может быть выбран из совокупности объектов n способами и после каждого такого выбора другой объект В – k способами, то пара объектов (А, В) в указанном порядке может быть выбрана n×k способами.

Если некоторые элементы повторяются, то в этом случае комбинации с повторениями вычисляют по другим формулам.

Размещения с повторениями

Число размещений по m элементов с повторениями из n различных элементов равно n m ,то есть

Пример.

Из цифр 1,2,3,4,5 можно составить 5 3 =125 трехзначных чисел, если в одном и том же числе могут попадаться и одинаковые цифры.

Перестановки с повторениями

Если среди n элементов есть n 1 элементов одного вида, n 2 элементов другого вида и т.д., то число перестановок с повторениями

где

Пример.

Сколько различных перестановок букв можно сделать в слове «математика»?

Решение:

Сочетания с повторениями

Число сочетаний с повторениями из n различных элементов по m элементов равно числу сочетаний без повторений из (n +m -1) различных элементов по m элементов:

Пример.

Найти число сочетаний с повторениями из четырех элементов a , b , c , d по 3 элемента.

Решение:

Искомое число будет

Бином Ньютона

Для произвольного положительного целого числа n справедлива следующая формула:

Это бином Ньютона. Коэффициенты называются биномиальными коэффициентами.

При n = 2 получим формулу ;

При n = 3 получим формулу .

Пример. Определить разложение при n=4.

Решение:

Биномиальные коэффициенты обладают рядом свойств:

2. ;

Рассмотрим следующий треугольник:

………………………….

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

……………………….

Это треугольник Паскаля. Он позволяет быстро найти значения биномиальных коэффициентов.

В русскоязычной литературе перестановки, составленные из n различных элементов выбором по m элементов, которые отличаются либо составом элементов, либо их порядком, обычно называют размещениями, а под перестановками понимают всю совокупность комбинаций, состоящих из одних и тех же n различных элементов и отличающихся только порядком их расположения. В этом смысле число всех возможных перестановок для множества из n различных элементов считается по формуле факториала Pn = n! или в Excel «=ФАКТР(N)» (см. рис. № 1)

Например, если ввести «=ПЕРЕСТ(3;2)», получим 6. Это 6 комбинации: (1,2), (2,1), (1,3), (3,1), (2,3), (3,2).

А вот встроенная функция «=ЧИСЛКОМБ(N;K)» выдает комбинаторную формулу, называемую у нас «Число сочетаний». В русскоязычной литературе так именуют перестановки, составленные из n различных элементов выбором по m элементов, которые отличаются только составом элементов, а порядок их выбора безразличен (см. рис, №4)

При использовании встроенных функций пользуйтесь «Справкой по этой функции». Например:

Задачи для самостоятельного решения

1. Вычислить:

2. Вычислить:

3. Вычислить:

4. Найти n , если 5С n 3 =

5. Найти n , если

6. Найти n , если

7. Найти n , если

8. Найти n , если , k n

9. Решить уравнение

10. Решить систему

11. Сколько можно составить сигналов из 6 флажков различного цвета, взятых по 2?

12. Сколькими способами можно выбрать четыре лица на четыре различные должности из девяти кандидатов?

13. Сколько можно составить телефонных номеров из 6 цифр так, чтобы в каждом отдельно взятом номере все цифры были различны?

14. В классе 10 учебных предметов и 5 разных уроков в день. Сколькими способами могут быть распределены уроки в один день?

15. Сколько можно записать четырёхзначных чисел, используя без повторения все 10 цифр?

16. Фирма производит выбор из девяти кандидатов на три различные должности. Сколько существует способов такого выбора?

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

18. В высшей лиге чемпионата страны по футболу 16 команд. Борьба идет за золотые, серебряные и бронзовые медали. Сколькими способами медали могут быть распределены между командами?

19. Сколькими способами можно разместить 9 лиц за столом, на котором поставлено 9 приборов?

20. На собрании выступят 6 ораторов. Сколькими способами их фамилии можно расположить в списке?

21. Сколько трехзначных чисел можно составить из цифр 1, 2, 3, если каждая цифра входит в изображение числа только один раз?

22. Сколькими различными способами можно расставить 10 различных книг на полке, чтобы определённые 4 книги стояли рядом?

23. В однокруговом турнире по футболу участвуют 8 команд. Сколько всего матчей будет сыграно?

24. Из 25 студентов нужно выбрать трех делегатов на конференцию. Сколькими способами это можно сделать?

25. Сколькими способами можно выбрать две детали из ящика, содержащего 10 деталей?

26. В колоде 36 карт, из них 4 туза. Сколькими способами можно извлечь 6 карт так, чтобы среди них было 2 туза?

27. Комплексная бригада состоит из двух маляров, трёх штукатуров и одного столяра. Сколько различных бригад можно создать из рабочего коллектива, в котором 15 маляров, 10 штукатуров и 5 столяров?

28. В отборочном турнире за 3 путёвки на чемпионат мира участвуют 10 команд. Сколько существует вариантов «счастливой тройки»?

29. Из 12 человек выбирают четверых для назначения на 4 одинаковые должности. Сколькими способами можно сделать такой выбор?

30. Сколькими различными способами можно составить разведывательную группу из 3-х солдат и одного командира, если имеется 12 солдат и 3 командира?

31. На плоскости дано n точек, из которых никакие три не лежат на одной прямой. Найти число прямых, которые можно получить, соединяя точки попарно.

32. Буквы азбуки Морзе образуются как последовательность точек и тире. Сколько различных букв можно образовать, если использовать 5 символов?

33. Сколько существует различных семизначных телефонных номеров?

34. Пусть буквы некоторой азбуки образуются как последовательность точек, тире и пробелов. Сколько различных букв можно образовать, если использовать 5 символов?

35. При игре в бридж между четырьмя игроками распределяется колода карт в 52 листа по 13 карт каждому игроку. Сколько существует различных способов раздать карты?

36. В почтовом отделении продаются открытки пяти видов. Определить число способов покупки семи открыток.

37. Два коллекционера обмениваются марками. Найти число способов обмена, если первый коллекционер обменивает 3 марки, а второй – 6 марок. (Обмен происходит по одной марке).

38. У одного студента 6 книг по математике, а у другого – 5. Сколькими способами они могут обменять 2 книги одного на 2 книги другого?

39. Сколько различных перестановок букв можно сделать в словах: «замок», «ротор», «обороноспособность», «колокол», «семинар»?

40. Сколькими различными способами можно разместить в 9 клетках следующие 9 букв: а, а, а, б, б, б, в, в, в?

41. В автомашине 6 мест. Сколькими способами 6 человек могут сесть в эту машину, если занять место водителя могут только двое из них?

42. Сколькими способами из колоды в 52 карты можно извлечь 6 карт, содержащих туза и короля одной масти?

43. Определить разложение при n=5.

44. Определить разложение при n=8.

45. Найти член разложения , не содержащий x (то есть содержащий x в нулевой степени).

46. Найти шестой член разложения , если биномиальный коэффициент третьего от конца члена равен 45.

47. В разложении коэффициент третьего члена на 44 больше коэффициента второго члена. Найти свободный член, то есть член разложения, не зависящий от x (членом, не зависящим от x, будет тот, который содержит x в нулевой степени).

48. В разложении бинома найти члены, не содержащие иррациональности.

49. Найти номер того члена разложения , который содержит a и b в одинаковых степенях.

Практическое занятие №2

(интерактивное занятие в малых группах)

Булевы функции

Цель занятия: уметь строить различные булевы функции, проверять эквивалентность булевых формул (используя таблицу истинности), определять существенные и фиктивные переменные.

План занятия:

1. Основные операции

2. Булевы функции от n переменных

3. Основные эквивалентности

Чтобы в материале было легче ориентироваться, добавлю содержание данной темы:

Введение. Множества и выборки.

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

Для работы нам понадобятся кое-какие вспомогательные сведения. Начнём с такого фундаментального математического понятия как множество. Подробно понятие множества было раскрыто в теме «Понятие множества. Способы задания множеств» .

Очень краткий рассказ про множества : показать\скрыть

Если вкратце: множеством именуют некую совокупность объектов. Записывают множества в фигурных скобках. Порядок записи элементов роли не играет; повторения элементов не допускаются. Например, множество цифр числа 11115555999 будет таким: $\{1,5,9 \}$. Множество согласных букв в слове «тигрёнок» таково: $\{т, г, р, н, к\}$. Запись $5\in A$ означает, что элемент 5 принадлежит множеству $A=\{1,5,9 \}$. Количество элементов в конечном множестве называют мощностью этого множества и обозначают $|A|$. Например, для множества $A=\{1,5,9 \}$, содержащего 3 элемента, имеем: $|A|=3$.

Рассмотрим некое непустое конечное множество $U$, мощность которого равна $n$, $|U|=n$ (т.е. в множестве $U$ имеется $n$ элементов). Введём такое понятие, как выборка (некоторые авторы именуют её кортежем). Под выборкой объема $k$ из $n$ элементов (сокращённо $(n,k)$-выборкой) будем понимать набор элементов $(a_1, a_2,\ldots, a_k)$, где $a_i\in U$. Выборка называется упорядоченной, если в ней задан порядок следования элементов. Две упорядоченные выборки, различающиеся лишь порядком элементов, являются различными. Если порядок следования элементов выборки не является существенным, то выборку именуют неупорядоченной.

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

Для примера рассмотрим множество $U=\{a,b,c,d,e\}$. Множество $U$ содержит 5 элементов, т.е. $|U|=5$. Выборка без повторений может быть такой: $(a,b,c)$. Данная выборка содержит 3 элемента, т.е. объём этой выборки равен 3. Иными словами, это $(5,3)$-выборка.

Выборка с повторениями может быть такой: $(a,a,a,a,a,c,c,d)$. Она содержит 8 элементов, т.е. объём её равен 8. Иными словами, это $(5,8)$-выборка.

Рассмотрим ещё две $(5,3)$-выборки: $(a,b,b)$ и $(b,a,b)$. Если мы полагаем наши выборки неупорядоченными, то выборка $(a,b,b)$ равна выборке $(b,a,b)$, т.е. $(a,b,b)=(b,a,b)$. Если мы полагаем наши выборки упорядоченными, то $(a,b,b)\neq(b,a,b)$.

Рассмотрим ещё один пример, немного менее абстрактный:) Предположим, в корзине лежат шесть конфет, причём все они различны. Если первой конфете поставить в соответствие цифру 1, второй конфете — цифру 2 и так далее, то с конфетами в корзине можно сопоставить такое множество: $U=\{1,2,3,4,5,6\}$. Представьте, что мы наугад запускаем руку в корзинку с целью вытащить три конфеты. Вытащенные конфеты — это и есть выборка. Так как мы вытаскиваем 3 конфеты из 6, то получаем (6,3)-выборку. Порядок расположения конфет в ладони совершенно несущественен, поэтому эта выборка является неупорядоченной. Ну, и так как все конфеты различны, то выборка без повторений. Итак, в данной ситуации говорим о неупорядоченной (6,3)-выборке без повторений.

Теперь подойдём с иной стороны. Представим себе, что мы находимся на фабрике по производству конфет, и на этой фабрике производятся конфеты четырёх сортов. Множество $U$ в этой ситуации таково: $U=\{1,2,3,4 \}$ (каждая цифра отвечает за свой сорт конфет). Теперь вообразим, что все конфеты ссыпаются в единый жёлоб, около которого мы и стоим. И, подставив ладони, из этого потока отбираем 20 конфет. Конфеты в горсти – это и есть выборка. Играет ли роль порядок расположения конфет в горсти? Естественно, нет, поэтому выборка неупорядоченная. Всего 4 сорта конфет, а мы отбираем двадцать штук из общего потока — повторения сортов неизбежны. При этом выборки могут быть самыми различными: у нас даже могут оказаться все конфеты одного сорта. Следовательно, в этой ситуации мы имеем дело с неупорядоченной (4,20)-выборкой с повторениями.

Рассмотрим ещё пару примеров. Пусть на кубиках написаны различные 7 букв: к, о, н, ф, е, т, а. Эти буквы образуют множество $U=\{к,о,н,ф,е,т,а\}$. Допустим, из данных кубиков мы хотим составить «слова» из 5 букв. Буквы этих слов (к примеру, «конфе», «тенко» и так далее) образуют (7,5)-выборки: $(к,о,н,ф,е)$, $(т,е,н,к,о)$ и т.д. Очевидно, что порядок следования букв в такой выборке важен. Например, слова «нокфт» и «кфтон» различны (хотя состоят из одних и тех же букв), ибо в них не совпадает порядок букв. Повторений букв в таких «словах» нет, ибо в наличии только семь кубиков. Итак, набор букв каждого слова представляет собой упорядоченную (7,5)-выборку без повторений.

Еще один пример: мы составляем всевозможные восьмизначные числа из четырёх цифр 1, 5, 7, 8. Например, 11111111, 15518877, 88881111 и так далее.{k}=\frac{n!}{(n-k)!} \end{equation}

Что обозначает знак «!»? : показать\скрыть

Запись «n!» (читается «эн факториал») обозначает произведение всех чисел от 1 до n, т.е.

$$ n!=1\cdot2\cdot 3\cdot \ldots\cdot n $$

По определению полагается, что $0!=1!=1$. Для примера найдём 5!:

$$ 5!=1\cdot 2\cdot 3\cdot 4\cdot 5=120. $$

Пример №1

Алфавит состоит из множества символов $E=\{+,*,0,1,f\}$. Определим количество таких трёхсимвольных слов в этом алфавите, которые не содержат повторяющихся букв.

Под трёхсимвольными словами будем понимать выражения вида «+*0» или «0f1». В множестве $E$ пять элементов, поэтому буквы трехсимвольных слов образуют (5,3)-выборки. Первый вопрос: эти выборки упорядочены или нет? Слова, которые отличаются лишь порядком букв, полагаются различными, поэтому порядок элементов в выборке важен. Значит, выборка является упорядоченной. Второй вопрос: допускаются повторения или нет? Ответ на этот вопрос даёт условие: слова не должны содержать повторяющихся букв.{n}=\frac{n!}{(n-n)!}=\frac{n!}{0!}=\frac{n!}{1}=n! $$

Пример №3

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

Пусть первому мороженому соответствует цифра 1, второму — цифра 2 и так далее. Мы получим множество $U=\{1,2,3,4,5\}$, которое будет представлять содержимое морозилки. Порядок съедения может быть таким: $(2,1,3,5,4)$ или таким: $(5,4,3,1,2)$. Каждый подобный набор есть (5,5)-выборка. Она будет упорядоченной и без повторений. Иными словами, каждая такая выборка есть перестановка из 5 элементов исходного множества. Согласно формуле (3) общее количество этих перестановок таково:

$$ P_5=5!=120. $$

Следовательно, существует 120 порядков выбора очередности съедения.

Ответ : 120.

Перестановки с повторениями

Перестановка с повторениями – упорядоченная $(n,k)$-выборка с повторениями, в которой элемент $a_1$ повторяется $k_1$ раз, $a_2$ повторяется $k_2$ раза так далее, до последнего элемента $a_r$, который повторяется $k_r$ раз. При этом $k_1+k_2+\ldots+k_r=k$.

Общее количество перестановок с повторениями определяется формулой:

\begin{equation}P_{k}(k_1,k_2,\ldots,k_r)=\frac{k!}{k_1!\cdot k_2!\cdot \ldots \cdot k_r!} \end{equation}

Пример №4

Слова составляются на основе алфавита $U=\{a,b,d\}$. Сколько различных слов из семи символов может быть составлено, если в этих словах буква «a» должна повторяться 2 раза; буква «b» — 1 раз, а буква «d» — 4 раза?

Вот примеры искомых слов: «aabdddd», «daddabd» и так далее. Буквы каждого слова образуют (3,7)-выборку с повторениями: $(a,a,b,d,d,d,d)$, $(d,a,d,d,a,b,d)$ и т.д. Каждая такая выборка состоит из двух элементов «a», одного элемента «b» и четырёх элементов «d». Иными словами, $k_1=2$, $k_2=1$, $k_3=4$. Общее количество повторений всех символов, естественно, равно объёму выборки, т.е. $k=k_1+k_2+k_3=7$. Подставляя эти данные в формулу (4), будем иметь:

$$ P_7(2,1,4)=\frac{7!}{2!\cdot 1!\cdot 4!}=105. $$

Следовательно, общее количество искомых слов равно 105.{k}=\frac{n!}{(n-k)!\cdot k!} \end{equation}

Пример №5

В корзине размещены карточки, на которых написаны целые числа от 1 до 10. Из корзины вынимают 4 карточки и суммируют числа, написанные на них. Сколько различных наборов карточек можно вытащить из корзины?

Итак, в данной задаче исходное множество таково: $U=\{1,2,3,4,5,6,7,8,9,10\}$. Из этого множества мы выбираем четыре элемента (т.е., четыре карточки из корзины). Номера вытащенных элементов образуют (10,4)-выборку. Повторения в этой выборке не допускаются, так как номера всех карточек различны. Вопрос вот в чём: порядок выбора карточек играет роль или нет? Т.е., к примеру, равны ли выборки $(1,2,7,10)$ и $(10,2,1,7)$ или не равны? Тут нужно обратиться к условию задачи. Карточки вынимаются для того, чтобы потом найти сумму элементов. А это значит, что порядок карточек не важен, так как от перемены мест слагаемых сумма не изменится. Например, выборке $(1,2,7,10)$ и выборке $(10,2,1,7)$ будет соответствовать одно и то же число $1+2+7+10=10+2+1+7=20$.{k}=\frac{(n+k-1)!}{(n-1)!\cdot k!} \end{equation}

Пример №6

Представьте себе, что мы находимся на конфетном заводе, — прямо возле конвейера, по которому движутся конфеты четырёх сортов. Мы запускаем руки в этот поток и вытаскиваем двадцать штук. Сколько всего различных «конфетных комбинаций» может оказаться в горсти?

Если принять, что первому сорту соответствует число 1, второму сорту — число 2 и так далее, то исходное множество в нашей задаче таково: $U=\{1,2,3,4\}$. Из этого множества мы выбираем 20 элементов (т.е., те самые 20 конфет с конвейера). Пригоршня конфет образует (4,20)-выборку. Естественно, повторения сортов будут. Вопрос в том, играет роль порядок расположения элементов в выборке или нет? Из условия задачи следует, что порядок расположения элементов роли не играет. Нам нет разницы, будут ли в горсти располагаться сначала 15 леденцов, а потом 4 шоколадных конфеты, или сначала 4 шоколадных конфеты, а уж потом 15 леденцов. Итак, мы имеем дело с неупорядоченной (4,20) выборкой с повторениями.{20}=\frac{(4+20-1)!}{(4-1)!\cdot 20!}=\frac{23!}{3!\cdot 20!}=1771. $$

Следовательно, общее количество искомых комбинаций равно 1771.

Тематические материалы:

Обновлено: 30.09.2019

103583

Если заметили ошибку, выделите фрагмент текста и нажмите Ctrl+Enter

Презентация «Основы комбинаторики. Размещения, перестановки, сочетания» 11 класс

Основы комбинаторики.

Размещения, перестановки,

сочетания.

Проказница Мартышка

Осёл,

Козёл,

Да косолапый Мишка

Затеяли играть квартет

…

Стой, братцы стой! –

Кричит Мартышка, — погодите!

Как музыке идти?

Ведь вы не так сидите…

И так, и этак пересаживались – опять музыка на лад не идет.

Вот пуще прежнего пошли у них разборы

И споры,

Кому и как сидеть…

знать:

• определения трех важнейших понятий комбинаторики:
• размещения из n элементов по m;
• сочетания из n элементов по m;
• перестановки из n элементов;
• основные комбинаторные формулы

уметь:

• отличать задачи на «перестановки», «сочетания», «размещения» друг от друга;
• применять основные комбинаторные формулы при решении простейших комбинаторных задач.

множество

Множество характеризуется объединением некоторых однородных объектов в одно целое.

Объекты, образующие множество, называются элементами множества.

Множество будем записывать, располагая его элементы в фигурных скобка {a, b, c, … , e, f}.

Во множестве порядок элементов роли не играет, так {a, b} = {b, a}.

Множество, не содержащее ни одного элемента, называется пустым множеством и обозначается символом ø.

множество

Если каждый элемент множества А является элементом множества В, то говорят, что множество А является подмножеством множества В.

В

А

Множество {a, b} является подмножеством множества {a, b, c, … , e, f}.

Обозначается

Пример:

Задача

Перечислите возможные варианты подмножества множества {3, 4, 5, 7, 9}.

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

Комбинаторика является важным разделом математики, который исследует закономерности расположения, упорядочения, выбора и распределения элементов с фиксированного множества.

ПРАВИЛО СУММИРОВАНИЯ

Если два взаимоисключающие действия могут быть выполнены в соответствии  k и m способами, тогда какое-то одно из этих действий можно выполнить  k + m способами.

Пример №1

Из города А в город В можно добраться 12 поездами, 3 самолетами, 23 автобусами. Сколькими способами можно добраться из города А в город В?

Решение

N=12+13+23=38

Пример № 2

В ящике имеется n разноцветных шариков. Произвольным образом вынимаем один шарик. Сколькими способами это можно сделать?

Решение. Конечно, n способами.

Теперь эти n шариков распределены по двум ящикам: В первом m шариков, во втором k. Произвольно из какого-нибудь ящика вынимаем один шарик. Сколькими разными способами это можно сделать?

Решение. 

Из первого ящика шарик можно вытянуть m различными способами, из второго k различными способами, всего  N = m + k способами.

ПРАВИЛО ПРОИЗВЕДЕНИЯ

Пусть две выполняемые одно за другим действия могут быть осуществлены в соответствии   k и m способами Тогда обе они могут быть выполнены  k ∙ m способами.

Пример № 3

 В турнире принимают участие 8 хоккейных команд. Сколько существует способов распределить первое, второе и третье места?

Решение

N=8∙7∙6=336

Пример № 4

Сколько можно записать двузначных чисел в десятичной системе счисления?

Решение. Поскольку число двузначное, то число десятков (m) может принимать одно из девяти значений: 1,2,3,4,5,6,7,8,9. Число единиц (k) может принимать те же значения и может, кроме того быть равным нулю. Отсюда следует, что m = 9, а k= 10. Всего получим двузначных чисел 

N = m ·k = 9·10 =90.

Пример № 5

В студенческой группе 14 девушек и 6 юношей. Сколькими способами можно выбрать, для выполнения различных заданий, двух студентов одного пола?

Решение. По правилу умножения двух девушек можно выбрать 14 ·13 = 182 способами, а двух юношей 6·5 = 30 способами. Следует выбрать двух студентов одного пола: двух студентов или студенток. Согласно правилу сложения таких способов выбора будет

N =182 + 30 = 212.

Типы соединений

Множества элементов называются соединениями.

Различают три типа соединений:

• перестановки из n элементов;
• размещения из n элементов по m;
• сочетания из n элементов по m (m < n).

Определение: Перестановкой из n элементов называется любое упорядоченное множество из n элементов.

Иными словами, это такое множество, для которого указано, какой элемент находится на первом месте, какой – на втором, какой- на третьем, …, какой – на n-м месте.

ПЕРЕСТАНОВКИ

Перестановки – это такие соединения по n элементам из данных элементов, которые отличаются одно от другого порядком элементов.

Число перестановок из n элементов обозначают Рn.

Рn = n · (n — 1) · (n – 2) · … · 2 · 1 = n!

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

Пусть n — натуральное число. Через n! (читается «эн факториал») обозначается число, равное произведению всех натуральных чисел 1 от до n:

n! = 1 · 2 · 3 · … · n.

В случае, если n = 0, по определению полагается: 0! = 1.

ФАКТОРИАЛ

Пример № 6

Найдем значения следующих выражений: 1! 2! 3!

7!

Пример № 7

Чему равно

а)Р5 ;

б) Р3.

Пример № 8

Упростите

а) 7! · 8

б) 12! · 13 ·14

в) κ! · (κ + 1)

Пример № 9

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

Решение. 

n =8

Р8=8! = 8·7·6·5 · 4 · 3 · 2 ·1 =40320

РАЗМЕЩЕНИЯ

Определение. Размещением из n элементов по m называется любое упорядоченное множество из m элементов, состоящее из элементов n элементного множества.

Число размещений из m  элементов по n обозначают: 

вычисляют по формуле:

Пример № 9

Учащиеся 11-го класса изучают 9 учебных предметов. В расписании учебных занятий на один день можно поставить 4 различных предмета. Сколько существует различных способов составления расписания на один день?

Решение. 

Имеем 9-элементное множество, элементы которого учебные предметы. При составлении расписания мы будем выбирать 4-элементное подмножество (уроков) и устанавливать в нем порядок. Число таких способов равно числу размещений из девяти по четыре (m=9, n=4) то есть A94:

Пример № 10

Сколькими способами из класса, где учатся 24 ученика, можно выбрать старосту и помощника старосты?

Решение. 

Имеем 24-элементное множество, элементы которого ученики класса. При выборах старосты и помощника старосты мы будем выбирать 2-элементное подмножество (ученика) и устанавливать в нем порядок. Число таких способов равно числу размещений из девяти по четыре(m=24, n=2), то есть A242:

СОЧЕТАНИЯ

Определение. Сочетанием без повторений из n элементов по m -называется любое m элементное подмножество n -элементного множества

Число сочетаний из n элементов по m обозначают 

и вычисляют по формуле:

Пример № 11

Сколькими способами из класса, где учатся 24 ученика, можно выбрать два дежурных ?

Решение. 

n =24, m=2

Учитывается ли порядок следования элементов в соединении?

Д А

НЕТ

Все ли элементы входят в соединение?

СОЧЕТАНИЯ

РАЗМЕЩЕНИЯ

ПЕРЕСТАНОВКИ

Рn =  n!

Д А

НЕТ

Определить к какому типу относится соединений относится задача.

1. Сколькими способами можно составить расписание одного учебного дня из 5 различных уроков?

2. В 9«Б» классе 12 учащихся. Сколькими способами можно сформировать команду из 4 человек для участия в математической олимпиаде?

Учитывается ли порядок следования элементов в соединении?

( да)

Все ли элементы входят в соединение?

( да)

Вывод: перестановка

Учитывается ли порядок следования элементов в соединении?

Все ли элементы входят в соединение?

(нет)

(на этот вопрос ответ не нужен)

Вывод: сочетания

3.Сколько существует различных двузначных чисел, в записи которых можно использовать цифры 1, 2, 3, 4, 5, 6, если цифры в числе должны быть различными?

Учитывается ли порядок следования элементов в соединении?

Все ли элементы входят в соединение?

(нет)

( да)

Вывод: размещение

Проказница Мартышка

Осёл,

Козёл,

Да косолапый Мишка

Затеяли играть квартет

…

Стой, братцы стой! –

Кричит Мартышка, — погодите!

Как музыке идти?

Ведь вы не так сидите…

И так, и этак пересаживались – опять музыка на лад не идет.

Вот пуще прежнего пошли у них разборы

И споры,

Кому и как сидеть…

Сколько различных вариантов расположения музыкантов возможно?

Решение. 

Учитывается ли порядок следования элементов в соединении?

( да)

Все ли элементы входят в соединение?

(да)

Вывод: перестановка

Рn =  n! =n · (n — 1) · (n – 2) · … · 2 · 1

n =4

Р4 =  4! = 4 · 3 · 2 ·1=24

«Рано или поздно всякая правильная математическая идея находит применение в том или ином деле»?

Кто автор высказывания?

Е

Е

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

К

размещение

Л

сочетание

Е

А

С

Й

Н

И

О

Ы

Р

Ч

В

М

12

21

120

56

132

720

6720

5040

9

1

Результаты решения задач

А

Л

Е

К

С

Е

Й

Н

К

И

О

В

Л

А

Е

Л

О

Ч

И

В

Ы

Р

К

ДОМАШНЕЕ ЗАДАНИЕ

Выучить конспект и формулы.

С. 321 № 1062

С. 325 №1074,1075

С. 329 №1081

комбинаций и перестановок (предалгебра, вероятность и статистика) — Mathplanet

Прежде чем мы обсудим перестановки, мы собираемся взглянуть на то, что означает сочетание слов и перестановка. Вальдорфский салат — это смесь сельдерея, грецких орехов и салата. Неважно, в каком порядке мы добавляем наши ингредиенты, но если у нас есть комбинация для нашего замка, которая составляет 4-5-6, то порядок чрезвычайно важен.

Если порядок не имеет значения, то у нас есть комбинация, если порядок имеет значение, то у нас есть перестановка.Можно сказать, что перестановка — это упорядоченная комбинация.

Число перестановок n объектов, взятых r за раз, определяется по следующей формуле:

$$ P (n, r) = \ frac {n!} {(N-r)!} $$

н! читается n факториал и означает, что все числа от 1 до n умножаются, например

$$ 5! = 5 \ cdot 4 \ cdot 3 \ cdot 2 \ cdot 1 $$

Читается пятифакториал. 0! Определяется как 1.

$$ 0! = 1 $$

Пример

Код состоит из 4 цифр в определенном порядке, цифры от 0 до 9.Сколько существует различных перестановок, если одну цифру можно использовать только один раз?

Четырехзначный код может быть любым в диапазоне от 0000 до 9999, следовательно, существует 10000 комбинаций, если каждая цифра может использоваться более одного раза, но поскольку в вопросе нам сказано, что можно использовать только одну цифру, если она ограничивает наше количество комбинаций . Чтобы определить правильное количество перестановок, мы просто подставляем наши значения в нашу формулу:

$$ P (n, r) = \ frac {10!} {(10-4)!} = \ Frac {10 \ cdot9 \ cdot8 \ cdot 7 \ cdot 6 \ cdot 5 \ cdot 4 \ cdot 3 \ cdot 2 \ cdot 1} {6 \ cdot5 \ cdot 4 \ cdot 3 \ cdot 2 \ cdot 1} = 5040 $$

В нашем примере порядок цифр был важен, если бы порядок не имел значения, у нас было бы определение комбинации.Количество комбинаций из n объектов, взятых r за раз, определяется по следующей формуле:

$$ C (n, r) = \ frac {n!} {(N-r)! R!} $$

Решить

Калькулятор перестановок и комбинаций

Результат

Перестановки и комбинации являются частью раздела математики, называемого комбинаторикой, который включает изучение конечных дискретных структур.Перестановки — это особый выбор элементов в наборе, где важен порядок, в котором элементы расположены, в то время как комбинации включают выбор элементов без учета порядка. Например, типичный кодовый замок с технической точки зрения следует называть замком с перестановкой по математическим стандартам, поскольку важен порядок вводимых чисел; 1-2-9 — это не то же самое, что 2-9-1, тогда как для комбинации будет достаточно любого порядка этих трех чисел. Существуют различные типы перестановок и комбинаций, но калькулятор выше учитывает только случай без замены, также называемый без повторения.Это означает, что для приведенного выше примера кодового замка этот калькулятор не вычисляет случай, когда кодовый замок может иметь повторяющиеся значения, например 3-3-3.

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

Предоставленный калькулятор вычисляет одну из наиболее типичных концепций перестановок, где расположения фиксированного числа элементов r берутся из заданного набора n . По сути, это можно назвать r-перестановками n или частичными перестановками , обозначенными как _n P _r , ⁿ P _r , P _{(n, r)} , или P (n, r) среди других.В случае перестановок без замены рассматриваются все возможные способы, которыми элементы в наборе могут быть перечислены в определенном порядке, но количество вариантов уменьшается каждый раз, когда выбирается элемент, а не такой случай, как «комбинационная» блокировка. , где значение может встречаться несколько раз, например 3-3-3. Например, при попытке определить количество способов, которыми капитан команды и вратарь футбольной команды могут быть выбраны из команды, состоящей из 11 человек, капитан команды и вратарь не могут быть одним и тем же человеком, и после выбора они должны быть снят с набора.Буквы с A по K будут обозначать 11 различных членов команды:

A B C D E F G H I J K 11 членов; А выбран капитаном

B C D E F G H I J K 10 членов; B выбран хранителем

Как можно видеть, первым был выбран A в качестве капитана из 11 начальных членов, но поскольку A не может быть капитаном команды, а также вратарём, A был удален из набора до второй выбор вратаря B мог быть сделан.Полные возможности, если бы каждый член команды был задан, были бы 11 × 10 × 9 × 8 × 7 × … × 2 × 1, или 11 факториалов, записанных как 11 !. Однако, поскольку в этом случае были важны только выбранные капитан команды и вратарь, релевантны только первые два варианта: 11 × 10 = 110. Таким образом, уравнение для вычисления перестановок удаляет остальные элементы, 9 × 8 × 7 × … × 2 × 1 или 9 !. Таким образом, обобщенное уравнение для перестановки можно записать как:

Или в данном случае конкретно:

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

_n P _r = n ^r

Комбинации

Комбинации связаны с перестановками в том смысле, что они по существу представляют собой перестановки, в которых все избыточности удаляются (как будет описано ниже), поскольку порядок в комбинации не важен.Комбинации, как и перестановки, обозначаются по-разному, включая _n C _r , ⁿ C _r , C _{(n, r)} или C (n, r ) , или чаще всего просто

Или в данном случае конкретно:

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

Узнайте о перестановках и комбинациях

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

Мы обсудим перестановки и комбинации. После того, как вы закончите этот урок, просмотрите все наши уроки Алгебры 1 и попрактикуйтесь.

В первом видео мы будем работать с перестановками.

У нас есть три машины: синяя, белая и зеленая.
У нас могут быть разные заказы:
B W G,
B G W,
W B G,
W G B,
G B W и
G W B
, что в сумме дает 6 возможных вариантов заказа.

Другой способ взглянуть на это — подумать о машинах по порядку:

• Во-первых, может быть три машины.
• Во-вторых, может быть только две машины, так как одна машина уже стоит на первом месте.
• На третьем месте может быть только одна машина, так как осталась только одна.

Умножив 3 на 2 на 1 , мы получим 6 . это тот же ответ, что и выше.

Мы можем просто использовать факториал: «! »для решения подобных вопросов.

для 4! выражение также можно записать как
от заданного числа до 1

Умножая числа вместе, получаем

Давайте поработаем на другом примере:
Если есть 5 машин, сколькими способами они могут финишировать на первых трех машинах?

В этой ситуации мы не можем напрямую использовать 5! , потому что мы не находим заказ на все пять автомобилей.
Вместо этого мы можем применить умножение до желаемого порядка, который мы называем перестановками. Мы используем перестановки в ситуациях, когда важны порядок и позиция.

₅ P ₃ =
₅ P ₃ =

На калькуляторе мы можем ввести первое число, нажать MATH / PRB nPr и ввести второе число. Ответ один и тот же в обеих ситуациях.

Примеры перестановок

Пример 1

Код состоит из цифр в определенном порядке, цифры находятся между ними.Сколько существует различных перестановок, если одну цифру можно использовать только один раз?

Поскольку в вопросе нам сказано, что можно использовать только одну цифру, если она ограничивает количество комбинаций.
Следовательно,
_{10 4} =

Пример 2

Сколько разных способов сделать шары для пула из шаров?
_{16 3} =

Стенограмма видеоурока

Давайте пройдемся по перестановкам.

Например, есть три машины.Синяя машина, белая машина и зеленая машина. Мы хотим увидеть, сколько разных способов мы можем разместить их в разном порядке.

У нас могут быть разные заказы, например:

Сине-белый-зеленый
Сине-зеленый-белый

Белый-Сине-Зеленый
Белый-Зеленый-Синий

Зелено-синий-белый
Зелено-белый-синий

Эти три машины можно разместить разными способами.

Еще один способ думать об этом — это первое, второе и третье места.

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

Но после того, как одна машина ставится на первое место, остается только две машины.

Затем после первых двух мест осталась только одна машина для третьего места.

Если мы умножим эти три, мы получим

Это то же самое, что и

Если у нас четыре машины, мы делаем четыре факториала

Если мы собираемся подсчитывать все места, мы могли бы использовать такую ​​вещь, как факториал.

Давайте посмотрим на этот пример.

В гонке участвуют автомобили: A, B, C, D и E.

а) Сколько они могут закончить,?

Поскольку мы собираемся считать все пять, мы будем использовать пять факториалов.

Если мы умножим их вместе:

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

Итак, есть способы, которыми эти пять машин могут финишировать.

б) Сколько они могут закончить,?

Здесь мы не можем сделать факториал, потому что у нас не будет последнего или пятого места.

Давайте просто напишем здесь четыре точки, которые представляют первое место, второе место, третье место и четвертое место.

Это также дало нам тот же ответ, что и первый, потому что последний несущественен.

Несущественно, потому что после четвертого места осталась только одна машина.Это не повлияет на количество результатов.

Теперь давайте посмотрим на

c) Сколько они могут закончить,?

Опять же, возьмем первое, второе и третье места.

г) Сколько они могут закончить,?

Посмотрим на первое и второе место.

д) Сколько они могут закончить?

Есть машины, так что все могут быть на первом месте.

Перестановки похожи на факториалы, за исключением того, что мы не заканчиваем все.

Если у нас разные числа и мы хотим четыре результата, мы начнем с общих чисел, которые у нас есть, а затем запишем количество точек, в которые мы собираемся подняться.

В письме б,

Это будет размножаться до пятен.

При решении буквы c у нас будет

Буква d решается как

И ответ на букву е —

Эти два взаимозаменяемые.

Теперь давайте посмотрим на фактическую перестановку.

Это означает, что мы начнем и умножим первые числа.

Мы не останавливаемся на цифре, мы останавливаемся на четвертой точке или цифре.

В калькуляторе мы можем просто ввести это.

Перейдите в раздел «Математика», затем «Вероятность», затем выберите nPr, которое означает число, перестановку и второе число.

Это дает нам тот же ответ.

Когда мы используем перестановку?

Мы используем перестановку, если порядок или позиция имеют значение.

Например, если у нас есть первое место, второе место, третье место и т. Д. С разным порядком, мы используем перестановку.

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

Допустим, в студенческий совет баллотируются студенты, которые занимают должности президента, вице-президента и казначея.

Мы можем использовать

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

Помните, что в перестановке важен определенный порядок или позиция.

Перестановки с повторяющимися элементами

Во втором видео мы будем работать с перестановками с повторяющимися элементами.

Слово КОЛЕНЬ состоит из трех отличительных букв, из которых буква Е повторяется дважды.

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

Примеры перестановок с повторяющимися элементами

Пример 1

КОЛЕНЬ

Пример 2

ТАТУ

Стенограмма видеоурока

У нас будет перестановка с повторением.

Например, слово ACT. Буквы A-C-T можно переупорядочивать по-разному.

ACT
ATC
CTA
CAT
TCA
TAC

Это

Теперь давайте посмотрим на слово TOO. Давайте реорганизуем этот

ТОО
TOO
OTO
OOT
OTO
OOT

Здесь нет большой разницы, так как здесь две буквы О.

Есть аранжировки, похожие на другие из-за той же буквы.

Итак, вы не можете просто выполнить факториал или перестановку.

Вместо этого мы должны сделать это:

Давайте посмотрим на другой пример, и в нем будет больше смысла.

Давайте переставим буквы в слове КОЛЕНЬ.

Давайте посмотрим на слово TATTOO

Давайте посмотрим на слово DIVIDEND

Если у вас есть повторяющиеся буквы или элементы, просто выполните перестановку, как если бы вы обычно делили
на факториал количества повторяющихся элементов.

Комбинации

В этом видео мы будем работать с комбинациями.

Комбинации: Количество заказов, в которых порядок не имеет значения.
Мы можем использовать формулу: _n C _r , чтобы найти комбинацию.

Для ₅ C ₃ =
У нас будет 5! сверху и 3! 2! внизу, что похоже на перестановки с повторяющимися элементами.

₅ С ₃ =

При необходимости уменьшить
₅ C ₃ =

Умножить на
₅ C ₃ =

А у нас
₅ C ₃ =

Примеры комбинаций

Пример 1

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

Джонс уже выбран, поэтому нам нужно выбрать другого из них.

При выборе комитета порядок не имеет значения; поэтому нам нужно количество комбинаций людей, выбранных из

₉ С ₄

Пример 2

Количество комбинаций шести объектов, взятых по два за раз.
₆ С ₂

Стенограмма видеоурока

Давайте рассмотрим комбинации.

Это способ узнать, сколько способов можно сделать, где порядок или место
не имеют значения.

Когда мы формируем комитет, или группу, или команду, или комбинацию и порядок не имеют значения, мы собираемся использовать эту формулу для решения:

Это может показаться сложным, но на самом деле не так уж и плохо.

Если у нас

Давайте посмотрим на другой пример:

Здесь также можно использовать калькулятор.

Вот пример.

В классе есть ученики.из них получат классные обязанности на неделю. Сколько групп можно сформировать?

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

В этом случае мы будем использовать комбинацию.

Это намного проще с помощью калькулятора.

Далее идет отбор учеников в офис класса — президента, вице-президента, секретаря, казначея и судьи.

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

В этом случае порядок имеет значение. Итак, мы будем использовать перестановку.

Между комбинацией и перестановкой существует явная разница.

Как рассчитать комбинации и перестановки

Предположим, у вас есть n типов элементов, и вы хотите выбрать набор из r. Нам могут понадобиться эти предметы в определенном порядке. Мы называем эти наборы элементов перестановками.Если порядок не имеет значения, мы называем набор коллекций комбинациями. Как для комбинаций, так и для перестановок вы можете рассмотреть случай, когда вы выбираете некоторые из n типов более одного раза, что называется «с повторением», или случай, когда вы выбираете каждый тип только один раз, что называется «без повторения». ‘. Цель состоит в том, чтобы иметь возможность подсчитать количество комбинаций или перестановок, возможных в данной ситуации.

Порядки и факториалы

Факториальная функция часто используется при вычислении комбинаций и перестановок.N! означает N × (N – 1) × … × 2 × 1. Например, 5! = 5 × 4 × 3 × 2 × 1 = 120. Количество способов упорядочить набор элементов является факториалом. Возьмите три буквы a, b и c. У вас есть три варианта выбора для первой буквы, два для второй и только один для третьей. Другими словами, всего 3 × 2 × 1 = 6 порядков. В общем, есть n! способов заказать n товаров.

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

Предположим, у вас есть три комнаты, которые вы собираетесь раскрасить, и каждая из них будет окрашена в один из пяти цветов: красный (r), зеленый (g), синий (b), желтый (y) или оранжевый. (о).р.

Перестановки без повторения

Теперь предположим, что каждая комната будет разного цвета. Вы можете выбрать один из пяти цветов для первой комнаты, четырех для второй и всего трех для третьей. Это дает 5 × 4 × 3 = 60, что просто равно 5! / 2 !. В общем, количество независимых способов выбрать r элементов в определенном порядке из n неповторяющихся вариантов равно n! / (N – r) !.

Комбинации без повторов

Затем забудьте о том, какая комната какого цвета.Просто выберите три независимых цвета для цветовой схемы. Порядок здесь не имеет значения, поэтому (красный, зеленый, синий) такой же, как (красный, синий, зеленый). На любой выбор из трех цветов есть 3! способы их заказа. Так вы уменьшите количество перестановок на 3! чтобы получить 5! / (2! × 3!) = 10. В общем, вы можете выбрать группу из r элементов в любом порядке из n неповторяющихся вариантов в n! / [(n – r)! × r! ] способов.

Комбинации с повторением

Наконец, вам нужно создать цветовую схему, в которой вы можете использовать любой цвет столько раз, сколько захотите.Умный бухгалтерский код помогает этой задаче подсчета. Используйте три крестика, чтобы обозначить комнаты. Ваш список цветов представлен как «rgbyo». Смешайте X в своем списке цветов и свяжите каждый X с первым цветом слева от него. Например, rgXXbyXo означает, что первая комната зеленая, вторая зеленая и третья желтая. X должен иметь по крайней мере один цвет слева, поэтому для первого X доступно пять слотов. Поскольку список теперь включает X, есть шесть доступных слотов для второго X и семь доступных слотов для третьего X.Всего 5 × 6 × 7 = 7! / 4! способы написания кода. Однако порядок комнат произвольный, поэтому на самом деле существует только 7! / (4! × 3!) Уникальных расположений. В общем, вы можете выбрать r элементов в любом порядке из n повторяемых вариантов (n + r – 1)! / [(N – 1)! × r!] Способами.

1.3: Комбинации и перестановки — математика LibreTexts

Расследуй!

У вас есть набор фишек пяти разных цветов: красный, синий, зеленый, фиолетовый и желтый.

1. Сколько разных стеков из двух фишек вы можете собрать, если нижняя фишка должна быть красной или синей? Объясните свой ответ, используя как аддитивный, так и мультипликативный принцип.
2. Сколько разных стеков из трех фишек вы можете составить, если нижняя фишка должна быть красной или синей, а верхняя фишка — зеленой, фиолетовой или желтой? Как эта проблема соотносится с предыдущей?
3. Сколько существует разных стеков из трех фишек, в которых не повторяется ни один цвет? А как насчет четырех фишек?
4. Предположим, вы хотите взять три фишки разного цвета и положить их в карман. Сколько у вас вариантов выбора? Что, если вам нужны четыре фишки разного цвета? Как эти проблемы соотносятся с предыдущей?

Перестановка — это (возможная) перестановка объектов.Например, есть 6 перестановок букв a, b, c :

Мы знаем, что у нас есть все они, перечисленные выше — есть 3 варианта выбора, какую букву мы помещаем первой, затем 2 варианта, для которой буква идет следующей, что оставляет только 1 вариант для последней буквы. Принцип мультипликативности гласит, что мы умножаем \ (3 \ cdot 2 \ cdot 1 \ text {.} \)

Пример \ (\ PageIndex {1} \)

Сколько существует перестановок букв a, b, c, d, e, f ?

Ответ

Мы НЕ хотим перечислять все это.Однако, если бы мы это сделали, нам нужно было бы сначала выбрать письмо, которое нужно записать. Есть 6 вариантов для этой буквы. Для каждого выбора первой буквы есть 5 вариантов для второй буквы (мы не можем повторить первую букву; мы переставляем буквы и получаем только по одной из каждой), и для каждого из них есть 4 варианта для третьей, 3 варианты выбора для четвертой буквы, 2 варианта для пятой и, наконец, только 1 вариант для последней буквы. Итак, есть \ (6 \ cdot 5 \ cdot 4 \ cdot 3 \ cdot 2 \ cdot 1 = 720 \) перестановки 6 букв.

Здесь может быть полезно обозначение: \ (n! \ Text {,} \) читать «\ (n \) факториал», является произведением всех положительных целых чисел, меньших или равных \ (n \) (по причинам для удобства мы также определяем 0! равным 1). Таким образом, количество перестановок из 6 букв, как показано в предыдущем примере, равно \ (6! = 6 \ cdot 5 \ cdot 4 \ cdot 3 \ cdot 2 \ cdot 1 \ text {.} \) Это обобщает:

Перестановки \ (n \) элементов

Есть \ (n! = N \ cdot (n-1) \ cdot (n-2) \ cdot \ cdots \ cdot 2 \ cdot 1 \) перестановки \ (n \) (различных) элементов.

Подсчет биективных функций

Сколько функций \ (f: \ {1,2, \ ldots, 8 \} \ to \ {1,2, \ ldots, 8 \} \) являются биективными ?

Раствор

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

\ begin {уравнение *} f = \ twoline {1 \ amp 2 \ amp 3 \ amp 4 \ amp 5 \ amp 6 \ amp 7 \ amp 8} {3 \ amp 1 \ amp 5 \ amp 8 \ amp 7 \ amp 6 \ amp 2 \ amp 4} \ end {уравнение *}

На самом деле мы просто переставляем элементы кодомена, поэтому мы создаем перестановку из 8 элементов.Фактически, «перестановка» — это еще один термин, используемый для описания биективных функций из конечного множества в себя.

Если вы в это верите, то вы видите, что ответ должен быть \ (8! = 8 \ cdot 7 \ cdot \ cdots \ cdot 1 = 40320 \ text {.} \). Это также видно напрямую: для каждого элемента домен, мы должны выбрать отдельный элемент кодомена для сопоставления. Есть 8 вариантов, куда отправить 1, затем 7 вариантов, куда отправить 2, и так далее. Мы умножаем по принципу мультипликативности.

Иногда мы не хотим переставлять все буквы / числа / элементы, которые нам даны.

Пример \ (\ PageIndex {3} \)

Сколько четырехбуквенных «слов» можно составить из букв от a до f , без повторяющихся букв?

Раствор

Это похоже на задачу перестановки 4 букв, только теперь у нас есть больше вариантов для каждой буквы. Для первой буквы есть 6 вариантов. Для каждой из них есть 5 вариантов для второй буквы. Затем есть 4 варианта для третьей буквы и 3 варианта для последней буквы.Общее количество слов равно \ (6 \ cdot 5 \ cdot 4 \ cdot 3 = 360 \ text {.} \) Это не \ (6! \), Потому что мы никогда не умножали на 2 и 1. Мы могли бы начать с \ (6! \), А затем отмените 2 и 1 и напишите \ (\ frac {6!} {2!} \ Text {.} \)

В общем, мы можем спросить, сколько существует перестановок \ (k \) объектов, выбирающих эти объекты из большей коллекции \ (n \) объектов. (В приведенном выше примере \ (k = 4 \ text {,} \) и \ (n = 6 \ text {.} \)) Мы пишем это число \ (P (n, k) \) и иногда называем его a \ (k \) — перестановка \ (n \) элементов .Из приведенного выше примера мы видим, что для вычисления \ (P (n, k) \) мы должны применить мультипликативный принцип к числам \ (k \), начиная с \ (n \) и считая в обратном порядке. Например

\ begin {уравнение *} P (10, 4) = 10 \ cdot 9 \ cdot 8 \ cdot 7. \ end {уравнение *}

Еще раз обратите внимание, что \ (P (10,4) \) вначале выглядит как \ (10! \ Text {,} \), но мы останавливаемся после 7. Мы можем формально учесть эту «остановку», разделив часть факториал, который нам не нужен:

\ begin {уравнение *} P (10,4) = \ frac {10 \ cdot 9 \ cdot 8 \ cdot 7 \ cdot 6 \ cdot 5 \ cdot 4 \ cdot 3 \ cdot 2 \ cdot 1} {6 \ cdot 5 \ cdot 4 \ cdot 3 \ cdot 2 \ cdot 1} = \ frac {10!} {6!}.\ end {уравнение *}

Внимание! Факториал в знаменателе равен не \ (4! \), А скорее \ ((10-4)! \ Text {.} \)

\ (k \) — перестановки \ (n \) элементов

\ (P (n, k) \) — количество \ (k \) — перестановок \ (n \) элементов, количество способов упорядочить \ (k \) объектов, выбранных из \ (n \) различных объекты.

\ begin {уравнение *} P (n, k) = \ frac {n!} {(N-k)!}. \ end {уравнение *}

Обратите внимание, что когда \ (n = k \ text {,} \) мы имеем \ (P (n, n) = \ frac {n!} {(Nn)!} = N! \) (Поскольку мы определили \ ( 0! \) Равным 1).Это имеет смысл — мы уже знаем, что \ (n! \) Дает количество перестановок всех \ (n \) объектов.

Счетные инъективные функции

Сколько функций \ (f: \ {1,2,3 \} \ to \ {1,2,3,4,5,6,7,8 \} \) являются инъективными ?

Раствор

Обратите внимание, что здесь нет смысла запрашивать количество биекций , так как их нет (поскольку кодомен больше, чем домен, сюръекций нет).Но для того, чтобы функция была инъективной, мы просто не можем использовать элемент кодомена более одного раза.

Нам нужно выбрать элемент из кодомена, который будет изображением 1. Есть 8 вариантов. Затем нам нужно выбрать один из оставшихся 7 элементов, который будет изображением 2. Наконец, один из оставшихся 6 элементов должен быть изображением 3. Таким образом, общее количество функций равно \ (8 \ cdot 7 \ cdot 6 = П (8,3) \ text {.} \)

В целом это демонстрирует, что количество инъекций \ (f: A \ to B \ text {,} \), где \ (\ card {A} = k \) и \ (\ card {B} = n \ текст {,} \) равен \ (P (n, k) \ text {.} \)

Вот еще один способ найти количество \ (k \) — перестановок элементов \ (n \): сначала выберите, какие элементы \ (k \) будут в перестановке, затем посчитайте, сколько способов их расположить . После того, как вы выбрали \ (k \) объекты, мы знаем, что есть \ (k! \) Способов их упорядочить (переставить). Но как выбрать \ (k \) объекты из \ (n \ text {?} \). У вас есть \ (n \) объектов, и вам нужно выбрать \ (k \) из них. Вы можете сделать это \ ({n \ выбрать k} \) способами.Затем для каждого выбора из этих \ (k \) элементов мы можем переставить из \ (k! \) Способами. Используя мультипликативный принцип, мы получаем другую формулу для \ (P (n, k) \ text {:} \)

Теперь, поскольку у нас уже есть замкнутая формула для \ (P (n, k) \), мы можем заменить ее в:

Если мы разделим обе части на \ (k! \), Мы получим замкнутую формулу для \ ({n \ choose k} \ text {.} \)

Замкнутая формула для \ ({n \ choose k} \)

\ begin {уравнение *} {n \ choose k} = \ frac {n!} {(N-k)! K!} \ End {уравнение *}

Мы говорим, что \ (P (n, k) \) подсчитывает перестановок , а \ ({n \ choose k} \) подсчитывает комбинаций . Формулы для каждого очень похожи, есть только лишний \ (k! \) В знаменателе \ ({n \ choose k} \ text {.} \). Этот дополнительный \ (k! \) Объясняет факт что \ ({n \ choose k} \) не делает различий между разными порядками, в которых могут появляться объекты \ (k \).Мы просто выбираем (или выбираем) объекты \ (k \), а не упорядочиваем их. Возможно, термин «комбинация» вводит в заблуждение. Мы не имеем в виду, что это кодовый замок (где порядок определенно имеет значение). Возможно, лучшая метафора — это сочетание вкусов: вам просто нужно решить, какие ароматы сочетать, а не порядок, в котором их объединять.

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

Пример \ (\ PageIndex {5} \)

Вы решили устроить званый обед.Несмотря на то, что вы невероятно популярны и имеете 14 разных друзей, у вас достаточно стульев, чтобы пригласить 6 из них.

1. Сколько у вас есть вариантов, для каких 6 друзей пригласить?
2. Что, если вам нужно решить не только, каких друзей пригласить, но и где их усадить за длинным столом? Сколько у вас тогда вариантов?

Решение

1. Вы должны просто выбрать 6 друзей из группы из 14 человек.Это можно сделать \ ({14 \ choose 6} \) способами. Мы можем найти это число, используя треугольник Паскаля или замкнутую формулу: \ (\ frac {14!} {8! \ Cdot 6!} = 3003 \ text {.} \)
2. Здесь вы должны сосчитать все способы, которыми вы можете переставить 6 друзей, выбранных из группы из 14. Итак, ответ будет \ (P (14, 6) \ text {,} \), который можно вычислить как \ (\ frac {14 !} {8!} = 2192190 \ text {.} \)

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

Как связаны эти числа? Обратите внимание, что \ (P (14,6) \) намного больше, чем \ ({14 \ choose 6} \ text {.} \). Это имеет смысл. \ ({14 \ choose 6} \) выбирает 6 друзей, но \ (P (14,6) \) размещает 6 друзей, а также выбирает их. Фактически, мы можем точно сказать, насколько больше \ (P (14,6) \). В обеих задачах на счет мы выбираем 6 друзей из 14. Для первого мы останавливаемся на 3003 путях. Но для второй задачи подсчета каждый из этих 3003 вариантов выбора 6 друзей может быть расположен ровно \ (6! \) Способами.Итак, теперь у нас есть выбор \ (3003 \ cdot 6! \), И это точно \ (2192190 \ text {.} \)

Или взгляните на первую проблему с другой стороны. Мы хотим выбрать 6 друзей из 14, но нас не волнует порядок их выбора. Чтобы выбрать 6 друзей из 14, мы можем попробовать следующее:

\ begin {уравнение *} 14 \ cdot 13 \ cdot 12 \ cdot 11 \ cdot 10 \ cdot 9. \ end {уравнение *}

Это разумное предположение, поскольку у нас есть 14 вариантов для первого гостя, затем 13 для второго и так далее.Но предположение неверно (на самом деле этот продукт равен \ (2192190 = P (14,6) \)). Он различает разные заказы, в которых мы могли приглашать гостей. Чтобы исправить это, мы можем разделить на количество различных расстановок 6 гостей (чтобы все они засчитывались как один результат). Существует ровно \ (6! \) Способов разместить 6 гостей, поэтому правильный ответ на первый вопрос —

.

\ begin {уравнение *} \ frac {14 \ cdot 13 \ cdot 12 \ cdot 11 \ cdot 10 \ cdot 9} {6!}.\ end {уравнение *}

Обратите внимание, что это можно записать по-другому:

.

\ begin {Equation *} \ frac {14!} {8! \ Cdot 6!}. \ end {уравнение *}

— это то, что у нас было изначально.

Перестановка / Комбинация — SAT Math

Если вы считаете, что контент, доступный через Веб-сайт (как определено в наших Условиях обслуживания), нарушает или другие ваши авторские права, сообщите нам, отправив письменное уведомление («Уведомление о нарушении»), содержащее в информацию, описанную ниже, назначенному ниже агенту.Если репетиторы университета предпримут действия в ответ на ан Уведомление о нарушении, оно предпримет добросовестную попытку связаться со стороной, которая предоставила такой контент средствами самого последнего адреса электронной почты, если таковой имеется, предоставленного такой стороной Varsity Tutors.

Ваше Уведомление о нарушении прав может быть отправлено стороне, предоставившей доступ к контенту, или третьим лицам, таким как в качестве ChillingEffects.org.

Обратите внимание, что вы будете нести ответственность за ущерб (включая расходы и гонорары адвокатам), если вы существенно искажать информацию о том, что продукт или действие нарушает ваши авторские права.Таким образом, если вы не уверены, что контент находится на Веб-сайте или по ссылке с него нарушает ваши авторские права, вам следует сначала обратиться к юристу.

Чтобы отправить уведомление, выполните следующие действия:

Вы должны включить следующее:

Физическая или электронная подпись правообладателя или лица, уполномоченного действовать от их имени; Идентификация авторских прав, которые, как утверждается, были нарушены; Описание характера и точного местонахождения контента, который, по вашему мнению, нарушает ваши авторские права, в \ достаточно подробностей, чтобы позволить репетиторам университетских школ найти и точно идентифицировать этот контент; например нам требуется а ссылка на конкретный вопрос (а не только на название вопроса), который содержит содержание и описание к какой конкретной части вопроса — изображению, ссылке, тексту и т. д. — относится ваша жалоба; Ваше имя, адрес, номер телефона и адрес электронной почты; а также Ваше заявление: (а) вы добросовестно считаете, что использование контента, который, по вашему мнению, нарушает ваши авторские права не разрешены законом, владельцем авторских прав или его агентом; (б) что все информация, содержащаяся в вашем Уведомлении о нарушении, является точной, и (c) под страхом наказания за лжесвидетельство, что вы либо владелец авторских прав, либо лицо, уполномоченное действовать от их имени.

Отправьте жалобу нашему уполномоченному агенту по адресу:

Чарльз Кон Varsity Tutors LLC
101 S. Hanley Rd, Suite 300
St. Louis, MO 63105

Или заполните форму ниже:

GRE Math: в чем разница между комбинацией и перестановкой?

Знаете ли вы разницу между перестановкой и комбинацией? Нет? Ты не одинок. Когда дело доходит до анализа данных GRE, комбинации и перестановки — отрава для многих студентов.Тем не менее, за эти годы я заметил, что проблема заключается не столько в них обоих, сколько в том, какой из них использовать для конкретной задачи: вопрос о комбинации или перестановке. Другими словами, учащимся нетрудно определить, является ли вопрос проблемой комбинаций / перестановок. Трудность состоит в том, чтобы точно знать, что это за комбинация или перестановка?

Комбинации и перестановки

Один из способов представить это — представить перестановок как количество расстановок или порядков внутри фиксированной группы.Например, если у меня пять учеников, и я хочу выяснить, сколько способов они могут сидеть на пяти стульях, я воспользуюсь формулой перестановок. Во-первых, количество в группе фиксировано. Во-вторых, я ищу, как я могу «расположить» студентов по пяти стульям.

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

Чтобы убедиться, что вы понимаете это важное различие, вот три различных сценария. Ваша задача не в том, чтобы решить вопрос, а в том, чтобы определить, используете ли вы комбинации или формулу перестановок для их решения.

Комбинация против перестановки: вы решаете

1. У Джоан есть дома пять панелей, которые она хочет раскрасить. У нее есть пять красок разного цвета, и она собирается покрасить каждую панель в другой цвет. Сколько разных способов раскрасить пять панелей?

2.Сколько уникальных комбинаций слова MAGOOSH я могу составить, зашифровав буквы?

3. Семь астронавтов пытаются стать частью космической летной группы из трех человек. Сколько разных летных команд можно сформировать?

Разница между комбинацией и перестановкой: ответы

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

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

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

Хорошо, это была небольшая уловка, поскольку я использовал слово «комбинации». Но это слово я использовал в разговорной речи, а не математически. В этом случае количество букв фиксировано. Мы их просто переставляем.

3. Комбинации

Мы выбираем группу из большей группы. Можно думать об этом так: когда вы используете слово «выбрать» в контексте выбора из группы, вы имеете дело с комбинациями. И слова «выбрать», и «комбинации» начинаются с буквы «С».Из этого правила есть исключение, о котором я расскажу в следующем разделе.

Разница между перестановкой и комбинацией: основной момент

Большая идея: если вы формируете группу из большей группы и важно размещение в меньшей группе, тогда вы хотите использовать перестановки.

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

Помните, что порядок перестановок является ключевым.Несмотря на то, что три лучших места для спринтеров образуют подгруппу, именно порядок в этой подгруппе имеет большое значение, и это разница между золотой, серебряной и бронзовой медалями. Простой способ математически решить этот вопрос — представить, что черточки ниже — это подиум, на котором будет стоять каждый спринтер (хотя черточки находятся на одном уровне):

____ ____ ____
золото серебро бронза

Чтобы узнать количество различных расстановок, спросите себя, сколько спортсменов сможет подняться на пьедестал почета? Что ж, всего у нас 12 спортсменов.А как насчет серебряного подиума? Теперь у нас на одного спортсмена меньше, потому что один уже на пьедестале почета. Это дает нам 11 очков за серебряную медаль. Наконец, у нас остается 10 спортсменов на подиуме за бронзовые медали.

Математика выглядит так:

12 x 11 x 10 = 1320

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

___4_______ x _____6______ = 24
# рубашек # шорт

Я не хочу их добавлять, в этом случае я получил бы 10, неправильный ответ.

Причина, по которой я поднимаю фундаментальный принцип счета, состоит в том, что некоторые вопросы фактически сочетают комбинации с фундаментальным принципом счета (хотя вы, вероятно, будете чаще использовать фундаментальный принцип счета с вопросами перестановки).Чтобы дать вам представление о том, как могут отображаться комбинации наряду с основным принципом счета, попробуйте ответить на следующий вопрос:

В классе миссис Пирсон 4 мальчика и 5 девочек. Она должна выбрать двух мальчиков и двух девочек для работы в аттестационной комиссии. Если одна девочка и один мальчик уйдут до того, как она сможет сделать выбор, то сколько уникальных комитетов может появиться в результате вышеизложенной информации?
(A) 9
(B) 12
(C) 18
(D) 22
(E) 120

Первым шагом в этой проблеме является определение того, имеем ли мы дело с комбинациями или перестановками.Поскольку я «выбираю» из большей группы, в данном случае из двух отдельных групп, я хочу использовать комбинации. Помните: как только мы выбрали двух мальчиков или трех девочек, позиция в комитете не имеет значения. То есть, вы либо в комитете, либо вне комитета (здесь нет золотых медалистов!)

Следующее, что нужно заметить с этой проблемой, — это проблема с исходными 9 учениками, 2 из них, один мальчик и одна девочка. Итак, у нас осталось 3 мальчика и 4 девочки. Мы хотим выбрать по два.Поэтому мы должны создать одну комбинацию для мальчиков и одну для девочек.

Для мальчиков у нас есть 3C2, а для девочек — 4C2. Это дает нам: 3C2 = 3 и 4C2 = 6
Последний шаг — как только мы выяснили вышеупомянутые комбинации, мы должны использовать фундаментальный принцип подсчета и умножить общее количество возможностей в комитете, а не складывать их: 3 x 6 = 18, ответьте (С).
Многие студенты застревают на этом шаге и задаются вопросом, почему я не добавляю их. Это хороший вопрос, поэтому я хочу, чтобы вы представили, что у вас есть 3 рубашки и 3 штана.Сколько разных нарядов рубашка-брюки ты можешь надеть? Ну, на каждую рубашку есть 3 варианта брюк. Таким образом, мы умножаем и получаем 9.

Мой совет — попробовать еще примерно 5 или 6 задач на комбинации / перестановки, чтобы вы могли понять это. Немного попрактиковавшись, вы сможете справиться с большинством проблем, которые вам дает GRE. Даже если вы пропустите вопрос — вероятно, из-за того, что он очень сложный — основ этого поста должно быть достаточно, чтобы помочь вам понять объяснение этого вопроса, чтобы вы могли получить аналогичный вопрос прямо в будущем.