Найти значение суммы

[DrVirogov]

вот такой:

$$S(k,n)= \sum_{i_1+i_2+\cdots+i_k=n}1^{i_1}2^{i_2}\cdots k^{i_k} $$

[EtCetera]

Очевидны следующие соотношения:

$$S(1,n)=1$$

$$S(k,\kappa)=0,\ 1\le\kappa<k$$

$$S(n,n)=n!$$

$$S(k,n)=\sum\limits_{i=1}^{n-k+1}S(k-1,n-i)k^i$$

С помощью первого и последнего соотношений можно установить вид зависимости $S(k,n)$ от $n$ при небольших $k$. Общий вид зависимости будет таким:

$$S(k,n)=\sum\limits_{j=1}^k(-1)^{k-j}\binom{k}{j}j^n$$

(Отдаленное подобие доказательства)

Для доказательства преобразуем это выражение:

$$\sum\limits_{j=1}^k(-1)^{k-j}\binom{k}{j}j^n=\sum\limits_{j=1}^k(-1)^{k-j}\binom{k}{j}\left.\left(e^{jx}\right)^{(n)}\right|_{x=0}=(-1)^k\left.\left(\sum\limits_{j=1}^k\binom{k}{j}\left(-e^{x}\right)^j\right)^{(n)}\right|_{x=0}=$$$$=(-1)^k\left.\left(\left(1-e^{x}\right)^k-1\right)^{(n)}\right|_{x=0}$$

Полученное выражение удовлетворяет второму и третьему соотношениям (всего $k$ равенств для фиксации $k$ неизвестных коэффициентов при $j^n$, $1\le j\le k$), что проверяется с помощью формулы Лейбница для функций $e^x$ и $1-e^x$.

Не знаю, можно ли получить формулу в (еще более) замкнутом виде.

[DrVirogov]

Наверное, Вы что-то недопоняли. Соотнощения не очевидны, а неверны.

$$S(k,1)=1+2+\cdots +k\ne 0$$

$$S(2,2)=1^02^2+1^12^1+1^22^0=7\ne 2!$$

Что считать замкнутой формой, зависит от соглашения. Предполагется, что ответ будет дан в виде простой формулы, в которую входят общеизвестные последовательности.

[nnosipov]

DrVirogov в сообщении #676297 писал(а):

Наверное, Вы что-то недопоняли. Соотнощения не очевидны, а неверны.

Верны, если считать индексы $i_j$ натуральными. Вам нужно было явно оговорить в условии задачи, что их следует считать целыми неотрицательными. Телепатов здесь нет.

[Руст]

Очевидно, что

$$S(k,n)=S(k-1,n)+kS(k,n-1).$$

Кажется числа Стирлинга удовлетворяют этим соотношениям.

[EtCetera]

Если нули допускаются, то рекурсивное выражение $S(k,n)$ принимает следующий вид:

$$S(1,n)=1$$

$$S(k,n)=\sum\limits_{i=0}^{n}S(k-1,n-i)k^i,\ k>1$$

Общий вид зависимости $S(k,n)$ будет таким:

$$S(k,n)=\dfrac{1}{(k-1)!}\sum\limits_{j=1}^k(-1)^{k-j}\binom{k-1}{j-1}j^{n+k-1}$$

Это легко проверяется подстановкой в рекурсивное выражение.

Upd. Но

$$\dfrac{1}{(k-1)!}\sum\limits_{j=1}^k(-1)^{k-j}\binom{k-1}{j-1}j^{n+k-1}=\dfrac{1}{k!}\sum\limits_{j=0}^k(-1)^{k-j}\binom{k}{j}j^{n+k}=\left\{\begin{matrix}n+k\\k\end{matrix}\right\}$$

Т.е. это действительно числа Стирлинга второго рода.

[DrVirogov]

Отпираться бесполезно - это так и есть!
Зная, что $S(k,n)=\left\{\begin{matrix}n+k\\k\end{matrix}\right\}$ можно дать простое комбинаторное доказательство, исходя из того,что числа Стирлинга второго рода дают количество неупорядоченных разбиений n-элементного множества на k непустых подмножеств.