Давайте разберемся с помощью простого примера: Представьте, что у вас есть 4 фрукта: яблоко, груша, банан и апельсин. Вам нужно выбрать любые 3 из них. Способы выбора: Как видите, из 4 фруктов можно составить 4 различных комбинации по 3 фрукта. Формула для расчета числа сочетаний Для более сложных задач существует специальная формула, которая позволяет посчитать количество сочетаний без перебора всех вариантов вручную: C(n, k) = n! / (k! * (n-k)!) Где: В нашем случае: Подставим значения...
"Сколькими способами можно..." Так начинаются задачи из области комбинаторики, то есть задачи на подсчет числа вариантов. Часто (хотя и не всегда) из маленьких исходных чисел получаются огромные, астрономические ответы. Это явление носит название "экспоненциальный взрыв" и мы с ним уже сталкивались. Иногда это на пользу, например в криптографии. Всё на виду, но вариантов перебрать надо многовато. Впрочем, обо всем по порядку. Цель заметки - собрать все основные формулы (вот редко когда они действительно все присутствуют) и показать, хоть примерно, откуда они берутся...