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

ⁿ C _r = . ^н-1 С _р-1

ⁿ C _r = (n – r + 1) ⁿ C _r-1

ⁿ C _{1 5 0 9 ^{= п-1}} = п

Решенные примеры

1. Докажите, что

Решение:

= =

2. Докажите, что

Решение: 6

=

3. Есть 6 вопросов с несколькими вариантами ответов на экзамене. Сколько возможных последовательностей ответов, если в первых трех вопросах по 4 варианта, а в следующих трех по 5 вариантов?

Решение: На каждый из первых трех вопросов можно ответить 4 способами, а на каждый из следующих трех вопросов можно ответить 5 различными способами.

Отсюда искомое количество различных последовательностей ответов

= 4 × 4 × 4 × 5 × 5 × 5 = 8000.

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

Решение: Любой из 5 человек может покинуть каюту 7 способами независимо от других.

Следовательно, необходимое количество способов = 7 × 7 × 7 × 7 × 7 = 7⁵.

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

Решение: Поставив на стол одного мальчика, оставшихся можно разложить на 4! способы.

Будет 5 мест, по одному между двумя мальчиками

который могут заполнить 5 девушек из 5! способы.

Отсюда по принципу умножения искомое количество способов = 4! × 5! = 2880.

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

Решение: Оставив одно место свободным между двумя мальчиками, можно сесть на 4! способы. Тогда на оставшихся 5 местах, 5 девушек сидят на 5! способы. Следовательно, искомое число = 4! × 5!

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

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

Кроме того, сотое место можно заполнить также 5 способами.

Следовательно, искомое количество трехзначных чисел равно 5 × 5 × 5 = 125.

8. Сколькими способами можно расставить 8 человек по кругу?

Решение: Восемь человек можно расположить в круг

(8 – 1) ! = 7! = 5040.

ДАЛЕЕ: Перестановка Комбинация

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

Сначала обратимся к , считая . Хотя это звучит просто, возможно, слишком просто учиться, это не так. Когда мы говорим о счете, это стенография для определения размера множества или, чаще, размеров многих наборы, все с чем-то общим, но разные размеры в зависимости от один или несколько параметров. Например: сколько исходов возможно когда бросают кубик? Две кости? $n$ кости? Как сказано, это двусмысленно: что мы подразумеваем под «результатом»? Предположим, мы бросаем две кости, скажем, красный кубик и зеленый кубик. Является ли «красный два, зеленый три» другим результат, чем «красное три, зеленое два»? Если да, мы подсчитываем количество возможных «физических» исходов, а именно 36. Если нет, то есть 21. Нас даже могут интересовать просто возможные итоги, т.е. в этом случае есть 11 исходов.

Даже довольно простая первая интерпретация опирается на некоторую степень знание счета; мы сначала выясним два простых факта. В с точки зрения размеров множества, предположим, что мы знаем, что множество $A$ имеет размер $m$ и множество $B$ имеет размер $n$. Каков размер $A$ и $B$ вместе, то есть размер $A\cup B$? Если мы знаем, что $A$ и $B$ не имеют элементов в общий, то размер $A\cup B$ равен $m+n$; если у них есть элементы в общее, нам нужно больше информации. Простая, но типичная проблема этого тип: если мы бросим два кубика, сколько существует способов получить либо 7, либо 11? Так как есть 6 способов получить 7 и два способа получить 11, ответ: $6+2=8$. Хотя этот принцип прост, его легко забыть требование непересекаемости двух множеств и, следовательно, использовать это когда обстоятельства иные. Этот принцип часто называется 9п м_i$. Этот может быть доказано простым рассуждением по индукции.

Почему мы знаем, не перечисляя их всех, что существует 36 исходов? когда бросают две игральные кости? Мы можем рассматривать результаты как два отдельных результаты, то есть результат броска кубика номер один и результат броска кубика номер два.

Пример 1.2.1 Сколько исходов возможно при броске трех игральных костей, если не может быть двух одинаковых? Первые две кости вместе имеют $6\cdot 5=30$ возможных исходов, сверху. Для каждого из этих 30 исходов, есть четыре возможных исхода для третьего кубика, поэтому общее количество исходов $30\cdot 4=6\cdot 5\cdot 4=120$. (Обратите внимание, что мы считаем кости различимыми, то есть броском 6, 4, 1 отличается от 4, 6, 1, потому что первое и второе кости различны в двух бросках, даже несмотря на то, что числа как набор одинаковы.) $\квадрат$

Пример 1.2.2. Предположим, что блоки с номерами от 1 до $n$ находятся в бочке; мы вытащите из них $k$, расположив их в линию, как мы. Сколько исходы возможны? То есть, сколько различных расположений $k$ блоки могли бы мы видеть?

По сути, это то же самое, что и в предыдущем примере: имеется $k$ «пятен». заполняться блоками. Любой из блоков $n$ может появиться первым в линия; то любой из оставшихся $n-1$ может появиться следующим, и, таким образом, на. Таким образом, число исходов равно $n(n-1)(n-2)\cdots(n-k+1)$, согласно принцип умножения. в В предыдущем примере первое «пятно» было номером один, второе точка была номером два, третья точка была номером три, и $6\cdot5\cdot4=6(6-1)(6-2)$; обратите внимание, что $6-2=6-3+1$. $\квадрат$

