Сочетания с повторениями с дополнительными условиями

Сколько существует сочетания с повторениями таких, что в них обязательно входят элементы r фиксированных типов?

Сразу возьмем по одному элементу указанного типа, и тогда уже сразу окажутся заняты r мест. Остальные k–r мест можно заполнять элементами прежних n типов.

В частности, пусть число типов n < k – числа выбранных элементов. Сколько существует сочетаний с повторениями, так что представлены хотя бы по одному все типы элементов?

Пример (эта задача задавалась на дом прошлый раз) r шаров размещаются по n ящикам. Сколько существует способов разместить их так, что пустых ящиков нет (r>n)?

РЕШЕНИЕ: пусть для разнообразия нолики – шарики, а единички – стенки ящиков (потребуется n +1 единичек). Две единички сразу кладем по краям. Теперь положим между ними шарики-нолики, а далее нужно заполнить некоторые промежутки между ними так, чтобы между любыми двумя ноликами находилась не более одной единички. Значит из r –1 промежутков между шариками нужно выбрать места для n +1–2= n –1 единичек. Всего таких способов

.