Добрый день, уважаемые читатели. Сегодня я бы хотел написать этот пост, как будто это моя заметка в записную книжку. Просто, чтобы потом я смог посмотреть в своём блоге, как посчитать подсчитать количество неотрицательных целых решений неравенства вида x1 + x2 + x3 + …. + xM <= N.
Зачем вообще считать эту величину? Наверное, это кому-то нужно в каких-нибудь расчётах. Я же просто решал задачки (а-ля «спортивное программирование») на плюсах — там мне попалась эта задача.
Очевидно, что для подсчёта количества уравнений нужно знать азы комбинаторики. Ещё желательно знать английский — ведь умные дядьки, которые работают в ведущих университетах Штатов давно всё изучили и любезно описали в тех самых white papers.
Итак, что же нам нужно знать, для того чтобы посчитать подсчитать количество неотрицательных целых решений неравенства вида x1 + x2 + x3 + …. + xM <= N. Во-первых, мы должны понять, что искомое число равно числу неотрицательных целых решений Уравнения вида x1 + x2 + x3 + …. + xM + x(M+1) = N. Теперь наша задача немного видоизменилась. Но легче от этого не стало. Как же теперь посчитать это заветное число?
Всё просто. Есть принцип Stars and bars в комбинаторике. Используя этот принцип, можно получить формулу для подсчёта числа решений уравнения = C(N + M, M), где C — количество сочетаний. Это и есть наше искомое число для подсчёта числа решений неравенства
Категории: О жизни