Решение 23 заданий с множествами и подмножествами (Вариант 31), страница 2

2)   . По условию R2-симметричное отношение®

Т.о. взяв произвольную пару множества R1ÇR2 , мы показали , что и в множестве R1 ,и в R2 одновременно , а значит в множестве R1ÇR2 , будет присутствовать пара <y,x>  .ч.т.д.

  1. Построить бинарное отношение: рефлексивное, транзитивное, не симметричное :

А={1,2}

P={<1,1>,<2,2>,<1,2>}

  1. Пусть a £ b Û a,b Î N и a делит b (считаем, что 0 делит 0). Доказать, что £ - частичный порядок на N.

1.  рефлексивное : любое натуральное число делит само себя

2.  транзитивное : а,б,с N  если  и  , то

3.  антисимметричное :  а,бN если   и  , то а=б

  1. Найти число способов размещения n различных шаров по m урнам так, чтобы m1 урн содержали по p1 шаров, m2 – по p2 шаров и т.д., mk урн по pk шаров (m = m1 + … + mk, n = m1p1 + … +mk pk), если

a)  урны различны;

1ую урну можно выбрать m способами , 2ю – m-1 , 3ю  - m – 2 и т.д.

Для первых m1 урн получаем

- выбираем первую урну и размещаем в нее p1 шаров из n .

 для второй , но размещаем p1 шаров из оставшихся .

………………………………………………………………………………………………

- число способов выбрать m1 урну и положить в нее p1

                                                                                                                                                                шаров из оставшихся .

Для следующих m2 урн получаем :

- для m1+1урны .

  для m1+2урны .

………………………………………………………………………………………………

- для m1+ m2 урны.

Т.о. ® для m урн :

b)  урны, содержащие  одинаковое число шаров, неразличимы.

Решение отличается от а) лишь тем, что количество способов выбрать урны в каждой группе (m1, m2,…, mk) нужно разделить на число перестановок внутри группы (mi!) :

  1. При составлении варианта контрольной работы нужно выбрать 5 из 25 задач, среди которых 15 по комбинаторике и 10 по теории множеств. Сколькими способами можно составить вариант так, чтобы в него попались не менее двух задач по комбинаторике?

не менее двух задач по комбинаторике =>  задач по комбинаторике ≥2

C310*C215 +   C210*C315  + C110*C415 + C-10*C515

  1. Сколько существует 6-значных чисел, в записи которых есть хотя бы одна четная цифра?

C165!-выбираем место под четную , остальные 5 ставим как хотим .

  1. Сколько диагоналей в выпуклом n-угольнике?

При n ≥ 4

 -n –выбираем вершину (n-3) – для выбранной вершины выбираем вершину,

                       не смежную. Делим на 2 , потому что м посчитала диагонали по 2 раза . 

  1. Между двумя игроками проводится n партий, причем каждая партия кончается или выигрышем, или проигрышем, и всевозможные исходы партий равновероятны. Найти вероятность того, что определённый игрок выиграет ровно m партий, 0≤m≤n.

      

-всевозможные способы выиграть m-партий из n-партий

 –максимальное число благополучных исходов для первого и второго игрока.

  1. Сколько можно составить перестановок из n элементов, в которых данные m элементов не стоят рядом в любом порядке?

n! – (n – m + 1)!m!

  1. Пусть общий объем доступных ресурсов равен 12. Требуется спланировать инвестиции на 4 года, зная зависимость величины дохода fk от величины выделенных ресурсов x (x=0, 1, ..., 12) в k-й год. Используя методы динамического программирования, определить, при каком распределении ресурсов по годам величина доходов будет максимальной.