Итак, давайте напоследок докажем, наверное,
два утверждения относительно тех чисел, которые мы только что ввели.
Иначе будет тяжело.
Давайте, теорема 1.
Если можно называть это теоремой.
Ну да, конечно, а почему ж не теорема?
На том уровне знаний, на котором мы находимся, это утверждение – тоже теорема.
А то, что есть какие-то более сложные факты, ну это уж, как водится.
Начинать надо с простых.
Итак, как я и говорил, самое просто устроенная,
с точки зрения своей величины, чиселка – это A из n по k с чертой.
И она просто равна n в степени k.
То есть реальное значение гораздо короче записывается, чем обозначение для него.
Это довольно забавно.
A из n по k с чертой, а тут просто n в степени k.
Именно поэтому, в частности, в литературе, конечно,
вот эти A из n по k с чертой особо не используются.
Ну давайте докажем.
Я не говорю, что это очевидно.
Ну кому-то очевидно, а кому-то нет, так что, конечно, надо доказать.
«Д-во» – это доказательство.
Давайте посмотрим, что здесь происходит.
Итак, у нас есть некоторое множество объектов по-прежнему,
которое состоит из n штук этих самых объектов.
Давайте, как обычно, их обозначим.
И вот из этого множества мы извлекаем объекты с повторениями, с повторениями.
То есть у нас имеется вот эта самая божественная коробка,
в которой содержится бесконечно много объектов a1,
бесконечно много объектов a2 и так далее, бесконечно много объектов an.
И вот мы из нее извлекаем последовательные элементы.
Ну давайте думать, что значит извлечь такие последовательные элементы.
Так это, по сути, задача на номер автомобиля.
Задача на правила умножения.
Смотрите, на первую позицию,
на первую позицию в будущем
k-размещении с повторениями,
в будущем k-размещении с повторениями на первую
позицию, мы можем выбрать любой из этих объектов.
Мы можем выбрать любой из n объектов.
Мы можем выбрать
любой из наших n объектов.
Но ведь и на вторую позицию мы тоже можем выбрать любой из наших n объектов.
То есть...
Ну давайте я, конечно, это напишу не столь подробно, но ничего ж не меняется.
На вторую позицию в строящемся k-размещении
мы тоже можем выбрать любой из наших n объектов.
И так далее.
На k-тую позицию, на k-тую позицию
[ШУМ] мы тоже можем выбрать любой из имеющихся в нашем распоряжении объектов.
То есть, иными словами, мы составляем такой автомобильный номер,
у которого на первой позиции используется любой из объектов вот этого множества,
на второй позиции – любой из объектов вот этого множества,
на k-той позиции – любой из объектов вот этого множества.
Ну понятное дело, что мы количество таких вот номеров,
количество таких размещений с повторениями и будем вычислять как n × n ×...
× n.
И этих умножений будет ровно k штук.
То есть мы просто n умножим на себя k раз, потому что имеет место правило умножения.
А это и есть n в степени k.
То есть в этом случае доказательство теоремы совершенно элементарно.
Ну я не знаю, я надеюсь, что это было понятно.
По сути, k-размещение с повторениями – это такой номер автомобиля,
у которого на каждой позиции используется один и тот же набор объектов.
Если в реальном номере мы сначала использовали буквы, потом какие-то цифры,
потом снова буквы, то здесь тупо и здесь буквы, и тут буквы, и тут буквы,
и так на каждой позиции.
Ну букв этих n штук.
Перемножаем по следствию из правила умножения,
и получаем в аккурат n в степени k.
И давайте я вам докажу еще одну теорему.
На сегодня этого явно хватит, а то переборщим, сложно будет.
Давайте докажем еще, чему равняется A из n по k.
Я утверждаю, что A из n по k нужно вычислять вот так: это
n × (n − 1) ×...
× (n − k + 1).
Ну давайте разбираться, почему это правильно.
Видите, пока я никаких факториалов не использовал, хотя факториал и ввел.
Ничего, это сегодня появится все-таки.
То есть я докажу теорему, а потом порассуждаю немножко про факториал.
Ну доказательство у этой теоремы, друзья мои,
абсолютно такое же, конечно, как доказательство у предшествующей теоремы,
только теперь надо говорить так: на первую позицию – сейчас
будет прямо полная параллель с предыдущим доказательством,
с предыдущим рассуждением – на первую позицию в k-размещении,
в k-размещении без повторений (видите, разница в том,
что мы теперь работаем без повторов), значит, на первую позицию в k-размещении,
в k-размещении без повторений мы можем выбрать любой из объектов.
Мы можем выбрать абсолютно любой из объектов.
Ну то есть,
если угодно, когда мы составляем будущий номер такой абстрактный,
обобщенный номер автомобиля, то на первую позицию в этом номере
мы можем поставить любой из имеющихся в нашем распоряжении n объектов.
Давайте я вот здесь напишу, что количество способов такого выбора – это в точности n.
Но когда мы переходим на вторую позицию,
ведь мы на первой позиции уже какой-то объект зафиксировали,
но размещение, которое мы хотим построить, оно ведь не допускает повторений.
Поэтому когда мы будем ставить какой-то объект на вторую позицию,
мы ни в коем случае не сможем использовать вот тот единственный объект,
который уже стоит на первой позиции.
Поэтому здесь все-таки надо сказать аккуратнее.
На вторую позицию, на вторую позицию
в строящемся k-размещении,
размещении без повторений мы не можем
взять тот объект, который уже стоит на первой позиции,
и потому мы можем выбрать любой из оставшихся (n − 1) объектов.
Мы можем выбрать,
можем выбрать любой из оставшихся
в нашем распоряжении – после того, как мы зафиксировали первый объект
– любой из оставшихся (n − 1) объектов.
И дальше, естественно, происходит абсолютно
тоже самое: когда мы выбираем объект на третью позицию, мы уже помним,
что мы зафиксировали некоторый объект на первой позиции,
некоторый отличающийся от него объект – на второй позиции.
Соответственно, на третью позицию у нас есть вариантов выбора сколько?
Только, конечно же, (n − 2).
А теперь смотрите, вот так, чтобы было предельно понятно.
На первую позицию у нас есть n вариантов выбора.
На вторую позицию у нас уже есть (n − 1).
Смотрите, 2 – вторая позиция, но (n − 1).
На третью позицию (три!) (n − 2) варианта
выбора; на четвертую (четыре!) – (n − 3); на пятую
– (n − 4); на шестую – (n − 5); на k-тую – разумеется, (n − k + 1).
Я надеюсь, что в такой последовательности изложения это должно быть понятно.
Соответственно, пользуемся правилом умножения, тем же самым,
ну вот в таком немножко видоизмененном варианте.
То есть теперь у нас номер не может состоять из одинаковых букв.
Он обязан состоять из разных букв.
Все буквы должны быть разными.
И правило умножения дает нам, как следствие, ровно то, что было заявлено.
Сначала у нас есть n вариантов выбора, вслед за ними (n − 1),
последовательность, по правилу умножения, можно составить n × (n − 1) способами,
дальше (n − 2) – это когда мы третий объект устанавливаем на свою позицию,
и так вплоть до k-того объекта, который дает сомножитель (n − k + 1).
И теорема 2 доказана полностью.
Теперь давайте небольшие комментарии в терминах
пресловутых факториалов сделаем и на этом сегодняшнюю лекцию завершим.
Ну смотрите, вот здесь написано такое произведение: n × (n − 1) ...