Задачка про целые неотрицательные числа

vsokolov

Решаю задачку. Она, вроде бы, простая, но до правильного ответа я её не довёл. Решаю не для сдачи зачётов, а больше для души.
Извиняюсь, если где-то она здесь решалась, но я что-то подобное не находил.
Помогите, пожалуйста.
Примерная формулировка:
Сумма k целых неотрицательных чисел равна N, то есть n_1 + ... + n_k = N; n_i >=0.
Сколько всего вариантов наборов {n_1, ..., n_k} существует? Важно не только содержание набора, но и порядок, то есть, например, наборы {2,1,3} и {3,1,2} разные.
Мои рассуждения:
Можно представить наборы чисел {n_1, ..., n_k} в виде набора точек в ячейках от 0 до N, то есть в N ячейках. Самая "левая" точка в s-ой ячейке соответствует первому числу n_1 и показывает его величину, вторая точка лежит в r-ой ячейке, при этом n_2 = r-s, то есть мы откладываем величину n_2 не от нулевой ячейки, а от s-ой, где лежит первая точка. И так далее. Ясно, что последняя точка попадёт в N-ую ячейку, чтобы сумма k чисел равнялась N. То есть положение последней, k-ой, точки определено.
По сути дела, надо раскидать по (N+1) ячейке k-1 точку, причём некоторые точки спокойно могут попадать в одну ячейку, если соответствующая им величина n_i нулевая. При этом нужно избежать повторений и учесть попадание в одни ячейки.
Правильны ли рассуждения? Существует ли очент простой способ решения?
Что посоветуете?

afony

Это известная задача. Представь, что у тебя есть N+k-1 урн в которых лежат k-1 камень (не более, чем по одному в каждом). Расположение этих камней в урнах однозначно соответствует искомому набору чисел. Действительно, пусть у нас первые n_1 урн пусты, потом урна с камнем, потом n_2 пустых, потом с камнем, и т.д. Очевидно, n_1+n_2+...+n_k=N,
n_j>=0. По набору чисел расположение камней в урнах также очевидно определяется однозначно. Ну а ответ в задаче с урнами посчитать несложно - число сочетаний из N+k-1 по k-1.

stm7537641

Еще один метод "решения" -- через производящие функции (см. например соотв. книжку Ландо). Точнее, производящая функция в данном случае будет $(1-s)^{-k}.$
P.S.: гораздо более сложной задачей является подсчет числа разбиений (см. например "Введение в теорию чисел" Харди и Райта или "Теорию разбиений" Эндрюса или "Перечислительную комбинаторику" Стэнли).
Оставить комментарий
Имя или ник:
Комментарий: