Подсчитайте способы раздать m предметов среди n человек

Даны m и n, представляющие количество манго и количество людей соответственно. Задача состоит в том, чтобы подсчитать количество способов раздать m манго среди n человек. Рассматривая обе переменные m и n, мы приходим к 4 типичным случаям использования, в которых манго и люди считаются:
1) Оба идентичны
2) Уникальные и идентичные соответственно
3) Идентичные и уникальные соответственно
4) Оба уникальных
Предпосылки: биномиальный коэффициент | Перестановка и комбинация

Случай 1: Раздача m одинаковых манго n одинаковым людям
Если мы попытаемся разложить m манго подряд, наша цель - разделить эти m манго между n людьми, сидящими где-то между этими манго. Все, что нам нужно сделать, это объединить эти m манго в n наборов, чтобы каждый из этих n наборов можно было распределить между n людьми соответственно.
Чтобы выполнить указанную выше задачу, нам нужно разделить начальное расположение манго с помощью n-1 разделителей, чтобы создать n наборов манго. В этом случае нам нужно собрать вместе m манго и n-1 разделителей. Итак, нам нужно способы вычислить наш ответ.
Приведенная ниже иллюстрация представляет собой пример (способ) расположения разделов, созданных после размещения 3-х разделителей, а именно P1, P2, P3, которые разделили все 7 манго на 4 разных раздела, чтобы 4 человека могли иметь свою собственную часть соответствующего раздела:

Поскольку все манго считаются одинаковыми, мы делим к чтобы вычесть повторяющиеся записи. Точно так же мы снова разделим приведенное выше выражение на потому что все люди тоже считаются идентичными.
Окончательное выражение, которое мы получаем:
Вышеприведенное выражение фактически равно биномиальному коэффициенту:
Пример:

 Ввод: m = 3, n = 2
Выход: 4
Есть четыре способа
3 + 0, 1 + 2, 2 + 1 и 0 + 3 

Ввод: m = 13, n = 6.
Выход: 8568

Ввод: m = 11, n = 3.
Выход: 78

Выход:

 330

Сложность времени: O (n)
Вспомогательное пространство: O (1)
Случай 2: Раздача m уникальных манго среди n одинаковых людей
В этом случае, чтобы вычислить количество способов раздать m уникальных манго среди n одинаковых людей, нам просто нужно умножить последнее выражение мы вычислили в случае 1 по .
Итак, наше окончательное выражение для этого случая:
Доказательство:
В случае 1 изначально мы получили выражение без удаления повторяющихся записей.
В этом случае нам нужно только разделить ведь все манго в этом случае считаются уникальными.
Итак, мы получаем выражение как:
Умножая числитель и знаменатель на ,
мы получаем
Где ===
Сложность времени: O (max (n, m))
Вспомогательное пространство: O (1)
Случай 3: Раздача m одинаковых манго среди n уникальных людей
В этом случае, чтобы вычислить количество способов раздать m одинаковых манго среди n уникальных людей, нам просто нужно умножить последнее выражение мы вычислили в случае 1 по .
Итак, наше окончательное выражение для этого случая:
Доказательство:
Это доказательство очень похоже на доказательство выражения последнего случая.
В случае 1 изначально мы получили выражение без удаления повторяющихся записей.
В этом случае нам нужно только разделить ведь в этом случае все люди считаются уникальными.
Итак, мы получаем выражение как:
Умножая числитель и знаменатель на ,
мы получаем
Где ===
Сложность времени: O (n)
Вспомогательное пространство: O (1)
Для справки о том, как рассчитать см. здесь факториал числа
Пример 4: Раздача m уникальных манго среди n уникальных людей
В этом случае нам нужно умножить выражение, полученное в случае 1, на оба а также .
Доказательства для обоих умножений определены для случая 2 и случая 3.
Следовательно, в этом случае наше окончательное выражение оказывается
Сложность времени: O (n + m)
Вспомогательное пространство: O (1)

Вниманию читателя! Не прекращайте учиться сейчас. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .