[МУЗЫКА] В прошлых видео мы обсудили, как подсчитывать количество слов. Теперь мы перейдем ко второй стандартной постановке комбинаторики — к перестановкам. Давайте рассмотрим следующую задачу. Пусть у нас есть алфавит из n символов. Сколько есть различных слов длины k в этом алфавите, в которых никакой символ не повторяется дважды? Слова длины k без повторений букв называются k-перестановками. Что мы можем сразу заметить? Если у нас n < k, то k-перестановок нет вообще, нам просто не хватит букв в алфавите, чтобы использовать каждую букву без повторений. Так что в этом случае k перестановок у нас ноль, и мы можем ограничиться случаем, когда k ≤ n, мы можем рассматривать только такой вариант. Хорошо, перейдем к подсчету. На картинке мы звездочками изображаем элементы, которые мы должны выбрать, и сверху мы просто пронумеровали их, а снизу мы будем писать количество способов выбрать ту или иную букву. Опять мы применим правило произведения. Первую букву можно выбрать n способами, это может быть просто любая буква в нашем алфавите. Но сколько у нас есть способов выбрать вторую букву? Мы можем выбрать ее любой, кроме той буквы, которая уже стоит на первой позиции. И получается, что первая буква любая, но вторая в любом случае может быть выбрана n − 1 способом. Для выбора второй буквы у нас всегда остается n − 1 способ. И получается, что пару из первой и второй букв мы можем выбрать n * (n − 1) способами. Дальше, третью букву можно выбрать n − 2 способами. Доступны все буквы, которые не использованы на первой и второй позиции. То есть на первой и второй позиции могут стоять разные буквы, но в любом случае для третьей буквы остается n − 2 способа. Получается, что первые три буквы можно выбрать n * (n − 1) * (n − 2) способами и так далее. Для каждой следующей буквы у нас вариантов на один меньше. И для последней буквы у нас будет n − k + 1 вариант. Как быстро понять, почему там получается именно n − k + 1? Давайте заметим, что сумма чисел сверху и снизу, она не меняется, для первой буквы — это 1 сверху и n снизу, в сумме n + 1. Для второй буквы верхнее число увеличивается на 1, а нижнее уменьшается на 1, в сумме остается n + 1, и так далее. Чтобы сумма в конце тоже сошлась, нужно внизу написать n − k + 1. Так что для последней буквы остается n − k + 1 вариантов. Всего получается n * (n − 1) * (n − 2) *... * (n − k) вариантов. Это мы посчитали количество k-перестановок. И для этого есть удобное обозначение, понятно, что такая формула, ей не очень удобно пользоваться. Удобное обозначение n! — это просто 1 * 2 *... * n, то есть это произведение всех чисел от 1 до n. Это называется факториалом n, или n факториал. И в этих обозначениях число k-перестановок на n символах записывается проще: это n! / (n − k)!, то есть просто запись получается короче и удобнее. Но тут может возникнуть тонкость, потому что мы тут на что-то поделили, на (n − k)!. А что, если n − k — это ноль, не делим ли мы тут на ноль? Мы не делим, если договориться, что такое 0!. И стандартное соглашение, общепринятое, что 0! — это 1, то есть просто давайте договоримся, что 0! = 1. И тогда деление на ноль не происходит, и получается правильный ответ. Давайте рассмотрим такую задачу. У нас есть n книг, и нам нужно расставить их на полки. Сколько есть способов это сделать? Понятно, что разные способы отличаются порядком, в котором расставлены книги. Каждая книга — это, по сути, буква. И у нас есть n букв, и нам нужно расставить их все на полку. Получается, что у нас есть n-перестановка, у нас есть последовательность длины n из n букв. Это называется просто перестановками, когда k совпадает с n, то мы можем опустить букву k в начале и называть это просто перестановками. По предыдущей задаче их количество равно просто n!, тут обозначение получается совсем удобное. Итак, мы обсудили в этом уроке две стандартные постановки в комбинаторике: слова и перестановки. И все рассуждения опирались на правило произведения. Но эти постановки на самом деле помогают очень во многих случаях, они уже очень полезны. Но они не покрывают все наши потребности, возникают ситуации, когда нам нужно посчитать что-то, и перестановок и слов не хватает. В следующем уроке мы обсудим еще одну важную стандартную постановку. [МУЗЫКА]