Перестановки с повторениями и без повторений.

[Solaris86]

Не могу понять логику перестановок.
Допустим, есть множество $E = \lbrace {1,2,3} \rbrace$
Задачи:
1) сколькими способами можно выбрать 1 элемент множества? Ответ: 3, то есть $A^1_3 = \overline {A^1_3} = C^1_3 = \overline {C^1_3} = 3$;
2) сколькими способами можно выбрать 2 элемента множества, при этом:
а) порядок имеет значение:
1) с повторами? Ответ: 9, то есть $\overline {A^2_3} = 9$;
2) без повторов? Ответ: 6, то есть $A^2_3 = 6$;
б) порядок не имеет значения:
1) с повторами? Ответ: 6, то есть $\overline {C^2_3} = 6$;
2) без повторов? Ответ: 3, то есть $C^2_3 = 3$;
3) сколькими способами можно выбрать 3 элемента множества, при этом:
а) порядок имеет значение:
1) с повторами? Ответ: 27, то есть $\overline {A^3_3} = 27$;
2) без повторов? Ответ: 6, то есть $A^3_3 = 6$;
б) порядок не имеет значения:
1) с повторами? Ответ: 10, то есть $\overline {C^3_3} = 10$;
2) без повторов? Ответ: 1, то есть $C^3_3 = 1$.
С размещениями и сочетаниями всё ясно.
Вот перестановки остаются загадкой...
Если следовать логике перестановок, то для них важен порядок, то есть перестановки - это некая разновидность размещений.
Перестановки без повторов тогда становятся понятны: $P_n = A^n_n$. В нашем случае: $P_3 = A^3_3 = 6$.
А вот перестановки с повторами вообще перестают быть понятны, откуда они такие взялись. По логике ведь должно быть тогда: $\overline{P_n} = \overline{A^n_n}$. В нашем случае: $\overline{P_3} = \overline{A^3_3} = 27$.
Но формула перестановок с повторами не даёт этот результата, она вообще разительно отличатся от всех формул.
Помогите разобраться.

[arseniiv]

Solaris86 в сообщении #1404169 писал(а):

Перестановки без повторов тогда становятся понятны: $P_n = A^n_n$.

Да, так и есть. Перестановка — это просто размещение всего что есть.

Solaris86 в сообщении #1404169 писал(а):

Но формула перестановок с повторами не даёт этот результата, она вообще разительно отличатся от всех формул.

Под перестановками с повторениями понимаются обычно перестановки мультимножества — и «без повторений», то есть без лишних повторений: если в мультимножестве $m$ копий некоторого элемента, то в перестановке тоже должно быть $m$. Потому число перестановок с повторениями зависит от количеств каждого элемента, а не от одного числа.

Знаете что такое мультимножество?

-- Вт июл 09, 2019 21:06:44 --

(О сочетаниях и размещениях из мультимножества — «без повторений», ибо «с повторениями» будет уже не важно, сколько раз кто там попадается, и случай не будет отличаться от случая для множества — тоже можно говорить. Там количества повторений элементов в конфигурациях ограничиваются теми, сколько их в исходном мультимножестве, и больше выбирать нельзя.)

[Solaris86]

Solaris86 в сообщении #1404169 писал(а):

А вот перестановки с повторами вообще перестают быть понятны, откуда они такие взялись. По логике ведь должно быть тогда: $\overline{P_n} = \overline{A^n_n}$. В нашем случае: $\overline{P_3} = \overline{A^3_3} = 27$.
Но формула перестановок с повторами не даёт этот результата, она вообще разительно отличатся от всех формул.

Я тут предположил:
$\overline{P_3} = \overline{P_3(0,0,3)} + \overline{P_3(0,1,2)} + \overline{P_3(0,2,1)} + \overline{P_3(0,3,0)} + \overline{P_3(1,0,2)} + \overline{P_3(1,1,1)} + \overline{P_3(1,2,0)} + \overline{P_3(2,0,1)} + \overline{P_3(2,1,0)} + \overline{P_3(3,0,0)} = 1 + 3 + 3 + 1 + 3 + 6 + 3 + 3 + 3 + 1 = 27 = \overline{A^3_3}$.
Задача как бы разбилась на подзадачи. Пример для $\overline{P_3(0,0,3)}$: сколькими способами можно выбрать 3 элемента множества, при этом порядок имеет значение, с повторами, причём первый элемент множества повторяется 0 раз, второй элемент множества - 0 раз, третий элемент множества - 3 раза.
$\overline{P_3}$ при этом - это как бы общее количество всех возможных перестановок с повторами.
Это верно?

