Сочетания с повторениями: сколькими способами выбрать k конфет n сортов?
В магазине n сортов конфет, нужно купить k штук, конфеты одного сорта неотличимы, сортов каждого можно брать сколько угодно (запас неограничен). Порядок покупки не важен. Сколькими способами это сделать? Это ведь не обычное C(n,k)?
2 ответа
Это сочетания с повторениями (мультимножества). Ответ:
C̄(n, k) = C(n + k − 1, k) = C(n + k − 1, n − 1).
Обоснование — те же «звёзды и палочки»: пусть x_i — сколько взяли сорта i, тогда x_1+...+x_n = k в неотрицательных целых, а число таких решений = C(n+k−1, k). Иначе: кодируем покупку строкой из k звёздочек и (n−1) палочек-разделителей между сортами; выбираем позиции для k звёздочек среди n+k−1 символов.
// через предподсчитанные fact, inv_fact mod p
long long C(int n, int k){ if(k<0||k>n)return 0; return fact[n]*inv_fact[k]%MOD*inv_fact[n-k]%MOD; }
long long multichoose(int n, int k) { // выбрать k из n сортов с повторениями
return C(n + k - 1, k);
}
O(1) на запрос после предподсчёта. Сравни с обычными сочетаниями C(n,k) — там БЕЗ повторений (каждый сорт максимум раз). Повторения «раздувают» n до n+k−1.
Частая ловушка — спутать с упорядоченным выбором. Если бы порядок покупки был важен (последовательность из k покупок, каждая — один из n сортов), ответ был бы n^k. Сочетания с повторениями — именно про НЕупорядоченный мультимножественный выбор. Если на каждый сорт есть верхняя граница запаса, простой формулы нет — добавляется включение-исключение по сортам, превысившим лимит.