Кейс по комбинаторике: имеется коробка с n различными предметами, нужно выбрать k предметов, но порядок выбора важен только в случае совпадения двух определённых предметов. Сформулируйте подсчёт числа вариантов и обсудите, какие формулы и учёты пересчёта подходят
Кейс по комбинаторике: имеется коробка с n различными предметами, нужно выбрать k предметов, но порядок выбора важен только в случае совпадения двух определённых предметов. Сформулируйте подсчёт числа вариантов и обсудите, какие формулы и учёты пересчёта подходят
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Ответ: число вариантов равно
(nk)+(n−2k−2), \binom{n}{k}+\binom{n-2}{k-2},
(kn )+(k−2n−2 ), при условии 0≤k≤n0\le k\le n0≤k≤n (при k>nk>nk>n — 0). Обоснование кратко:
- Всего наборов размера kkk без учёта каких-либо порядков — (nk)\binom{n}{k}(kn ).
- Те из них, что содержат и A, и B, изначально посчитаны один раз; но они должны учитываться дважды (две относительные упорядоченности A и B), значит нужно добавить ещё ровно число таких наборов: (n−2k−2)\binom{n-2}{k-2}(k−2n−2 ).
Альтернативное разбиение по случаям даёт тот же результат:
(n−2k)+2(n−2k−1)+2(n−2k−2)=(nk)+(n−2k−2). \binom{n-2}{k}+2\binom{n-2}{k-1}+2\binom{n-2}{k-2}=\binom{n}{k}+\binom{n-2}{k-2}.
(kn−2 )+2(k−1n−2 )+2(k−2n−2 )=(kn )+(k−2n−2 ).
Замечания и обобщения:
- Если k<2k<2k<2, то дополнительного умножения не бывает и ответ = (nk)\binom{n}{k}(kn ).
- Обобщение на mmm отмеченных предметов (если порядок важен только внутри отмеченных, т.е. для выбранных ttt отмеченных их все t!t!t! порядка различны) даётся формулой
∑t=0min(m,k)(mt)(n−m k−t )t!. \sum_{t=0}^{\min(m,k)}\binom{m}{t}\binom{n-m}{\,k-t\,}t!.
t=0∑min(m,k) (tm )(k−tn−m )t!.