Мейси wrote: ↑Jul 8, '20, 17:08
- почему у элементов x индекс i1, i2, а не просто 1,2 и тп
Индекс i это идентификатор каждого из возможных упорядоченных наборов (или, иначе говоря, размещений).
Если, допустим, возможны 99 размещений из k элементов, то они выглядели бы так:
Размещение 1: {Х
11, Х
12,Х
13,...,Х
1k}
(идентификатор =1, то есть речь идет о разных элементах "x" в количестве k штук, принадлежащих набору номер 1 (так как i=1))
Размещение 2, аналогично: {x
21,x
22,x
23,...,x
2k}
Размещение 3: {x
31,
32,
33,...,x
3k}
....
Размещение 99: {x
991,x
992,
993,....,x
99k}
- объясните кто-нибудь человеческим языком, почему при добавлении элемента Xik+1 у нас образуется именно n-k размещений, а не n. Интуиция мне подсказывает, что если сделать их по n, то будут повторы, но я не понимаю, почему. Это как раз та ситуация, когда без примера для меня вся эта конструкция неосязаемая, и я не понимаю ее закономерностей.
Сначала пример.
Допустим, вначале n=4, k=1 (то есть у меня есть размещение по 1 элементу из множества, состоящего из 4 элементов).
Значит, у меня есть такие 4 набора (или 4 размещения):
{1}
{2}
{3}
{4}
Теперь, перефразируя текст доказательства под мой пример, и пися более человеческим языком, можно сказать так:
"Можно взять из этого примера каждое размещение по 1 элементу, т.е. каждую упорядоченную группу по 1 элементу, и добавить в каждое из этих размещений по одному из каких-нибудь еще не входящих в него элементов Xi
k+1 (а таких элементов всего n-k, то есть 3). Таким образом из каждого из этих 4-х размещений можно получить n-k (то есть 3) размещения по k+1 элементам (то есть по факту уже из 2 элементов) вида {xi1, xi2}.
Например, было размещение {1}, и из него теперь можно получить 3 (или n-k) размещения: {1,2}, {1,3}, {1,4}
Получить из этого размещения (то есть из {1}) больше размещений, в том числе n размещений, не получается по определению. Ведь я хочу получить размещения добавлением еще не входивших туда элементов. А элемент "1" уже входил в это размещение {1}. Остается выбор только из еще не входивших элементов, а это только элементы "2", "3", "4", и их количество равно n-k.
Теперь, если продолжить эту логику, то есть добавить по одному еще не входившему элементу в каждое из 4-х размещений моего примера (то есть в каждое из {1}, {2}, {3}, {4}), то у меня получится, что n=4, k=2 (то есть я получу размещения по 2 элементам из 4).
И в итоге у меня получатся такие 12 наборов (или 12 размещений):
{1,2}
{2,3}
{3,4}
{4,1}
{4,2}
{4,3}
{1,3}
{1,4}
{2,4}
{3,2}
{3,1}
{2,1}
И из каждого из 4-х первоначальных наборов из 1 элемента у меня таким образом получилось по 3 набора (n-k) из 2 элементов. Вот их и стало 12. И причем каждый раз это действительно были неповторяющиеся, уникальные наборы (в формулировке Кудрявцева это звучит как "причем таким образом получаются все размещения по k+1 элементов и точно по одному разу").
Из каждого из 12 наборов по 2 элементам можно получить наборы по 3 элементам, и как и предсказывает формула из примера Кудрявцева (n-k), из каждого такого набора получится по 2 набора (n-k = 4-2=2).
И опять же, каждый из получившихся 24 наборов будет уникальным.