ТГиК-2019-Семинар-09.09.2019: различия между версиями

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску
Строка 7: Строка 7:
 
Если некоторый объект А можно выбрать m способами, а другой объект B можно выбрать n способами, то выбор «либо A, либо B» можно осуществить m+n способами.
 
Если некоторый объект А можно выбрать m способами, а другой объект B можно выбрать n способами, то выбор «либо A, либо B» можно осуществить m+n способами.
  
Правило суммы применяется, когда удается разбить все изучаемые комбинации на несколько классов, причем каждая комбинация входит в один и только один класс. Иными словами, необходимо убедиться, что ни один из способов выбора объекта А не совпадает с каким-либо способом выбора объекта B. На предыдущем примере представим, что один из студентов недавно перевелся из одной группы в другую. Из списка пятой группы его еще не удалили, а в список студентов тринадцатой уже добавили. У нас появилось совпадение способов выбора объекта (студента), из-за чего правило суммы утрачивает силу. Способов выбора становится m+n-k, где k — число совпадений  
+
Правило суммы применяется, когда удается разбить все изучаемые комбинации на несколько классов, причем каждая комбинация входит в один и только один класс. Иными словами, необходимо убедиться, что ни один из способов выбора объекта А не совпадает с каким-либо способом выбора объекта B. На предыдущем примере представим, что один из студентов недавно перевелся из одной группы в другую. Из списка пятой группы его еще не удалили, а в список студентов тринадцатой уже добавили. У нас появилось совпадение способов выбора объекта (студента), из-за чего правило суммы утрачивает силу. Способов выбора становится $$m+n-k$$, где $$k$$ — число совпадений  
  
 
==Правило произведения==
 
==Правило произведения==
Строка 20: Строка 20:
 
Задача тривиальная. Выбрать первую цифру мы можем 16 способами. Во втором разряде мы не можем, по условию задачи, повторять предыдущий выбор, так что для него перед нами стоит выбор из 15 цифр. На третьей позиции мы не можем повторять вторую, но уже можем повторить первую, то есть, способов выбрать снова 15. Аналогично выбираем до пятого знака. Таким образом, получаем ответ:
 
Задача тривиальная. Выбрать первую цифру мы можем 16 способами. Во втором разряде мы не можем, по условию задачи, повторять предыдущий выбор, так что для него перед нами стоит выбор из 15 цифр. На третьей позиции мы не можем повторять вторую, но уже можем повторить первую, то есть, способов выбрать снова 15. Аналогично выбираем до пятого знака. Таким образом, получаем ответ:
  
<math>16\cdot15\cdot15\cdot15\cdot15=16\cdot15^4=810000</math>
+
$$$16\cdot15\cdot15\cdot15\cdot15=16\cdot15^4=810000$$$
  
 
Вернемся к нашим демографическим вопросам. Сформулируем задачу:
 
Вернемся к нашим демографическим вопросам. Сформулируем задачу:

Версия 06:24, 13 сентября 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. Четверо студентов сдают экзамен. Сколькими способами могут быть поставлены им оценки, если известно, что никто из них экзамен не завалил? 2. Сколько чисел, меньших миллиона, можно написать с помощью цифр: а) 1, 5; б) 4, 5, 6; в) 0, 2, 8? 3. В деревне проживают 1000 жителей. Докажите, что по крайней мере двое из них имеют одинаковые инициалы. 4. Сколько существует шестизначных телефонных номеров, в первых 3 цифрах которых не встречаются цифры 0 и 1? 5. В приложение к диплому идут оценки за 32 дисциплины. Сколько существует различных способов заполнить приложение к диплому при условии, что получившие и не пересдавшие оценку "2" студенты остаются без диплома? 6. Вы хотите подобрать пароль к "своему" аккаунту с помощью несловарного брутфорса. Вы точно знаете длину пароля — 12 символов, и то, что он состоит из букв латинского алфавита различного регистра и цифр. Предположим, что вы используете старенький ноутбук и подбираете пароли со скоростью 1000 шт. в секунду. Сколько вам, в самом худшем случае, понадобится лет на подбор пароля

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

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

  • Кружок «БинПоиск» организовал олимпиаду по спортивному программированию. На участие в олимпиаде подали заявки 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 пар перчаток различных размеров. Сколькими способами можно выбрать из них одну перчатку на левую руку и одну — на правую руку так, чтобы эти перчатки были различных размеров? 2. Сколько словарей нужно купить, чтобы можно было непосредственно выполнять переводы с любого из пяти языков: русского, английского, французского, немецкого, дотракийского на любой другой из этих пяти языков? На сколько больше словарей придется купить, если число различных языков равно 10?

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

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

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

1. Сколькими способами можно выбрать из полной колоды карт (52 карты) по одной карте каждой масти (13*13*13*13)? А сколькими при условии, чтобы карты красных мастей и карты черных мастей образовывали пары (например, девятки пик и треф и валеты бубен и червей) (13*13)? А так, чтобы из выбранных карт можно было составить две пары, состоящие из черной и красной карты одного и того же названия? (13*13) 2. Сколькими способами можно расположить на шахматной доске 8 ладей так, чтобы они не могли бить друг друга? (87654321) 3. На званый ужин приглашены 5 мужчин и 5 женщин. Напротив каждого места на круглый стол необходимо поставить табличку с именем того, кто будет на этом месте сидеть, но никакие два лица одного пола не должны сидеть рядом. Сколькими способами можно расставить таблички? А если 5 мужчин и 5 женщин садятся не за круглый стол, а на карусель, и способы, переходящие друг в друга при вращении карусели, считаются совпадающими?

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