Это довольно общая проблема:

Определение 1.2.3 Количество перестановок $n$ вещи, взятые $k$ за раз, $$P(n,k)=n(n-1)(n-2)\cdots(n-k+1)={n!\over (n-k)!}.$$ $\квадрат$

Перестановка некоторых объектов представляет собой конкретное линейное упорядочение объекты; Фактически $P(n,k)$ одновременно учитывает две вещи: количество способов выбрать и упорядочить $k$ из $n$ объектов. Полезный частный случай $k=n$, в котором мы просто считаем число способов упорядочить все $n$ объектов. Это $n(n-1)\cdots(n-n+1)=n!$. Обратите внимание, что вторая форма $P(n,k)$ из определение дает $${n!\over (n-n)!}={n!\over 0!}.$$ Это правильно, только если $0!=1$, поэтому мы принимаем стандартное соглашение что это правда, то есть мы определите $0!$ как $1$.

Предположим, мы хотим подсчитать только количество способов выбрать $k$ предметов. из $n$, то есть порядок нам не важен. В Пример 1.2.1, мы подсчитали количество броски трех игральных костей с разными числами. Кости были различимы или в определенном порядке: первый кубик, второй и третий. Теперь мы хотим просто посчитать, сколько комбинаций чисел есть, причем 6, 4, 1 теперь считаются той же комбинацией, что и 4, 6, 1.

Пример 1.2.4 Предположим, нам нужно перечислить все 120 возможностей в пример 1.2.1. Список будет содержать множество исходов, которые мы теперь хотим считать одним исходом; 6, 4, 1 и 4, 6, 1 будут в списке, но не должны учитываться в отдельности. Сколько раз один результат появится в списке? Это задача на перестановку: есть $3!$ порядков, в которых 1, 4, 6 может появиться, и все 6 из них будут в списке. На самом деле каждый исход появится в списке 6 раз, так как каждый исход может появляются в заказах $3!$. Следовательно, список слишком велик в 6 раз; правильный счет для новой задачи: $120/6=20$. $\квадрат$

Следуя тем же рассуждениям вообще, если у нас есть $n$ объектов, количество способов выбрать $k$ из них $P(n,k)/k!$, так как каждый набор из $k$ объектов будет посчитал $k!$ раз по $P(n,k)$.

Определение 1.2.5 Количество подмножеств размера $k$ множества размера $n$ (также называется $n$-множеством) $$C(n,k)={P(n,k)\более k!}={n!\over k!(n-k)!}={n\выбрать k}.$$ Обозначение $C(n,k)$ используется редко; вместо этого мы используем $n\выбрать k$, произносится как «$n$ выбирает $k$». $\квадрат$

Пример 1.2.6 Рассмотрим $n=0,1,2,3$. Несложно перечислить подмножества малого $n$-множества; типичное $n$-множество $\{a_1,a_2,\ldots,a_n\}$. $0$-множество, а именно пустое множество, имеет одно подмножество, пустой набор; $1$-множество имеет два подмножества, пустое множество и $\{a_1\}$; $2$-подмножество имеет четыре подмножества, $\emptyset$, $\{a_1\}$, $\{a_2\}$, $\{a_1,a_2\}$; а $3$-подмножество имеет восемь: $\emptyset$, $\{a_1\}$, $\{a_2\}$, $\{a_3\}$, $\{a_1,a_2\}$, $\{a_1,a_3\}$, $\{a_2,a_3\}$, $\{a_1,a_2,a_3\}$. Затем из этих списков легко вычислить $n\выбрать k$: $$\displaylines{\cr \матрица{ &\rlap{\lower 3pt\hbox{$\Rule{65pt}{0pt}{0.5pt}$}}\cr &0\кр п&1\кр &2\кр &3\кр }\влево\верт \матрица{ 0&\нижний 3.5pt\hbox{}\rlap{\smash{\поднять 1.5em \hbox{$k$}}}1&2&3\cr 1\кр 1&1\кр 1&2&1\кр 1&3&3&1\кр }\право.\cr}$$ $\квадрат$

Вы, наверное, узнаете эти цифры: это начало Треугольник Паскаля . Каждая запись в Треугольник Паскаля получается путем добавления двух элементов из предыдущего ряд: тот, что прямо сверху, и тот, что выше и левее. Этот предполагает, что ${n\выбрать k}={n-1\выбрать k-1}+{n-1\выбрать k}$, и действительно это правда. Чтобы сделать это аккуратно, мы принимаем соглашение о том, что ${n\choose k}=0$, когда $kn$.

Теорема 1.2.7 $\ds{n\выберите k}={n-1\выберите k-1}+{n-1\выберите k}$.

