Задача на размещения

[sa1ntdevil]

Здравствуйте, помогите, пожалуйста, решить следующую задачку:

Сколько существует способов разложить $r$ предметов по $n$ ящикам так, чтобы ровно $s$ ящиков были пустыми, если и предметы и ящики различаются.

Я решал следующим образом:
Обозначим искомую величину за $N$.
Обозначим также за $c(n, m)$ число способов разложить $m$ предметов по $n$ ящикам так, чтобы в каждом ящике был хотя бы один предмет. При $n < m$ будем иметь $c(n, m) = 0$. Условимся, что в дальнейших рассмотрениях $n \geq m$. Понятно, что $N$ - это число способов выбрать $s$ пустых ящиков, помноженное на $c(n-s,r)$
Имеем:

$$N = C_n^s \cdot c(n-s,r)$$

Чтобы найти $c(n,m)$, обозначим за $u_i(n, m)$ число размещений $n$ по $m$, в которых хотя бы $i$ ящиков пустые. Имеем:

$$u_i(n, m) = C_n^i \cdot (n-i)^m$$

По формуле включений-исключений:

$$c(n,m) = u_0(n, m) - u_1(n, m) + \ldots +(-1)^{n-1} u_{n-1}(n, m) = \sum_{i=0}^{n-1}(-1)^i u_i(n,m)$$

Итого,

$$c(n,m) = \sum_{i = 0}^{n-1} (-1)^i C_n^i \cdot (n-i)^m$$

$$N = C_n^s \cdot \sum_{i = 0}^{n-s-1} (-1)^i C_n^i \cdot (n-s-i)^r$$

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

[Хорхе]

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

(Оффтоп)

Хорхе в сообщении #502372 писал(а):

Битовую информацию всегда очень сложно запомнить.

(поэтому мне больше нравится название "число Стирлинга сюръекций")

и проще формулы для него нет.

[sa1ntdevil]

Спасибо за полезную информацию и быстрый ответ!
На самом деле в решении есть ошибка. Но ответ, действительно, правильный(правда я ошибся когда его набирал в TeX'e, так что и там в формуле ошибка).