Элементы комбинаторного анализа.
Основное правило комбинаторики: пусть имеется множ-во А,содерж. n- элементов и B~n,тогда число А, взяв по одному элементу из каждого мн-ва будет равно .
Размещение: пусть имеется множ-во, содерж n- эл-ов, каждое упорядоченное подмн-во этого мн-ва, сост из k- эл-ов наз-ся размещением из n- эл-ов по k.Для того,чтобы найти какое- либо размещение надо:выбираем 1-ый эл-нт – число способов, которыми можно сделать это=n; выбираем 2-ой эл-нт из оставшихся n-1,сущ. сп-б сделать это (n-1),число пар n(n-1); 3-ий эл-нт выбираем из (n-2), общее число будет равно n(n-1)(n-2),процесс повторить k раз, общее число n(n-1)(n-2)…(n-k+1).
Перестановка n- эл-ов наз-ся размещением n-эл-ов из m.
Сочетание: - число сочетан. по k- эл-ам, выбран. из n. Пусть имеется множество, сод. n- эл-ов, каждое его поджнож-во , сод. к-разл. эл-ов наз-ся сочетание n-элементов по k. Порядок элементов в сочетании не учитывается и различными считаются сочетания отличающиеся хотя бы одним элементом.
Док-во: пусть – это число различных подмн-в, сод k-эл-ов , которые отлич. хотя бы одним эл-ом, тогда сущ. k! сп-ов, которые мы можем упорядочить k- выбранных эл-ов, тогда число подмножеств, упорядоченных всеми способами и содерж. k-эл-ов будет = произведению .