Вычислить число сочетаний из n по k

Формулировка. Даны натуральные числа n и k (k не превышает n). Вычислить число сочетаний из n по k.

Примечание: в комбинаторике сочетанием из n по k называется набор k элементов, выбранных из данных n элементов; при этом наборы, отличающиеся только порядком следования элементов, считаются одинаковыми. Обозначение числа сочетаний из n по k элементов: . При этом считается, что ,   и  для любого натурального n.

Например, найдем все 2-элементные сочетания 3-элементного множества {1, 2, 3}. Таковыми являются {1, 2}, {1, 3} и {2, 3}. То есть, таковых сочетаний 3. При этом, например, {1, 2} и {2, 1} – одинаковые сочетания, так как они отличаются только порядком следования элементов.

Решение. Из комбинаторики известна формула:

Не интересуясь вопросом ее вывода и корректности, мы будем использовать тот ее вариант, который написан после второго знака равенства (если смотреть слева направо), так как он наиболее оптимален для вычислений и позволит обойтись двумя циклами (для числителя for с downto, для знаменателя – просто for). Для числителя и знаменателя предусмотрим соответственно переменные num (от англ. numerator – «числитель») и denom (от англ. denominator – «знаменатель»), которым нужно поначалу присвоить значения 1, чтобы осуществить контроль частных случаев (этот вопрос упомянут в задаче 29):

1) При k = 0 переменная num останется неизменной и будет равна 1, так как невозможен вход в цикл с уменьшением от nдо (n + 1), переменная denom будет равна 1 как 0!;

2) При n = k num и denom будут вычислены и при делении дадут единицу;

3) При n = k = 0 переменная denom будет вычислена как 0!, а переменная num не изменится по невозможности входа в цикл с уменьшением от 0 до 1.

Код:

1. program NumOfCombinations;
2. var
3. i, n, k: byte;
4. num, denom: integer;
5. begin
6. readln(n, k);
7. num := 1;
8. for i := n downto n — k + 1 do begin
9. num := num * i
10. end;
11. denom := 1;
12. for i := 1 to k do begin
13. denom := denom * i
14. end;
15. writeln(num div denom)
16. end.