$$\large{\displaylines{\Large {\color{#ff7800}{P_{n-1+k; \ k,n-1}=\overline{C_{n}^{k}}}} \\ \\ A=\{\underbrace{a_1,a_2,a_3,a_4}_{\color{#ff7800}n=4} \} \\ \downarrow \\ \{a_1,a_3 \} \quad (1,0,0,1,0) \\ \{\underbrace{a_2,a_2}_{\color{#ff7800}k=2} \} \quad (\underbrace{0,1,1,0,0}_{\color{#ff7800}4-1+2})}}$$

Связь числа перестановок c повторениями и числа сочетаний с повторениями

Из $(n-1+k)$ элементов двух типов

Каждому сочетанию с повторениями из $n$ по $k$ можно однозначно сопоставить упорядоченный набор из $(n-1+k)$ элементов двух типов: $1$ — элемент на данной позиции включен один раз, $0$ — «перегородка», переход к следующей позиции
По принципу биекции, число перестановок с повторениями из мультимножества $(n-1+k)$ элементов двух типов равно числу сочетаний c повторениями из $n$ по $k$

. . . комбинаторные тождества связь перестановок и сочетаний сочетание сочетание с повторениями перестановка перестановка с повторениями