Размещения vs сочетания: когда A(n,k), а когда C(n,k)? Постоянно путаю
В задачах то «сколькими способами выбрать k из n», то «сколькими способами расставить k из n». Знаю формулы C(n,k) = n!/(k!(n−k)!) и A(n,k) = n!/(n−k)!, но путаюсь, когда какая. Как раз и навсегда понять разницу и не ошибиться на контесте?
2 ответа
Ключевой вопрос: важен ли ПОРЯДОК выбранных элементов?
- Порядок НЕ важен → сочетания C(n,k) = n!/(k!(n−k)!). Пример: выбрать 3 человек в команду — {Аня, Боря, Вася} = {Вася, Аня, Боря}.
- Порядок ВАЖЕН → размещения A(n,k) = n!/(n−k)! = n·(n−1)·...·(n−k+1). Пример: раздать золото/серебро/бронзу 3 из n спортсменов — кто на каком месте, важно.
Связь: A(n,k) = C(n,k) · k!, потому что каждое сочетание можно упорядочить k! способами. Поэтому A всегда ≥ C.
// через предподсчитанные 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 A(int n, int k){ if(k<0||k>n)return 0; return fact[n]*inv_fact[n-k]%MOD; } // размещения
Оба запроса O(1) после O(n) предподсчёта. Мнемоника: «сочетание — состав» (только кто), «размещение — расстановка» (кто и куда).
Добавлю две соседние сущности, чтобы закрыть тему: перестановки P(n) = n! — это A(n,n), все элементы расставлены. А если выбор С ПОВТОРЕНИЯМИ и порядок не важен — это сочетания с повторениями C(n+k−1, k) (то самое stars and bars). Так что четыре случая: (порядок ±) × (повторения ±) дают четыре разные формулы — всегда сначала спрашивай про порядок и повторения.