Доказательство. Типичным $n$-множеством является $A=\{a_1,\ldots,a_n\}$. Мы рассматриваем два типа подмножества: содержащие $a_n$ и не содержащие. Если $k$-подмножество $A$ не содержит $a_n$, то оно является $k$-подмножеством $\{a_1,…,a_{n-1}\}$, и таких $n-1\выберите k$. Если оно содержит $a_n$, то он состоит из $a_n$ и $k-1$ элементов $\{a_1,…,a_{n-1}\}$; так как их $n-1\выберите k-1$, таких подмножеств $n-1\выберите k-1$. Таким образом, общее количество $k$-подмножеств $A$ равно ${n-1\выбрать k-1}+{n-1\выбрать k}$.

Обратите внимание, что когда $k=0$, ${n-1\выберите k-1}={n-1\выберите -1}=0$, и когда $k=n$, ${n-1\выбрать k}={n-1\выбрать n}=0$, так что ${n\выбрать 0}={n-1\выбрать 0}$ и ${n\выбрать n}={n-1\выбрать п-1}$. Эти значения являются граничными в треугольнике Паскаля. $\qed$

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

Пример 1.2.8 Шесть человек должны сидеть за круглым столом; сколько сидячих мест аранжировки есть?

Не совсем ясно, что именно мы имеем в виду, чтобы считать здесь. если есть «специальное место», например, может иметь значение, кто окажется на этом сиденье. Если это не имеет значения, нас интересует только относительное положение каждого человека. Тогда может или не может быть важно, является ли определенное лицо находится слева или справа от другого. Так что этот вопрос можно интерпретируется (по крайней мере) тремя способами. Давайте ответим на них все.

Во-первых, если имеют значение фактические стулья, на которых сидят люди, то это точно так же, как выстраивание шести человек в ряд: 6 вариантов места номер один, 5 для второго места и так далее, всего 6 долларов! Если стулья не имеют значения, тогда $6!$ считают одно и то же расположение слишком большим раз, по одному разу для каждого человека, который может быть на первом месте. Итак, общее количество в в этом случае $6!/6=5!$. Другой подход к этому: поскольку фактическое места не имеют значения, просто посадите одного из шести человек на стул. Тогда мы нужно расставить оставшихся 5 человек в ряд, что можно сделать в $5!$ способами. Наконец, предположим, что нас волнует только то, кто рядом с кем, игнорируя право и лево. Тогда предыдущий ответ считает каждый расположение дважды, один раз для порядка против часовой стрелки и один раз для по часовой стрелке. Итого $5!/2=P(5,3)$. $\квадрат$

Мы дважды видели общий принцип в действии: если мы можем пересчитать желаемый набор таким образом, чтобы каждый элемент считался одинаковым количество раз, мы можем получить желаемое количество, просто разделив на общий фактор пересчета. Это по-прежнему будет полезной идеей. А вариация на эту тему состоит в том, чтобы пересчитать , а затем вычесть из сумма перерасчета.

Пример 1.2.9. Сколькими способами можно выстроить шесть человек так, чтобы конкретная пара людей не является соседней?

Обозначим людей $A$ и $B$. Общее количество заказов составляет $6!$, но здесь учитываются заказы с $A$ и $B$ рядом друг с другом. Сколько из них есть? Думать о эти два человека как единое целое; сколько существует способов выстроить Блок $AB$ с остальными четырьмя людьми? У нас есть 5 предметов, поэтому ответ $5!$. Каждый из этих порядков соответствует двум различным порядкам в которые $A$ и $B$ являются смежными, в зависимости от того, является ли $A$ или $B$ первый. Таким образом, количество $6!$ слишком велико на $2\cdot5!$ и количество, которое мы seek равен $6!-2\cdot 5!=4\cdot5!$. $\квадрат$ 9{e_n}$ есть, где $p_i$ — различные простые числа?

Пример 1.2.2 Покерная рука состоит из пяти карт из стандартных 52 карт. колода с четырьмя мастями и тринадцатью достоинствами в каждой масти; получатель чего-то карты в руке значения не имеют. Из скольких рук состоит 2 карты одного достоинства и 3 карты другого достоинства (фулл-хаус)? Сколько состоит из 5 карт одной масти (флеш)?

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

Пример 1.2.4 Восемь человек должны сидеть за столом; стулья неважно, только кто рядом с кем, а справа и слева другой. Два человека, X и Y, не могут сидеть рядом друг с другом. Сколько посадочных мест возможно?

Пример 1. 2.5 В шахматах ладья атакует любую фигуру в той же строке или столбце. как ладья, если между ними нет другой фигуры. Сколькими способами можно ли разместить на шахматной доске восемь неразличимых ладей так, чтобы двое не нападают друг на друга? Как насчет восьми неразличимых ладей на доска $10\times 10$?

Пример 1.2.6 Предположим, мы хотим поставить 8 неатакующих ладей на поле. шахматная доска. Сколькими способами мы можем это сделать, если 16 наиболее Квадраты «северо-запад» должны быть пустыми? А если только 4 самых Квадраты «северо-запад» должны быть пустыми?

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