Дискретная математика (1). Лекция Составные высказывания
 Скачать 2.15 Mb.
|
Задача о числе подмножеств данного множества.Пусть имеется М={  , }. Пустое множество Ø входит в это множество как подмножество. Одноэлементные множества тоже. Поставим каждому подмножеству кортеж длиной n, состоящий из 0 и 1.0-если соответствующий элемент не входит в подмножество. 1-если входит. Например, подмножеству {  } будет соответствовать кортеж 010100000….0000…Для вех подмножеств получим (0,0,0,…0), (1,0,0,…0), (0,1,0,0,...,0)… (1,1,1,…1) Кортежей столько, сколько подмножеств. Это размещения, состоящие из двух элементов (0 и 1) и отличающиеся друг от друга либо элементами, либо их порядком. Это размещения с повторениями из двух по n: Получим Ậ  = .Таким образом, мы доказали теорему: Число подмножеств n-элементного множества равно .Следствие: Так как число пустых подмножеств С  (0)=1, одноэлементных-С =n, двухэлементных-С , трехэлементных-С , n-элементных С , то сумма  С = .Перестановки с повторениями.Пусть мы имеем n элементов , ,  =n!. Пусть элемент повторяется  раз, элемент - раз,….,  - раз, где  . Тогда число различных перестановок будет в ! меньше за счет одинаковых элементов , в ! раз меньше за счет одинаковых элементов ,…и в ! раз меньше за счет одинаковых элементов . Тогда число различных перестановок будет равно: ( , ,…, )= .Пример. Сколько различных перестановок можно составить из слова МОЛОТОК? Решение: (М)=1; (О)=3;  (Л)=1;  (Т)=1;  (К)=1; (1,3,1,1,1)=  =840. |