Вычислить все варианты. Комбинаторика.

Question

Всего есть 16 элементов. Из них можно выбрать от 6 до 16 (включительно) . Порядок выбора не важен. Как определить количество всех возможных вариантов выбора?

Answer 1

Абстрагируемся от конкретной проблемы и перейдём к числам. Давайте представим, что у нас есть двоичное шестнадцатизначное число. Каждой позиции в этом числе будет сответствовать один из 16 наших элементов, и тогда 1 в этой позиции будет означать, что мы элемент выбрали, а 0, что не выбрали.

Теперь нас интересует сколько есть таких 16-значных двоичных чисел (допустимы ведущие нули) , в которых от 6 до 16 единиц. Предлагаю считать количество чисел в которых от 0 до 5 единиц, и потом отнять от общего количество получившеся.

16! / (0! *16! ) + 16! / (1! *15! ) + 16! / (2! *14! ) 6! / (3! *13! ) + 16! / (4! *12! ) + 16! / (5! *11! )
1 + 16 + 120 + 560 + 1820 + 4368 = 6885 - это сколько вариантов нам не подходят
Теперь посчитаем сколько подходят - все минус те, что не подходят:
2^16 - 6885 = 65536 - 6885 = 58651

Вот. если нигде не накосячил, то вот столько вариантов