Число невозрастающих наборов

[Otta]

Обобщение попавшейся задачи.
Посчитаем упорядоченные наборы $\ (a_1,\ldots, a_n)$ длины $n$,
каждый элемент может иметь натуральное значение от $1$ до $k$.
Каково количество невозрастающих наборов? $a_1\ge\cdots \ge a_n$

Мне эта задача понадобилась при малых $n, k$, проще было посчитать вручную. Но стало интересно, есть ли какая идея в общем случае. Пока кроме числа сочетаний с повторениями ничего в голову не идет, но до конца не додумала.

[iifat]

До конца как-то тоже не додумал, но.
Психологически мне как-то легче думать о возрастающих наборах.
Дописываем справа $a_{n+1}=k$.
Представляем себе набор как $n+1$ столбиков кубиков. Строим его таким образом: берём начальный набор один столбик из одного кубика. Производим действия а) положить кубик на последний столбик и б) сдублировать последний столбик вправо. Действий а) будет $k-1$, действий б) $n$, порядок любой. Помнится, формула несложная.

[vpb]

Это, несомненно, число мономов степени $n$ от $k$ переменных. Каковое, как известно, равно

$$n+k-1\choose k-1$$

-- 09.11.2020, 03:07 --

Otta в сообщении #1491284 писал(а):

Пока кроме числа сочетаний с повторениями ничего в голову не идет, но до конца не додумала.

Да, это и есть сочетания с повторениями.

[Otta]

Самое забавное, я ж даже и решала через диофантовы уравнения, в каком месте меня тупануло - фиг знает теперь. Явно на каком-то ровном месте )
Спасибо.

[vpb]

Пожалуйста.

[Padawan]

Поставить $n$ перегородок между числами от $k$ до $1$ ($a_i$ равно числу слева от $i$-той перегородки). То есть сколькими способами можно упорядочить $k$ предметов и $n$ перегородок, если на первом месте должен стоять предмет. Получается $C_{k+n-1}^{n}$