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

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

Т.о. взяв произвольную пару множества R₁ÇR_{2 , мы показали} , что и в множестве R₁ ,и в R₂ одновременно , а значит в множестве R₁ÇR₂ , будет присутствовать пара <y,x>  .ч.т.д.

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

А={1,2}

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

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

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

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

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

11. Найти число способов размещения n различных шаров по m урнам так, чтобы m₁ урн содержали по p₁ шаров, m₂ – по p₂ шаров и т.д., m_k урн по p_k шаров (m = m₁ + … + m_k, n = m₁p₁ + … +m_k p_k), если

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

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

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

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

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

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

- число способов выбрать m₁ урну и положить в нее p₁

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

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

- для m₁+1урны .

  для m₁+2урны .

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

- для m₁+ m₂ урны.

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

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

Решение отличается от а) лишь тем, что количество способов выбрать урны в каждой группе (m₁, m_2,…, m_k) нужно разделить на число перестановок внутри группы (m_i!) :

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

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

C³₁₀*C²₁₅ +   C²₁₀*C³₁₅  + C¹₁₀*C⁴₁₅ + C^-₁₀*C⁵₁₅

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

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

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

При n ≥ 4

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

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

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

      

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

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

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

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

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