Пусть M - конечное (не обязательно упорядоченное) множество, состоящее из n элементов. Сочетанием из n элементов по k называется любое подмножество множества , состоящее из k элементов. Два сочетания из n элементов по k мы будем считать различными в том случае, если в одном из них есть, хотя бы один элемент, не содержащийся в другом.

     Другими словами, в сочетаниях не важен порядок элементов, а важен лишь их состав. Так, например, из множества M = {1, 2, 3, 4} можно составить четыре различных сочетания из 4 по 3: {1, 2, 3}, {1,2,4}, {2, 3, 4}, {1, 3, 4}.

     Число различных сочетаний из n элементов по k равно:

     Учитывая, что число размещений из n элементов по k равно:

можно выразить число сочетаний через число размещений, тогда получим:

     Составим процедуру вычисления числа сочетаний из n элементов по k. Для этого удобней воспользоваться второй формулой, в которой вычисляется только один факториал числа k. В формуле

их надо вычислять целых три (n!, (n - k)! и k!) и может возникнуть ситуация, когда будут получаться очень большие числа, которые могут выходить за пределы указанного целого типа.

     Можно найти и другую формулу для числа сочетаний, в которой можно избежать больших чисел и вычисления факториалов чисел.

     В процедуре, в качестве входных формальных переменных будут две переменные n и k, для числа всех элементов и числа выбираемых элементов. Выходной параметр для значения сочетания обозначим c, имя процедуры - Сombination.

     Входные параметры имеют тип integer, а выходной - longint, так как значение числа сочетаний может быть даже очень большим числом.

     Переменные самой процедуры - i, - переменная для цикла for и p - промежуточная переменная для факториала k!.

     Программа для вычисления числа сочетаний

{combin.pas

Сайт Algorithm (http://www.algorithm1.narod.ru/)

Автор проекта: Galina}

uses Crt;

var n1,k1,p : longint;

Procedure combination(n, k : integer; var c : longint);

var i : longint;

begin

  c := 1;

  for i := 1 to n - k do c := c*(n - k + i) div i

end;

begin

  writeln('Введите число всех элементов: ');

  readln(n1);

  writeln('Введите число выбираемых элементов: ');

  readln(k1);

  combination(n1, k1, p);

  writeln('Число сочетаний равно: ', p)

end.