Нужен ли тут метод математической индукции?

[Mr. Dred]

Здравствуйте.
Рассмотрим абстрактный объект называемый строем знаковой цепи
Пусть у нас есть знаковая цепь cabbabcba. Под строем будем понимать соответствующей ей кортеж натуральных чисел где каждый компонент цепи заменен на некоторое натуральное число. Первый компонент цепи (в данном случае это 'c') заменяем на 1, второй компонент также на единицу если он совпадает с первым или 2 если он отличен от первого, и так далее. Таким образом алфавит произвольной цепи заменяется на алфавит натуральных чисел. Для цепи cabbabcba соответственно $<c,a,b>\to<1,2,3>$
Строй цепи cabbabcba будет выглядеть: 123323132.

Строй цепи сообщений – это кортеж (упорядоченное множество), в котором каждому компоненту данной цепи в соответствие поставлено натуральное число, причем идентичные по выбранному признаку компоненты отображены одним и тем же числом. Самый первый компонент такого кортежа – единица, а все остальные первые встречные разные натуральные числа (представляющие вместе с единицей алфавит строя) возрастают на единицу

Рассмотрим задачу генерации всех разных строев для цепей длинной $n$ с алфавитом мощностью $n$
при $n=3$ получим следующую последовательность строев:
111
112
121
122
123

Несложно увидеть что между строями и разбиениями множества мощностью $n$ существует взаимо-однозначное соответствие:
$111\to{a,b,c}$
$112\to{a,b}{c}$
$121\to{a,c}{b}$
$122\to{a}{b,c}$
$123\to{a}{b}{c}$

Возникает вопрос, нужно ли доказывать это взаимооднозначное соответствие, и как подступится к доказательству. Первое что приходит в голову - метод математической индукции.

[Sonic86]

Mr. Dred в сообщении #472764 писал(а):

Несложно увидеть что между строями и разбиениями множества мощностью $n$ существует взаимо-однозначное соответствие:
$111\to{a,b,c}$
$112\to{a,b}{c}$
$121\to{a,c}{b}$
$122\to{a}{b,c}$
$123\to{a}{b}{c}$
Возникает вопрос, нужно ли доказывать это взаимооднозначное соответствие, и как подступится к доказательству. Первое что приходит в голову - метод математической индукции.

фигурные скобки предваряются слешем: $\{ x\}$
Тут нечего доказывать, все ясно: берем любое разбиение множества и ставим его однозначным образом строй цепи. И обратно: каждому строю цепи ставим в соответствие одно разбиение. И все.

[Mr. Dred]

Тоесть на примере одного частного случае можно говорить что это отображение биективно?

[Sonic86]

Mr. Dred в сообщении #472872 писал(а):

Тоесть на примере одного частного случае можно говорить что это отображение биективно?

Почему?! Я же говорю: берем разбиение множества (произвольное разбиение для произвольного $n$) и ставим ему в соответствие однозначно строй цепи. И обратно: берем любую цепь (произвольного устройства произвольной длины) и ставим ей в соответствие разбиение множества. Все. Нет никаких частных случаев.