1.Множество D всех сочетаний С* разобьем на два непересекающихся подмножества D = D\ и D2, где D\ n D2 = 0. Множество включает все сочетания с произвольным фиксированным элементом, Z>j = С*:/. Множество D2 включает все сочетания без выделенного фиксированного элемента, Z)2 =Су. Следовательно, С* =Ск~1 +Ск.

Я11-111-1

2.Используйте бином Ньютона (1+л)" УС*Х*.

3.Применить индукцию по п. 7. 2".

л

8. Воспользуйтесь тождеством (а + А)" = ]ГС*а 2>"~ .

Р. Воспользуйтесь тождеством (1 + jc)m(l +jc)"= (1 + x)m+. 10. Воспользуйтесь тождеством (1 + (1 + 1))"= 3".

11-13. Воспользуйтесь тождеством + х)" =]у

14.Указание. Воспользуйтесь полиномиальным разложением формулы (1 + 1 + ... + 1)" = к".

15.21. 16. С2+2. 17. 2л2 х 2л2. 18. 2л2х (2л2 - 2л). 19. 2"т. 20.Л53,С4231 21. З6. 22.63. 23. С2 — двустороннихсловарей, А2— односторонних словарей, л — словарей при переводе по циклу. 24. Ат. 25. Д5,7,3) = -$fy = С[5СщС] . 26. С™+т. 27. Сгп.

28. Ат +А + Ап — учитывается порядок имен. 29. Д2,2,2,1,1).

31.=32.

33.где деление на число п обозначает совпадение соседей

при циклическом перемещении исходной перестановки; в цифре 2 учитываются одни и те же соседи при отраженном (зеркальном) расположении исходной перестановки.

34.Cf0(Cf0 -1)(Cf0 -2) =A3r6. 35. С£,С£,С£.

"10

36. C,f((C62C2C2)/3!) = 15СЯ6. 37. Слб((С2С2С)/3!) = 15СП6.

38. ((2л)!/(2!)")/л! — неупорядоченное разбиение множества.

282

Ответы

39. См. решение задач 7 и 8. 40. 9!-С7!3!+С325!3!3!3!-С333!3!3!3!. 42. (СХС/з )3 + (С(С!23 )2ХС/з )2. 43.3" 44. З17. 45. т".

4Wl %+/я-Г ч/ (п-т)+т-\ "Sl-l1 и(л-*)+т-2 с(л->~>;. )+OT-Jt-l1

51. 54, Л\. 52. 53. CC32i, С\-С\Х-С\С\ГС\С\Х

55. Р(3,2,ЗЛ)- 56. CCf 57. (1 + + а2)...(1 +а„),

1-р"1 1-ру2 1- а«

— . 59. п {п/р] — столько чисел среди 12V!

1-Л 1-Л 1-А и не кратных р. Всего произведений С*, тогда число произведений, кратных/?, равно С,; -Ct\nip) 60. л! - - т + .(объединить т элементов в один элемент).

61. 2 (С2)2 =ni(fl~l)% способов поставить две ладьи так, чтобы

они не угрожали друг другу.— способов по-

ставить две ладьи так, чтобы они угрожали друг другу. Для ответа на вопрос задачи осталось сравнить указанные числа. 63. q20+С20 =90. 66.18. 68.31. 71. с£2 ,, С*"1.

72. 205223000, см. п. 1.13. 73. 27354186, см. п. 1.13. 75. Указание: воспользуйтесь тем, что перестановка двух соседних меток N и Мне оказывает влияния на произведение 2"~т. 76.Щп2". 77. (kn)\f{(k\)"n\). 78. (30)!/((1О!)33!), (30)!/((3!)1010!).

79. (С}С2/2\)(С1£С[1). 80. (С20С2С2С42С22)/5!= 10!/((2!)5 5!). 81. 9!/((1!)1(2!)41!4!). 82. 9!/((3!)33!). 83. Р(2,2,2,2,2,2,1,1,1,1). 84. СС. 85. 48 -СЗ8 + С228 -С4318 — воспользоваться формулой включений и исключений для свойств: — пустой этаж, /=1,4. 87. Л,4,- 88.(9°+91) + 92 +934-...+91

89.90. C,(Jj(M -1, где -1 обозначает число 0.

91. Ч+1.92. С/.. 93. Схема посева сортов пшеницы должна соответствовать латинскому квадрату т х т.

к

94.95. 96. £(-1)С\ (£-/)".

k-r .k-r

97- r+Pk-f-T =ckr£(-nrk-r<r-r~i}m

mm

A=0A=0 m

99.Х(-1)*С*(т-А)!-т!2;4г-*"п!«f -

*=0A=0

100.X(-i)"C;+iC;-(m-r-/:)!=>js=-1. *=0 л=о

102.Введем обозначения. Рк — свойство, что к-я пара враждую-шихрыцарей сидит ряд ом, к =1,2,..., л. ДО) — размещение рыцарей, которые не обладают ни одним из указанных свойств, т.е. требуемые размещения по условию задачи. ДО) = W(0) - W{1)+ + W{2) - ... + {-\)nW{n), где Щк) — количество размещений рыцарей, когда к и более враждующих пар сидят вместе. Объединим каждую из к указанных пар в один объект. Тогда имеем 2л - к объектов, которые можно расположить (2л - Л)! способами. В каждой из к заданных пар врагов можно поменять местами 2к способами. Выбор к враждующих пар можно сделать С? способами. Следова-

п

тельно, искомое число равно ДО) = У(-1) С"2 (2 л-к)1

к=0

103.542. 104. 734. 106. 20%, 60%, 70%. 107. 2, 6, 3. 109-110. Решение подобного уравнения рассмотрено в п.1.1.

11L § f«H*% 111 С"-2" Действительно> выбирая из л-2 три различных предмета способами, можно однозначно отобразить их в разбиения, требуемые по условию. Если выбраны предметы с номерами < к2 < А"3, то в исходном ряду их номера будут кх<к2 + 1<к3 + 2.

ИЗ. ±(-1У g Ц§. 114..2.2]"(2л)! = (12)" (2л)!.

115. 2", 116. п +1. 117. Количество прямоугольников размера

i xj равно (л - + 1) х -j + 1). Каждый прямоугольник учитывается в сумме столько раз, какова его площадь. Тогда сумма рав-

ЪЪ, ,w i\ ibt . ivl (и(л + 1)(«+2)У на1 n "" 2> :"n -i -I

/=!/=!u=i) v ч J