Комбинаторный кейс: приведите разные стратегии подсчета числа способов выбрать комитет из n человек с условием, что в комитете обязательно присутствует хотя бы один представитель заданной подгруппы, и объясните, когда используют принцип включения-исключения
Комбинаторный кейс: приведите разные стратегии подсчета числа способов выбрать комитет из n человек с условием, что в комитете обязательно присутствует хотя бы один представитель заданной подгруппы, и объясните, когда используют принцип включения-исключения
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
1) Принцип дополнения (самый простой). Считаем все комитеты и вычитаем те, в которых нет ни одного из подгруппы:
#=(Nk)−(N−mk). \#=\binom{N}{k}-\binom{N-m}{k}.
#=(kN )−(kN−m ). Пояснение: (Nk)\binom{N}{k}(kN ) — все выборы, (N−mk)\binom{N-m}{k}(kN−m ) — выборы только из остальных N−mN-mN−m человек.
2) Прямой подсчёт по числу представителей из подгруппы. Перебираем iii — сколько человек взяли из подгруппы (1≤i≤min(m,k)1\le i\le\min(m,k)1≤i≤min(m,k)):
#=∑i=1min(m,k)(mi)(N−m k−i ). \#=\sum_{i=1}^{\min(m,k)}\binom{m}{i}\binom{N-m}{\,k-i\,}.
#=i=1∑min(m,k) (im )(k−iN−m ). Пояснение: выбрать iii из подгруппы и k−ik-ik−i из остальных. Эта формула равносильна формуле из пункта 1 по биномиальным тождествам.
3) Принцип включения‑исключения (обобщение и случай пересечений). Если условие шире — например, требуется хотя бы по одному представителю из нескольких подгрупп A1,…,ArA_1,\dots,A_rA1 ,…,Ar (они могут пересекаться) — применяют включение‑исключение. Обозначим событие EiE_iEi : комитет не содержит представителей AiA_iAi . Тогда число комитетов, пересекающих каждую AiA_iAi , равно
#=∑X⊆{1,…,r}(−1)∣X∣( N− ∣⋃i∈XAi∣ k ), \#=\sum_{X\subseteq\{1,\dots,r\}}(-1)^{|X|}\binom{\,N-\,\bigl|\bigcup_{i\in X}A_i\bigr|\,}{\,k\,},
#=X⊆{1,…,r}∑ (−1)∣X∣(kN− ⋃i∈X Ai ), где для пустого XXX член даёт (Nk)\binom{N}{k}(kN ).
Когда использовать включение‑исключение: когда несколько «хотя бы одного» требований (по каждой из нескольких подгрупп) и подгруппы пересекаются либо накладываются так, что простое вычитание/прямой перебор даёт пересчёт или неудобны. Для одной подгруппы включение‑исключение сводится к пунктам 1–2 и обычно избыточно.
Короткий пример: N=10N=10N=10, m=3m=3m=3, k=4k=4k=4:
#=(104)−(74)=210−35=175. \#=\binom{10}{4}-\binom{7}{4}=210-35=175.
#=(410 )−(47 )=210−35=175.