В задаче на комбинаторику: сколько разных неубывающих последовательностей длины k из чисел 1..n; сравните подходы "звёздочки и черточки" и использование биномиальных коэффициентов, объясните, как формула меняется при ограничениях на повторения
В задаче на комбинаторику: сколько разных неубывающих последовательностей длины k из чисел 1..n; сравните подходы "звёздочки и черточки" и использование биномиальных коэффициентов, объясните, как формула меняется при ограничениях на повторения
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
(n+k−1k). \binom{n+k-1}{k}.
(kn+k−1 ).
Два объяснения (эквивалентны):
- «Звёздочки и черточки»: представьте kkk звёздочек (элементы) и n−1n-1n−1 черточек (разделители между значениями). Всего n+k−1n+k-1n+k−1 позиций, выбираем где будут, например, kkk звёздочек: (n+k−1k)\binom{n+k-1}{k}(kn+k−1 ).
- Биномиальный/мультимножество: это число kkk-мультимножеств из nnn типов, равно (n+k−1k)\binom{n+k-1}{k}(kn+k−1 ).
Как меняется при ограничениях на повторения:
- Запрещены повторы (строго возрастающая последовательность): нужно выбрать kkk различных чисел и упорядочить их единственным способом, ответ
(nk)(при k≤n, иначе 0). \binom{n}{k}\quad(\text{при }k\le n,\ \text{иначе }0).
(kn )(при k≤n, иначе 0). - Каждое значение появляется как минимум один раз (xi≥1x_i\ge1xi ≥1): число решений x1+⋯+xn=k, xi≥1x_1+\dots+x_n=k,\ x_i\ge1x1 +⋯+xn =k, xi ≥1 равно
(k−1n−1)(при k≥n, иначе 0). \binom{k-1}{n-1}\quad(\text{при }k\ge n,\ \text{иначе }0).
(n−1k−1 )(при k≥n, иначе 0). - Ограничение «каждое значение не более ttt раз» (0≤xi≤t0\le x_i\le t0≤xi ≤t): можно использовать порождающую функцию — искомое равно коэффициенту при zkz^kzk в (1+z+⋯+zt)n(1+z+\dots+z^t)^n(1+z+⋯+zt)n, или дать явную формулу через включение-исключение:
∑j=0⌊kt+1⌋(−1)j(nj)(n+k−1−j(t+1)k−j(t+1)). \sum_{j=0}^{\left\lfloor\frac{k}{t+1}\right\rfloor}(-1)^j\binom{n}{j}\binom{n+k-1-j(t+1)}{k-j(t+1)}.
j=0∑⌊t+1k ⌋ (−1)j(jn )(k−j(t+1)n+k−1−j(t+1) ).
Эти формулы получаются из модели с кратностями xix_ixi и стандартных приёмов (звёздочки-черточки, включение–исключение, порождающие функции).