С.Н. Селезнева - Основы дискретной математики (1060725), страница 5
Текст из файла (страница 5)
. ∩ Aim+k |.k=0 1≤i1 <...<im+k ≤nЗадача 2.10. 1. Доказать формулу включений-исключений (теорема 1.3),подсчитав сколько раз произвольный элемент входит в левую и правуючасти ее выражения.2. Доказать формулу из п. 2 задачи 2.9, подсчитав сколько раз произвольный элемент входит в левую и правую части ее выражения.Задача 2.11.
1. Перестановка n элементов называется беспорядком, если в ней элемент i находится не на i-том (то есть не на своем“) месте”для всех i = 1, . . . , n. По формуле включений-исключений (теорема 1.3)вывести формулу для подсчета количества беспорядков из n элементов.2. По формуле п. 2 задачи 2.9 вывести формулу для подсчета количества перестановок n элементов, в которых ровно m, 0 ≤ m ≤ n,элементов находятся на своих“ местах.”Задача 2.12. Пять гостей рассаживаются за столом, не обращая внимания на таблички с именами.
Найти вероятность того, что хотя бы одиниз гостей окажется на месте с табличкой со своим именем.Задача 2.13. Четыре человека сдают свои шляпы в гардероб. В предположении, что шляпы возвращаются наугад, найти вероятность того,что ровно k, 0 ≤ k ≤ 4, человек получат свои шляпы обратно.Задача 2.14. Рассмотрим следующую игру.
Выбирается некоторое слово. Затем из его букв составляются новые слова, в которых каждая буква может встречаться не более раз, чем в выбранном слове. Например,из слова комбинаторика“ можно составить слова канат“, карат“,”””банка“, но не получится слово банан“ (буква н“ в выбранном слове”””встречается только один раз).271. Сколько разных слов из k букв можно так составить из выбранногослова из n букв (1 ≤ k ≤ n)?2. Сколько разных слов можно так составить из выбранного слова изn букв?Задача 2.15. Сколько разных одночленов получится, если раскрытьскобки и привести подобные слагаемые в выражении (x + y)n , где n ≥ 2?Задача 2.16.
1. Сколько разных одночленов получится, если раскрытьскобки и привести подобные слагаемые в выражении (x1 + . . . + xk )n , гдеk ≥ 2, n ≥ 2?2. Найти количество разных одночленов, которые получатся, если раскрыть скобки и привести подобные слагаемые в следующих выражениях:1) (x + y + z)2 ; 3) (x + y + z + u)2 ;2) (x + y + z)3 ; 4) (x + y + z + u)5 ?2.3Свойства комбинаторных чиселk−1k+ Cn−1.Пример 2.3.
Доказать, что Cnk = Cn−1Решение. Сочетание из n элементов по k можетk1) или не содержать n-й элемент – таких сочетаний ровно Cn−1;k−12) или содержать n-й элемент – таких сочетаний ровно Cn−1 .Этими вариантами исчерпываются все возможные сочетания из n элементов по k, и эти варианты одновременно не возможны. Поэтому Cnk =k−1k+ Cn−1.Cn−1nPПример 2.4. Доказать, чтоk · Cnk = n · 2n−1 .k=0Решение. Заметим, что при k ≥ 1 верноk · Cnk = k ·n!n!==k!(n − k)! (k − 1)!(n − k)!(n − 1)!k−1= n · Cn−1.(k − 1)!((n − 1) − (k − 1))!Слагаемое при k = 0 обнуляется.
Поэтому, учитывая следствие к теореме 2.5, получаем=n·nXk=0k·Cnk=nXk=1k·Cnk=nXn·k−1Cn−1k=1=n·n−1Xl=028lCn−1= n · 2n−1 .2.4УпражненияЗадача 2.17. 1. Доказать, что при n ≥ 1 и 0 ≤ l ≤ k ≤ nk−l· Cnl .2) Cnk · Ckl = Cn−l1) Cnk = Cnn−k ;k−1kЗадача 2.18. 1. Доказать, что Cnk = Cn−1+ Cn−1.2. Доказать по индукции, опираясь на п. 1, чтоnnPPk+1k−lk2) Cn+1 =Clk .1) Cn =Cn−l−1 ;l=kl=0kЗадача 2.19. 1. Доказать, что Cn+1> Cnk (то есть последовательность{Cnk } возрастает по n при фиксированном k).k−(l+1)k−lk−l}(то есть последовательность {Cn−l2. Доказать, что Cn−(l+1) < Cn−lубывает по l при фиксированных n и k).k+13. Доказать, что Cnk+1 > Cnk при k < n−1< Cnk при k > n−12 и Cn2 (тоесть последовательность {Cnk } возрастает по k при k < n−12 и убываетn−1по k при k > 2 при фиксированном n).4.
Доказать, что1) если n – нечетно, то максимальное значение числа Cnk при фиксиn+1рованном n достигается при k = n−12 и k = 2 ;2) если n – четно, то максимальное значение числа Cnk при фиксированном n достигается при k = n2 .Задача 2.20. Доказать, что если p – простое число (см. задачу 1.26,п. 6), то Cpk делится на p при всех k = 1, . . . , (p − 1).Задача 2.21.
Доказать, опираясь на формулу бинома Ньютона (см. теорему 2.5), что при n ≥ 1nnPPnk(2k + 1) · Cnk = (n + 1) · 2n ;1)Cn = 2 ;5)2)k=0nP3)k=0nP4)k=0nP(−1)k · Cnk = 0;k · Cnk = n · 2n−1 ;6)k=0nP7)k=0nPk(k −1)Cnk = n(n−1)2n−2 ; 8)k=0k=0nPk=11k+1· Cnk =(−1)kk+1· Cnk =(−1)k−1·CnkkЗадача 2.22. 1. Доказать, что при n ≥ 1 и k ≥ 0XX1Cn2k =Cn2k+1 = · 2n .2kk291n+1· (2n+1 − 1);1n+1 ;= 1+ 12 +. . .+ n1 .2.
Доказать, что n ≥ 1 и k ≥ 0X1 nπn 3kCn = · 2 + 2 cos.33kЗадача 2.23. 1. Доказать, перейдя к сумме бесконечно убывающей геометрической прогрессии, что если n ≥ 1 и r < n2 , тоrXCnk ≤k=0n−r· Cnr .n − 2r2. Доказать, перейдя к сумме бесконечно убывающей геометрическойпрогрессии, что если n ≥ 1 и r > n2 , тоnXCnk ≤k=rr· Cnr .2r − nЗадача 2.24. Доказать индукцией по n, опираясь на свойство возрас1 nтания последовательности 1 + n , чтоCnknn≤ kk · (n − k)n−kпри всех n ≥ 1, 0 ≤ k ≤ n (полагаем, что 00 = 1).Задача 2.25. Доказать, что если n ≥ 1 и r < n2 , тоrXk=0Cnknn≤ r.r · (n − r)n−rЗадача 2.26.
Если целые неотрицательные числа k1 , . . . , km таковы, чтоn!k1 + . . . + km = n, то число Cn (k1 , . . . , km ) = k1 !·...·kназывается полиноm!миальным коэффициентом.1. Исходя из комбинаторного смысла доказать, чтоk2kmCn (k1 , . . . , km ) = Cnk1 · Cn−k· . . . · Cn−k.11 −...−km−12. Доказать, что биномиальный коэффициент Cnk является частнымслучаем полиномиального коэффициента Cn (k1 , k2 ) при k2 = n − k1 .303. Индукцией по m доказать, чтоXn(x1 + .
. . + xm ) =Cn (k1 , . . . , km ) · xk11 · . . . · xkmm .k1 , . . . , km ≥ 0 :k1 + . . . + km = n4. Доказать, опираясь на п. 3, чтоXCn (k1 , . . . , km ) = k n .k1 , . . . , km ≥ 0 :k1 + . . . + km = n313Отношения на множествах3.1Основные понятияОпределение 3.1. Пусть h ≥ 1. h-арным (или h-местным) отношением на множестве A назовем любое подмножество множества Ah .Обозначение:R(h) ⊆ Ah – R – h-арное отношение на множестве A.Если (a1 , . . . , ah ) ∈ R(h) , то говорят, что элементы a1 , . .
. , ah множества A находятся в отношении R, или что отношение R выполняется(или верно) на элементах a1 , . . . , ah , и записывают R(a1 , . . . , ah ).Если (a1 , . . . , ah ) ∈/ R(h) , то говорят, что элементы a1 , . . . , ah множества A не находятся в отношении R, или что отношение R не выполняется (или не верно) на элементах a1 , .
. . , ah , и записывают R(a1 , . . . , ah ).Если h = 1 – h-арное отношение называется унарным отношением,или свойством. В этом случае любой элемент множества A или обладаетэтим свойством, или нет.Если h = 2 – h-арное отношение называется бинарным. В этом случаелюбая пара элементов из множества A или находится в этом отношении,или нет.Как правило, когда из контекста понятна арность отношения, верхнийиндекс при записи опускают. Пишут: R – h-арное отношение на множестве A.Определение 3.2. Бинарное отношение R(2) ⊆ A2 называется- рефлексивным, если оно выполняется на паре (x, x) для любого элемента x, то есть ∀8 x ∈ A R(x, x);- иррефлексивным, если оно не выполняется на паре (x, x) для любогоэлемента x, то есть ∀x ∈ A R(x, x);- симметричным, если из его выполнения на паре элементов (x, y)следует выполнение и на паре элементов (y, x), то есть ∀x, y ∈ A R(x, y) ⇒9R(y, x);- антисимметричным, если его одновременное выполнение на парахэлементов (x, y) и (y, x) возможно только в случае совпадения элементовx и y, то есть ∀x, y ∈ A R(x, y) и R(y, x) ⇒ x = y;89знак ∀ – квантор всеобщности – читается для всех“, для каждого“.””знак ⇒ – логическое следование – читается следует“.”32- транзитивным, если из его выполнения на парах элементов (x, y)и (y, z) следует выполнение на паре (x, z), то есть ∀x, y, z ∈ A R(x, y) иR(y, z) ⇒ R(x, z).Определение 3.3.
n-й степенью h-арного отношения R(h) ⊆ Ah (гдеn ≥ 2 – натуральное число) называется h-арное отношение на множествеAn , выполняющееся в точности на всех h-ках элементов множества An ,в которых по каждой координате выполняется отношение R.Обозначение:(Rn )(h) = {((a11 , . . . , a1n ), . .
. , (ah1 , . . . , ahn )) | R(a1i , . . . , ahi ), i = 1, . . . , n} ⊆(An )h – n-я степень отношения R(h) , является h-арным отношением на множестве An .3.2УпражненияЗадача 3.1. Пусть A – множество слов толкового словаря В. Даля.1. Являются ли свойствами на множестве A1) имена существительные;3) диалектизмы;2) синонимы;4) устаревшие слова?2. Связаны ли бинарным отношением1) однокоренные слова;2) антонимы;3) соседние слова;4) наречия?Задача 3.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
