Пункт 11

Сочетания, размещения и перестановки

Число перестановок: P(n)=n!

Это количество перестановок множества из n элементов, порядок важен

Число размещений: (A_n^k)=n!/(n-k)!

Это количество способов выбрать k элементов из n элементов, порядок важен. P(n)=(A^n_n)

Число сочетаний: (C^k_n)=n!/(k!(n-k)!)

Это количество способов выбрать k элементов из n элементов, порядок не важен.

Если кратко: во всем с буквой р порядок важен, в остальном - нет.

Тождества

1. Сочетания с повторениями:

2. (C^k_n)=(C^n-k_n)- количество способов выбрать k равно количеству способов не выбрать n-k

3. (∑_i^n)((C^i_n))=2n - мощность множества всех подмножеств равна 2n, с другой стороны
для каждого k ≤ n число множеств из k элементов - (C^k_n)

4. (∑_i^n)((C^i_n)2)=(C^n_2*n)- можно взять множество из 2*n элементов, и выбрать k из одного куска, а n-k из другого. Тогда: (C^n_2*n)=(∑_i^n)((C^k_n)*(C^n-k_n))=(∑_i^n)((C^i_n)2)

Формула включений и исключений

Беспорядки