1.Введение в комбинаторику. Генерация k–элементного подмножества данного множества. Размещения. Сочетания.

Размещение из n элементов по m — это упорядоченный (здесь нам важен порядок) набор из m различных чисел, лежащих в промежутке от 1 до n (т. е. ∈ X). Другими словами размещение — это множество с повторениями.

Размещение – это произвольное k-элементное подмножество n-элементного множества. Порядок элементов в подмножестве имеет значение.

Число размещений находится по формуле: A (n, k) = n! / (n – k)!

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

Private Function RazmCount (ByVal n As Integer, ByVal k As Integer) As Double

RazmCount = fact (n) / fact (n – k)

End Function

Private Function fact (ByVal n As Integer) As Double

Dim i As Integer

Fact = 1

For i = 1 To n ‘перемножаем все числа от 1 до n

fact = fact * i

Next

End Function

Сочетание из n элементов по m — это неупорядоченный набор (множество) из m различных чисел, принадлежащих множеству X. Обозначим число элементов множества сочетаний через Cn,m. Т. к. сочетание является неупорядоченным набором, то каждому такому набору соответствует m! размещений (т. е. упорядоченных набора тех же элементов). Тогда получаем, что Cn,m = n! ⁄ m!(n−m)!

Можно привести некоторые свойства сочетаний:

Cn,m = Cn,n−m

Cn,m + Cn,m+1 = Cn+1,m+1

Cn,m * Cm,k = Cn,k * Cn−k,m−k

Эти свойства следуют из самих определений и проверяются непосредственно.

Генерирование всех к-элементных подмножеств множества (1,…,п) в лексикографическом порядке

begin

for i;=1 to k do A[i]:=1;//первое подмножество

p:=k;

while p>=1 do

begin

write(A[i],//,A[k]);

if A[k]=n then p:=p-1

else p:=k;

if p>=1 then

for i:=k downtop do A[i]:=A[p]+i-p+1

end

end

Сочетание – это произвольное k-элементное подмножество n-элементного множества. Порядок элементов в подмножестве не имеет значения.

Пример сочетаний по 2 из 3:

12

13

23

Число сочетаний находится по следующей формуле: C (n, k) = n! / (k! * (n-k)!)

Число сочетаний можно вычислить, используя следующий код:

Private Function SochCount (ByVal n As Integer, ByVal k As Integer) As Double

SochCount = fact (n) / (fact (k) * fact (n-k))

End Function

Private Function fact (ByVal n As Integer) As Double

Dim i As Integer

Fact = 1

For i = 1 To n ‘перемножаем все числа от 1 до n

fact = fact * i

Next

End Function

2. Законы алгебры логики. Таблицы истинности.?????

Билет № 14