ТГиК-2019-Семинар-09.09.2019

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Факториал

TODO: Дать краткую базу по факториалам, 0! = 1, сокращение факториалов в дробях, свойства.

Правило суммы

В группе А-05-18 n студентов, а в А-13-18 — m. Выбрать одного студента из А-05-18 можно n способами, аналогично из тринадцатой группы одного студента можно выбрать m способами. А выбрать одного студента из обеих групп можно m+n способами.

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

Правило суммы применяется, когда удается разбить все изучаемые комбинации на несколько классов, причем каждая комбинация входит в один и только один класс. Иными словами, необходимо убедиться, что ни один из способов выбора объекта А не совпадает с каким-либо способом выбора объекта B. На предыдущем примере представим, что один из студентов недавно перевелся из одной группы в другую. Из списка пятой группы его еще не удалили, а в список студентов тринадцатой уже добавили. У нас появилось совпадение способов выбора объекта (студента), из-за чего правило суммы утрачивает силу. Способов выбора становится $$m+n-k$$, где $$k$$ — число совпадений

Правило произведения

Возьмем те же условия про две группы, но в этот раз нам нужно выбрать пару из двух студентов, причем такую, где в каждой паре есть по студенту от каждой группы. Здесь стоит представить ментальный процесс выбора такой пары. Выбираем студента из пятой группы, то есть из n, полдела сделано. Теперь необходимо подобрать ему пару из студентов тринадцатой группы. Влияет ли наш выбор первого члена пары на выбор второго? Совершенно не влияет. Таким образом, пару мы выбираем из m студентов. Таким образом, мы, составляя комбинацию из двух элементов (студентов) точно знаем, сколькими способами можно выбрать первый элемент и сколькими способами можно выбрать второй элемент, причем число способов выбора второго элемента не зависит от того, как именно выбран первый. В таком случае, выбрать пару студентов можно m*n способами.

Если объект A можно выбрать m способами и если после каждого такого выбора объект B можно выбрать n способами, то выбор пары (A; B) в указанном порядке можно осуществить m*n способами.

Как и в прошлый раз, попробуем сломать правило произведения в нашей задаче. Предположим, что мы хотим не просто взять пару студентов из разных групп, но и сделать это таким образом, чтобы в паре один из студентов оказался студентом, а второй — студенткой. Снова представим, как мы будем выбирать такую пару. Выбрали элемент из пятой группы. Он оказался парнем. Сколько у нас способов подобрать ему пару из тринадцатой? Столько, сколько в 13 группе девушек. Однако если бы мы выбрали в качестве первого элемента девушку, то способов выбрать ей пару из 13 группы было бы столько, сколько в ней студентов мужского пола. Таким образом, правило произведения более не применяется. Эту измененную задачу можно очень легко решить, используя только комбинации правила суммы и правила произведения. Пока попробуем решить простейшую задачу на правило произведения:

  • Сколько пятизначных шестнадцатиричных идентификаторов можно составить таким образом, чтобы любые две стоящих рядом цифры (знака) были различны?*

Задача тривиальная. Выбрать первую цифру мы можем 16 способами. Во втором разряде мы не можем, по условию задачи, повторять предыдущий выбор, так что для него перед нами стоит выбор из 15 цифр. На третьей позиции мы не можем повторять вторую, но уже можем повторить первую, то есть, способов выбрать снова 15. Аналогично выбираем до пятого знака. Таким образом, получаем ответ\[16\cdot15\cdot15\cdot15\cdot15=16\cdot15^4=810000\]

Вернемся к нашим демографическим вопросам. Сформулируем задачу:

[Вторая пара] *В группе А-05-18 14 человек, половина из которых девушки, а в А-16-18 студентов 10, из них 3 девушки. Необходимо выбрать пару, состоящую из разнополых студентов различных групп. Сколькими способами можно это сделать?*

[Третья пара] *В группах А-13-18 и А-14-18 по 12 человек, в первой из них 5 девушек, а во второй 7. Необходимо выбрать пару, состоящую из разнополых студентов различных групп. Сколькими способами можно это сделать?*

