Сочетания

Пусть 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 равно:

  Если k = 0, тогда

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

,

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

.

Пример 9. Дано 10 точек, из которых никакие три не лежат на одной прямой и никакие четыре точки не лежат в одной плоскости. Сколько различных плоскостей можно провести через эти точки?

Из геометрии нам известна аксиома, что через три точки, не лежащие на одной прямой можно провести плоскость и притом только одну.

Поскольку это так, тогда, если плоскость проходит через три точки A, B, C, то через точки B, A, C или C, B, A и т.п., проходит та же плоскость, т. е.

порядок расположения трех точек, через которые проходит плоскость не имеет значения. А значит число различных плоскостей, проведенных через каждые три точки из 10 равно числу сочетаний из 10 элементов по 3.

Составим процедуру вычисления числа сочетаний из n элементов по k.

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

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

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

Итак, пользуемся формулой:  

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

Получим: Procedure Combination(n, k : integer; var  с : longint);

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

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

В процедуре устанавливаются первоначальные значения для числа сочетаний (c := 1).

Организуется цикл for от 1 до k, в котором в переменную с будет накапливаться произведение, которое и является числом сочетаний из n элементов по k:

 ,   (1)  где  -  знак произведения от 1 до k.

Давайте проверим, будет ли эта формула выдавать нам число сочетаний из n элементов по k. Пусть n = 5, k = 3, тогда по формуле для числа сочетаний будем иметь:



а по формуле (1), получаем:



Таким образом, этой формулой можно пользоваться при подсчете числа сочетаний в программе.

Окончательно процедура вычисления числа сочетаний будет следующей:

Procedure combination(n, k : integer;  var

с : longint);

    var

        i : longint;

    begin

       с := 1;

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

    end;

Для составления программы решения данной задачи, надо в основной программе обратиться к процедуре combination, причем фактические значения переменных будут 10, - общее число точек и 3 - число точек через которые проходит одна плоскость.

Программа

 

Program Problem9;

     uses WinCrt;

     var

        pl : 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

        combination(10, 3, pl);

        writeln('Число плоскостей равно: ', pl)



     end.

Пример 10. Сколько различных вариантов хоккейной команды можно составить из 9 нападающих, 5 защитников и 3 вратарей, если в состав команды должны войти 3 нападающих, 2 защитника и 1 вратарь?

Соображения по составлению программы

Из 9 нападающих можно выбрать троих числом способов:  Из 5 защитников можно выбрать двоих  способами. Из 3 вратарей можно выбрать одного  способами. Общее число возможных способов равно произведению числа способов выбора нападающих, защитников и вратарей: .

Программа

Program Problem10;

     uses WinCrt;

     var

        h1, h2, h3 : longint;

{----------------------------------------------------------------------------------------}

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

         var

            i : longint;

         begin

            c := 1;

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

         end;

{----------------------------------------------------------------------------------------}

     begin

        combination(9, 3, h1);

        combination(5, 2, h2);

        combination(3, 1, h3);

        write('Хоккейную команду можно составить ', h1*h2*h3);

        writeln(' способами');

     end.


Содержание раздела

---

---

Главная сайта

---