Поиск чисел удовлетворяющих условию

#алгоритм #комбинаторика

Необходимо написать программу, которая определяет количество троек натуральных чисел
(x,y,z), таких что:

0 < x < y < z < N, 

Где N - натуральное число, 0 < N < 1000

Понимаю, что задача состоит в правильном использовании комбинаторных формул. Однако
идей нет. Вариант в лоб (через 3 цикла и перебор не подходит для меня). Нет идей. Не
нужно ничего писать, если можно подтолкните к правильному решению.
    

Ответы

Ответ 1

Как уже написали в комментариях, посчитать число троек (x, y, z) натуральных чисел,
таких что 

0 < x < y < z < N


можно так:


Сначала уберём условие упорядоченности, то есть посчитаем число троек (x, y, z),
таких что каждое из трёх чисел больше нуля и меньше N

Получится N - 1 * N - 2 * N - 3 троек (первое число можно выбрать N - 1 способами,
второе N - 2 способами, ...)
Теперь рассмотрим три различных числа, например {1, 2, 3}. Всего троек, составленных
из этих чисел будет 6 = 3 * 2 * 1 штук (следствие предыдущего пункта для N равного
3+1). Нам подходит ровно одна из этих шести троек — когда числа стоят по возрастанию


Таким образом, ответ равен (N - 1) * (N - 2) * (N - 3) / 6