[Подменить значения на третьей паре] Для решения этой задачи вновь представим последовательность действий при выборе такой пары. Выбирать будем из групп по порядку. Способов выбрать первого студента (студентку) у нас 14, причем на девушек и парней приходится равное количество случаев (7). Если первым элементом оказалась девушка, то выбирать ей пару придется из 7 парней, а если из пятой группы мы выбрали парня, то способов выбрать ему девушку из шестнадцатой будет 3. По правилу произведения в первом случае получаем 7*7, а во втором 7*3 способов собрать пару. Так как подсчитанные нами количества способов являются исчерпывающими и не имеют никаких пересечений, то мы можем применять правило суммы\[7\cdot7+7\cdot3=70\]

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

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

В задачах по комбинаторике практически такой же вопрос может звучать несколько иначе, попробуем переформулировать. У нас есть k = 16 позиций (бит). Их необходимо заполнить элементами. На каждую позицию можно разместить элемент одного из n = 2 видов, причем элементы могут повторяться. Два способа заполнения считаются различными, если хотя бы на одном месте в них стоят разные элементы. Сколько существует способов заполнить два байта?

В таких условиях каждый способ заполнения является **размещением с повторениями из n элементов по k** (k — число элементов, которые могут повторяться, вошедших в размещение). Число всех таких размещений обозначается следующим образом:

$$\bar{A}_n^k$$

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

$$\bar{A}_n^k=n^k$$

Итого, чтобы решить нашу задачу про способы заполнения двух байт, или, иными словами, способы разместить с повторениями два элемента (0 и 1) в двоичную строку длиной 16 бит, мы применим вышеуказанную формулу:

$$\bar{A}_2^{16}=2^{16}=65536$$

Задачи на семинар и самостоятельную работу

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

(Решение: Неудовлетворительной оценкой принято считать любой балл ниже 3. Если принять максимальный балл за экзамен равный 5, то каждый из 4 студентов может получить 3 оценки: 3,4 и 5 баллов.

Для того, чтобы найти общее возможное количество способов получения оценок за экзамен, нужно количество оценок, а именно 3 возвести в 4 степень. В таком случае получим: А = 3^4 = 3 * 3 * 3 * 3 = 81

Ответ: оценки могут быть поставлены 81 различным способом )

2. Сколько чисел, меньших миллиона, можно написать с помощью цифр: а) 1, 5; б) 4, 5, 6; в) 0, 2, 8?

(Решение: По условию, числа меньше миллиона, следовательно это однозначные, двузначные, трёхзначные, четырёхзначные, пятизначные и шестизначные числа, разумеется, удовлетворяющие условиям пунктов а), б) и в)

а) Для записи чисел можно использовать лишь цифры 1 и 5.

Однозначных:   2  

Двузначных:     2*2=2²=4

Трёхзначных:   2*2*2=2³=8

Четырёхзначных: 2*2*2*2=2⁴=16

Пятизначных: 2*2*2*2*2=2⁵=32

Шестизначных: 2*2*2*2*2*2=2⁶=64

Общее количество: 2+4+8+16+32+64=126

Ответ: 126 чисел

б) по аналогии с (а) A = 3 + 32 + 33 + 34 + 35 + 36 = 1092

Ответ: 1092 способа

в) Для записи чисел можно использовать цифры 0, 8 и 2.

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

Однозначных:   2

Двузначных:     2*3=6

Трёхзначных:   2*3*3=18

Четырёхзначных: 2*3*3*3=54

Пятизначных: 2*3*3*3*3=162

Шестизначных: 2*3*3*3*3*3=486

Общее количество:2+6+18+54+162+486=728

Ответ:  728 чисел

)

3. В деревне проживают 1000 жителей. Докажите, что по крайней мере двое из них имеют одинаковые инициалы.

