Давайте введём стандартные обозначения, которые в этом месте возникают. Значит, для k-сочетаний с повторениями — это самый важный, на самом деле, момент — вводится обозначение, которое читается как C из n по k. Давайте я даже напишу, наверное, здесь, потому что очень важно создавать культуру правильного прочтения этого символа, потому что люди даже очень грамотные, даже очень сильные зачастую неправильно его произносят. Это обидно. Значит, «це из n по k», именно из n по k, то есть мы из n объектов выбираем k, из n по k. Вот, C из n по k — это обозначение, которое восходит, на самом деле, к Паскалю, к одному из классиков современной комбинаторики и теории вероятностей, который трудился, слава богу, уже почти 400 лет назад. И французы очень чтят это обозначение, но в современной международной комбинаторике, в серьёзных журналах, в которых публикуются статьи, особенно на Западе вот это обозначение если не забыто, то, по крайней мере, не общепринято. Я буду всегда использовать его. В нашей российской литературе оно по-прежнему имеет очень большую силу, но есть другое обозначение, которое, повторяю, используется в международных журналах, и оно немножко путает, конечно, слушателей, потому что здесь n расположено сверху над k, такие вот скобочки, n сверху, k снизу. Смысл тот же самый — это количество всех возможных k-сочетаний без повторений, которые можно выбрать, имея на руках n различных объектов. Вот, но вот некоторая путаница, видите. Читается это уже не «C из n по k». Если по-английски, например, говорить, то это читается «n choose k», то есть из n выбираем k, но по-прежнему из n, естественно, выбираем k. Ну, хорошо, это я уже занудил немножко. Давайте, k-размещение без повторений — стандартное обозначение A из n по k. Поскольку на самом деле, как мы увидим позже, всё по большому счёту выражается через C из n по k, вот эти все градации и их обозначение уже не столь важны для литературы, и, соответственно, в международной литературе просто обычно не используют никакого стандартного обозначения для этой величины, а для нашего удобства, ну, вот я ввожу A из n по k, чтобы просто потом можно было доказывать теоремы. Вот, соответственно, если возникают повторения, то мы обычно рисуем чёрточку над символом, который выражает соответствующее количество без повторов. То есть тут получается C из n по k с чертой, и тут, соответственно, A из n по k с чертой. Но читается всё время одинаково: A из n по k, C из n по k с чертой, A из n по k с чертой, то есть так же точно, как читалось C из n по k, число сочетаний. Вот, такие вот имеются обозначения. Но, интересно, а чему же они на самом деле равны, как их выразить? А для того чтобы из выразить, давайте введём такую функцию, которая в математике называется факториалом. Это нам полезно будет для дальнейшего. Ну и, наверное, на сегодня мы докажем пару простейших утверждений, которые касаются этих величин, а более сложные мы оставим напоследок, на будущее. Так. Давайте введём функцию факториал. Вот эта штука называется факториал. Надеюсь, что большинство, конечно, знает, что это такое, но я всё-таки напомню. На самом деле, определять надо аккуратно так: 0! — это просто некое соглашение, это, по определению, 1. 0! по определению равен 1. 1! тоже по определению равен 1, а в общем случае n! — это есть (n – 1)!, который мы уже определили, так сказать, на предыдущих шагах определения, помноженный на n. То есть по большому счёту, если говорить совершенно простыми и понятными словами, n! — это просто произведение всех чисел от 1 до n. Но в случае, когда мы говорим про 1!, ну, непонятно, что значит произведение всех чисел от 1 до 1. Ну, это сама же 1, ни на кого не умножаемая. 0! — это вообще удобное соглашение, и мы скоро обсудим, почему оно удобно. Соответственно, n! — это действительно произведение уже чисел от 1 до n, скажем, 10! — это 1 * 2 * ..., * 10. Если посчитаете, будет что-то типа 3628800. Это очень быстро растущая функция, как она растёт мы обсудим несколько позже, это само по себе очень интересно, но вот некоторым образом факториал сейчас будет связан с тем, как посчитать вот эти вот основные комбинаторные величины. Но начнём мы не с тех величин, которые считаются с помощью факториала, а, наверное, с более простой. И как ни странно, товарищи, вот это вот очень забавно: самая простая с точки зрения подсчёта своего величина — вот эта вот, несмотря на то, что она обозначена, грубо говоря, наиболее громоздким образом – A из n по k с чертой. Ну, вот сейчас мы докажем про неё некую теорему, посчитаем ее очень легко.