-- 09.07.2019, 20:00 --

arseniiv в сообщении #1404174 писал(а):

Под перестановками с повторениями понимаются обычно перестановки мультимножества — и «без повторений», то есть без лишних повторений: если в мультимножестве $m$ копий некоторого элемента, то в перестановке тоже должно быть $m$. Потому число перестановок с повторениями зависит от количеств каждого элемента, а не от одного числа.

Знаете что такое мультимножество?

Нет, это для меня сложновато.

[arseniiv]

Solaris86 в сообщении #1404179 писал(а):

Это верно?

Ага. Но учтите, что с повторениями мы можем в общем случае выбрать сколь угодно много элементов, в отличие от случая без повторений, и потому $\overline P_n$ (без скобок) никак особо не выделено в отличие от $P_n$.

А мультимножества просты и для комбинаторики полезны. Сочетания с повторениями — это как раз мультимножества (а сочетания без повторений — обычные множества). Сейчас я вам их определю.

В множество некий элемент может входить или не входить. В мультимножество же элементы входят некоторое неотрицательное целое число раз. Формально можно мультимножество, состоящее из элементов некоторого множества $A$, определить как функцию $M\colon A\to\mathbb N$, и значение её на каком-то элементе, $M(a)$, будет равно числу его вхождений в это мультимножество. Записывают мультимножества перечислением элементов обычно как множества, но имеют в виду и кратность каждого элемента: $\{1,1,1,3,8,8\}$ — сюда, если мы понимаем запись как мультимножество, 1 входит три раза, 3 один раз, 8 два раза и всё остальное 0 раз. (Есть обозначения, которые не перепутаешь, но у разных авторов они разные.)

Мультимножества можно так же объединять, пересекать, вычитать как множества, а ещё складывать — как новую полезную операцию:

$$\begin{aligned} (M_1\cup M_2)(a) &:= \max(M_1(a), M_2(a)), \\ (M_1\cap M_2)(a) &:= \min(M_1(a), M_2(a)), \\ (M_1\setminus M_2)(a) &:= \max(M_1(a) - M_2(a), 0), \\ (M_1\uplus M_2)(a) &:= M_1(a) + M_2(a). \end{aligned}$$

Одно мм. является подмножеством другого мм., если в него каждый элемент входит не большее число раз:

$$M_1\subset M_2 :\Leftrightarrow \forall a\in A.\; M_1(a)\leqslant M_2(a).$$

Мощность тоже можно определить: просто учитывать кратности элементов, так что

$$|M| := \sum_{a\in A} M(a).$$

Если считать множества частным случаем мм. (где каждый элемент входит не больше раза), ${\cup},{\cap},{\setminus},{\subset},|{\cdot}|$ будут вести себя как и полагается.

Теперь может быть видно, что сочетания с повторениями удобно представлять мультимножествами — нам ведь тут не важен порядок: $\{3,3,4\}=\{3,4,3\}$ — но важен «состав», кратности: $\{3,3,4\}\ne\{3,4,4,4\}$.

И теперь мы можем расширить определения обычных сочетаний, размещений, перестановок для мультимножеств:
• Сочетание — это подмножество мультимножества. Объём сочетания — это его мощность.
• Размещение — это кортеж, в который каждый элемент входит не больше раз, чем его кратность в мм..
• Перестановка — это как обычно размещение наибольшего возможного объёма (то есть объёма $|M|$).

И $\overline P(n_1,\ldots,n_k)$ — это в результате просто $P\{1_{(n_1\text{ раз})},\ldots,k_{(n_k\text{ раз})}\}$. Попробуйте как-нибудь потом посчитать числа сочетаний и размещений элементов мультимножества (то есть они тоже должны будут зависеть от некоторого набора кратностей $n_1,\ldots,n_k$).