(Решение: Всего есть 33 буквы. Но не со всех букв может начинаться имя и фамилия. Таких букв 3 - ю, ь, ъ. То есть есть 30 букв с которых может начинаться имя и фамилия человека. Воспользуемся формулой комбинаций с повторениям.

А = 30 * 30 = 900

Всего может быть 900 уникальных комбинаций. То есть в деревне как минимум у 100 человек будут повторятся первые буквы в имени и фамилии. )

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

(Решение: на первую позицию можно поставить число от 2 до 9, на вторую и третью также, а вот начиная с четвертой позиции мы можем использовать числа от 0 до 9. Получаем : $$A= \bar{A}_8^3*\bar{A}_{10}^3$$

Ответ: А= 83 * 103)

5. В приложение к диплому идут оценки за 32 дисциплины. Сколько существует различных способов заполнить приложение к диплому при условии, что получившие и не пересдавшие оценку "2" студенты остаются без диплома?

(Решение: Это снова размещение с повторением, поэтому А=332)

6. Вы хотите подобрать пароль к "своему" аккаунту с помощью несловарного брутфорса. Вы точно знаете длину пароля — 12 символов, и то, что он состоит из букв латинского алфавита различного регистра и цифр. Предположим, что вы используете старенький ноутбук и подбираете пароли со скоростью 1000 шт. в секунду. Сколько вам, в самом худшем случае, понадобится лет на подбор пароля

(Решение: "осторожно спойлеры: боюсь Вам не хватит жизни". Итак, алфавит состоит из 26 букв, это уже много, а еще и различного регистра, получаем 52 возможных символа, и езе 10 цифр. 26+26+10=64 - из стольких символов будем собирать пароль. На первую позицию можем поставить один из 64 символов, на вторую - 64, да и на третью , и на двенадцатую. Значит всего у нас 6412 возможных вариантов. Так как компьютер старенький, то он сгенерирует все наши пароли за (6412 / 1000) секунд, посчитаем сколько это в годах. 6412/1000/60(минуты)/60(часы)/24(суток)/365 = 1,497*1011 лет)

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

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

  • Кружок «БинПоиск» организовал олимпиаду по спортивному программированию. На участие в олимпиаде подали заявки 25 человек. Оказывается, что студенты из общежития в порыве скуки и азарта решили по этому поводу организовать ставки. Вы хотите заработать и решаетесь точно предсказать, кто именно займет первое, второе и третье места. Каковы ваши шансы на выигрыш?*

Попробуем переформулировать задачу на комбинаторный лад. Имеется упорядоченная последовательность, в которой k = 3 позиции. Необходимо все три позиции заполнить элементами, число которых составляет n = 25, причем так, чтобы ни один элемент не повторялся. Сколько существует способов заполнить такую последовательность? Два способа заполнения считаются различными, если хотя бы на одном месте в них стоят разные элементы.

Каждый способ заполнения позволяет разместить на k = 3 местах некоторые из n = 25 элементов, причем повторяться эти элементы не могут. Такой способ называется **размещением без повторений из n элементов по k** и обозначается следующим образом:

$$A_n^k$$

При составлении размещений без повторений из n элементов по k, необходимо сделать k выборов. На первом шагу можно выбрать любой из имеющихся n элементов. Если этот выбор уже сделан, то на втором шагу приходится выбирать из оставшихся n-1 элементов. Соответственно, на третьем стоит выбор из n-2, на четвертом n-3, а на k-м шагу — из n-(k-1)=n-k+1 элементов. Применяя правило произведения, получаем, что число размещений без повторений из n элементов по k выражается так:

$$A_n^k=n(n-1)\cdot...\cdot(n-k+1)$$

Домножив числитель и знаменатель на произведение (n-k)*(n-k-1)*...*1 получаем следующий вид:

$$A_n^k=\frac{n(n-1)...(n-k+1)(n-k)(n-k-1)\cdot...\cdot1}{(n-k)(n-k-1)\cdot...\cdot1}$$

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

$$A_n^k=\frac{n!}{(n-k)!}$$

