Основные модели при выборе $k$ предметов из $N$ при условии, что порядок не учитывается, — две: без повторений и с повторениями. Как отличить и какие формулы применять:
- Без повторений (каждый предмет можно взять не более одного раза).
- Число способов: $\left(\genfrac{}{}{0ex}{}{N}{k}\right)=\frac{N!}{k!(N-k)!}$.
- Условия в задаче: фразы «без повторений», «без возвращения», «каждый предмет не более один раз», «выбрать подмножество», или явное ограничение $k\le N$. Если $k>N$, ответ равен $0$.
- С повторениями (один и тот же предмет можно выбирать несколько раз).
- Число способов: $\left(\genfrac{}{}{0ex}{}{N+k-1}{k}\right)=\frac{(N+k-1)!}{k!(N-1)!}$ (метод «звёзд и перегородок»).
- Условия в задаче: фразы «с повторениями», «можно выбирать один предмет несколько раз», «с возвращением», или явно разрешён выбор одного типа многократно; здесь допускается $k>N$.
Как быстро отличить по тексту задачи:
- Если говорится про «повторять», «с возвращением» или нет ограничения $k\le N$ — используем модель с повторениями.
- Если говорится «без повторений», «каждый предмет не более одного раза», «без возвращения» или явно $k\le N$ — используем модель без повторений.
- Если предметы неразличимы или заданы ограничения на количество каждого типа — нужна модель мультимножеств с ограничениями (тогда формула меняется).
Короткие примеры:
- $N=5,k=3$, без повторений: $\left(\genfrac{}{}{0ex}{}{5}{3}\right)=10$.
- $N=5,k=7$, с повторениями: $\left(\genfrac{}{}{0ex}{}{5+7-1}{7}\right)=\left(\genfrac{}{}{0ex}{}{11}{7}\right)=330$.