Применим ее для решения нашей задачи про азартных студентов:

$$A_{25}^3=\frac{25!}{(25-3)!}=13800$$

Выходит, что удачно вы сможете поставить в 1 из 13800 случаев.

Поняв принцип размещений без повторений, можно без труда вывести еще одну комбинаторную величину. Предположим, что вы хотите предсказать всю итоговую таблицу олимпиады по спортивному программированию, то есть, предсказать для каждого из участников его финальное положение. Можно использовать ту же самую формулу числа размещений без повторений из n элементов по k, где n=25 и k=25. В решении этой задачи мы уже доподлинно знаем, какие именно участники будут использоваться в размещении, так как использоваться они будут все, то есть, нам нужно найти количество пермутаций упорядоченной последовательности из 25 элементов. Такие размещения из n элементов по n называются **перестановками из n элементов**, которые обозначаются следующим образом:

$$P_n$$

Формула для этой величины выводится из формулы для числа размещений без повторений:

$$P_n=A_n^n=n(n-1)\cdot...\cdot1=n!$$

Задачи на семинар и самостоятельную работу

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

(Решение: Всего 6 пар значит перчаток 12, 6 - на правую и 6 - на левую. Выберем перчатку на правую, всего 6 вариантов, выберем перчатку на левую, теперь вариантов 5. Общее кол-во комбинаций будет произведение возможностей выбрать перчатки: 5 * 6 = 30 )

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

(Решение: Русско-английский и англо-русский - это разные словари так же, как и другие. По правилу комбинаторики находим число размещений из 5 по 2:

$$A_{5}^2=\frac{5!}{(5-2)!}=20$$

Ответ: 20 словарей)

[](https://www.notion.so/2ef43f9926474649a9b53f494406359e#a6b95091833246e086348b513c036a5e)

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

(Решение: Три судьи могут выбрать победителя 103 способами. В $$A_{10}^3=\frac{10!}{(10-3)!}=720$$ случаях они назовут трех различных кандидатов в победители. Поэтому совпадение хотя бы двух судей будет в 1000-720=280 случаях. Доля таких случаев равна $$\frac{280}{1000}=0,28$$

Ответ: 0,28.

[](https://www.notion.so/2ef43f9926474649a9b53f494406359e#31c002634e304d33b0030ade59fe28cb)

4. Сколькими способами можно выбрать из полной колоды карт (52 карты) по одной карте каждой масти ?

Ответ: 13*13*13*13

А сколькими при условии, чтобы карты красных мастей и карты черных мастей образовывали пары (например, девятки пик и треф и валеты бубен и червей) ?

Ответ: 13*13

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

Ответ: 13*13

5. Сколькими способами можно расположить на шахматной доске 8 ладей так, чтобы они не могли бить друг друга?

Ответ: 8*7*6*5*4*3*2*1

6. На званый ужин приглашены $$n$$ мужчин и $$n$$ женщин. Напротив каждого места на круглый стол необходимо поставить табличку с именем того, кто будет на этом месте сидеть, но никакие два лица одного пола не должны сидеть рядом. Сколькими способами можно расставить таблички? А если $$n$$ мужчин и $$n$$ женщин садятся не за круглый стол, а на карусель, и способы, переходящие друг в друга при вращении карусели, считаются совпадающими?

(Решение: Естественно предположить, что как мужчины, так и женщины различимы. Предположим также, что места за столом также различимы, пронумеруем их. Если женщины займут четные места n! способами, то мужчины будут занимать нечетные места тоже n! способами и наоборот. По правилу умножения получаем $$2(n!)^2$$ .Если места за столом неразличимы, то стол можно поворачивать на одно место, при этом расположение сидящих не изменится (такая ситуация имеет место на карусели), поскольку имеется n способов расположения стола относительно сидящих, то предыдущий результат нужно разделить на $$n$$.

[](https://www.notion.so/2ef43f9926474649a9b53f494406359e#c612f8f265cb4a82b499d8f5614d1cfd)