23. Сколько различных словарей надо издать, чтобы можно было переводить с любого из данных языков на любой другой язык этого же множества?

24. В правление избрано т человек. Из них надо выбрать председателя, заместителя председателя, секретаря и казначея. Сколькими способами можно это сделать?

25. У мамы 5 яблок, 7 груш и 3 апельсина. Каждый день в течение 15 дней подряд она выдает сыну по одному фрукту. Сколькими

способами это может быть сделано?

26. У мамы т яблок и п груш. Каждый день в течение п + т дней

подряд она выдает сыну по одному фрукту. Сколькими способами это может быть сделано?

27. Найти число векторов а = (аь а2,.-., о„), координаты которых

п

удовлетворяют условию at = {О, 1}, i= 1, 2,..., п, Vflj =г.

28. У англичан принято давать детям несколько имен. Сколькими

способами можно назвать ребенка, если ему дают не более трех

имен, а общее число имен равно т?

29. Сколькими способами можно расставить белые фигуры: 2 коня, 2 слона, 2 ладьи, ферзя и короля на первой линии шахматной доски?

30. Сколькими способами можно расставить k ладей на шахматной доске размером п х т так, чтобы они не угрожали друг другу, т. е. так, чтобы никакие две из них не стояли на одной вертикали

или горизонтали?

31. Сколькими способами можно посадить п мужчин и л женщин за круглый стол так, чтобы никакие два лица одного пола не сидели рядом?

Та же задача, но стол может вращаться и способы, переходящие при вращении друг в друга, считаются одинаковыми.

32. На школьном вечере присутствуют 12 девушек и 15 юношей.

Сколькими способами можно выбрать из них 4 пары?

33. Пусть п (л > 2) человек садятся за круглый вращающийся стол. Два размещения будем считать совпадающими, если каждый человек имеет одних и тех же соседей в обоих случаях. Сколько существует способов сесть за стол?

34. Хор состоит из 10 участников. Сколькими способами можно в течение трех дней выбирать по 6 участников, так, чтобы каждый день были различные составы хора?

35. Сколькими способами можно распределить Зл различных предметов между тремя людьми так, чтобы каждый получил п предметов?

36. Имеется п абонентов. Сколькими способами можно одновременно соединить три пары?

37. Сколькими способами можно составить три пары из п шахматистов?

38. Рассматриваются всевозможные разбиения 2л элементов на пары, причем разбиения, отличающиеся друг от друга порядком элементов внутри пар и порядком расположения пар, считаются совпадающими. Определить число таких разбиений.

39. Доказать, что нечетное число предметов можно выбрать из п предметов 2 1 способами.

40. Сколькими способами можно посадить рядом 3 англичан, 3

французов и 3 немцев так, чтобы никакие три соотечественника

не сидели рядом?

41. В колоде 52 карты. В скольких случаях при выборе из колоды 10 карт среди них окажутся: а) ровно один туз; б) хотя бы один туз; в) не менее двух тузов; г) ровно два туза?

42. Сколькими способами можно выбрать 6 карт из колоды, содержащей 52 карты, так, чтобы среди них были карты каждой масти?

43. На железнодорожной станции имеется т светофоров. Сколько может быть дано различных сигналов, если каждый светофор

имеет три состояния: красный, желтый и зеленый?

44. Имеется 17 пар различных предметов. Найти полное число выборок из этих предметов. Каждая пара может участвовать в выборке, предоставляя любой из двух ее элементов, или не участвовать. Выборки считаются различными, если отличаются друг от друга своим составом; порядок предметов в выборке не учитывается.

45. Найти число способов раскладки п различных шаров по т различным корзинам.

46. Найти число способов раскладки л одинаковых шаров по т различным корзинам.

47. Сколькими способами можно разместить л одинаковых шаров по т различным корзинам при следующих условиях:

а) пустых корзин нет;

б) во второй корзине k шаров;

в) в первых корзинах соответственно шаров?

48. Сколькими способами можно разместить красных, желтых и зеленых шаров по т различным урнам?

49. Сколькими способами 3 человека могут разделить между собой 6 одинаковых яблок, 1 апельсин, 1 сливу, 1 лимон, 1 грушу, 1 айву и 1 финик?

50. Поезду, в котором находится л пассажиров, предстоит сделать т остановок. Сколькими способами могут распределиться пассажиры между этими остановками?

51. Сколькими способами можно раскрасить квадрат, разделенный на четыре части, пятью цветами:

а) допуская окрашивание разных частей в один цвет;

б) если различные части окрашиваются разными цветами?

52. Сколькими способами можно выбрать 5 номеров из 36?

53. В скольких случаях при игре в Спортлото (угадывание 5 номеров из 36) будут правильно выбраны: а) ровно 3 номера; б) не

менее 3 номеров?

54. Сколько существует различных комбинаций из 30 монет достоинством 1,2 и 5 рублей (построить дереворешений, см.п.2.2.2)1

55. Сколькими способами можно раскрасить квадрат, разделенный на девять частей, четырьмя цветами таким образом, чтобы в

первый цвет были окрашены 3 части, во второй - 2, в третий - 3, в четвертый - 1 часть?

56. Определить коэффициент с в одночлене CXxf х|после разложения выражения + и приведения подобных членов.

57. Сколько делителей имеет число q = />, р\г ...р% , где# - простые числа, не равные единице, - некоторые натуральные

ла? Чему равна сумма этих делителей?

58. Доказать, что в разложении числа на простые сомножители

Г 1 г т г 1 простое число р входит с показателем Иг +1 +. - +. .

LP j ~LV J LC J

59. Из выбранных k различных чисел от 1 до л составляют произведение, k фиксировано. Какое количество полученных таким образом произведений делится на простое числор < п?

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

На шахматную доску п х п произвольным образом поставили две ладьи - черную и белую. Что вероятнее: ладьи друг друга

или нет?

62. Доказать, что из пяти грибов, растущих в лесу и не расположенных на одной прямой, всегда можно найти четыре таких, которые служат вершинами вьтуклого четырехугольника.

63. В розыгрыше первенства мира по футболу участвуют 20 команд. Какое наименьшее число игр должно быть сыграно, чтобы среди любых трех команд нашлись две, уже игравшие между собой?

64. Некая комиссия собиралась 40 раз. Каждый раз на заседаниях присутствовали по 10 человек, причем никакие двое из ее членов не были на заседаниях вместе больше одного раза. Доказать, что число членов комиссии больше 60.

65. В некотором учреждении 25 сотрудников. Доказать, что из них нельзя составить больше 30 комиссий по 5 человек в каждой так, чтобы никакие две комиссии не имели более одного общего члена.

66. В соревнованиях по гимнастике две команды имели одинаковое число участников. В итоге, общая сумма баллов, полученных всеми участниками, равна 156. Сколько было участников, если каждый из них получил оценки только 8 или 9 баллов?

67. Группа из 41 студента успешно сдала сессию из трех экзаменов. Возможные оценки: 5,4,3. Доказать, что, по крайней мере,

пять студентов сдали сессию с одинаковыми оценками.

68. Поступающий в высшее учебное заведение должен сдать четыре экзамена. Он полагает, что для поступления будет достаточно набрать 17 баллов. Сколькими способами он сможет сдать экзамены, набрав не менее 17 баллов и не получив ни однойдвойки (построить дерево решений, см.п.2.2.2)1

69. Каких чисел больше среди первого миллиона: тех, в записи которых встречается или тех, в записи которых ее нет?

70. Пусть числа 1, 2,..., л расположены подряд по кругу. Двигаясь по кругу, вычеркиваем каждое второе число. Показать, что последнее не вычеркнутое число равно 2л 2log2n+1 +1.

71. Сколькими способами можно число п представить в виде суммы k слагаемых (представления, отличающиеся лишь порядком слагаемых, считаются различными), если: а) каждое слагаемое является целым неотрицательным числом; б) каждое слагаемое - натуральное число?

72. Какова таблица инверсий для перестановки 271845936?

73. Какой перестановке соответствует таблица инверсий 50121200?

74. Пусть перестановке ayflv..an соответствует таблица инверсий dyd2...dn. Какой перестановке тогда будет соответствовать следующая таблица инверсий (и - 1 - dx)(n - 2 - d2)...(0 - d )7

75. На окружности произвольным образом отмечают л точек буквой Nh т точек буквой М. На каждой из дуг, на которые окружность делится выбранными точками, ставят числа 2 или 1/2 следующим образом: если концы дуги отмечены буквой N, то ставят число 2; если концы дуги отмечены буквой М, то ставят число 1/2; если же концы дуги отмечены различными буквами, ставят число 1. Доказать, что произведение всех поставленных чисел равно

16. Сколькими способами можно распределить Зл различных книг между тремя лицами так, чтобы числа книг образовывали арифметическую прогрессию?

77. Рассматриваются всевозможные разбиения nk элементов на п групп по k элементов в каждой, причем разбиения, отличающиеся друг от друга только порядком элементов внутри групп и порядком расположения групп, считаются совпадающими. Сколько существует различных таких разбиений?

78. Сколькими способами можно разбить 30 рабочих на 3 бригады: по 10 человек в каждой бригаде? На 10 групп по 3 человека в

каждой группе?

79. Сколькими способами можно разделить колоду из 36 карт пополам так, чтобы в каждой пачке было по два туза?

80. Сколькими способами можно разложить 10 книг в 5 бандеролей по 2 книги в каждую (порядок бандеролей не принимается во

внимание)?

81. Сколькими способами можно разложить 9 книг в 4 бандероли

по 2 книги и в 1 бандероль 1 книгу (порядок бандеролей не принимается во внимание)?

82. Сколькими способами можно разделить 9 книг в 3 бандероли по 3 книги в каждую (порядок бандеролей не принимается во внимание)?

83. На первые две линии шахматной доски выставляют белые и черные фигуры (по два коня, два слона, две ладьи, ферзя и короля

каждого цвета). Сколькими способами можно это сделать?

84. Сколькими способами можно расположить в 9 лузах 7 белых

шаров и 2 черных шара? Часть луз может быть пустой, и лузы считаются различными.

85. В лифт сели 8 человек. Сколькими способами они могут выйти на четырех этажах так, чтобы на каждом этаже вышел, по крайней мере, один человек?

86. Доказать, что число упорядоченных разбиений числа л на k натуральных слагаемых, т. е. число решений уравнения п =щ + +х2 + ... +хк, Xj О.г 1, 2,..., к, равноС*, /, а общее число упоря-

доченных разбиений для различных k равно

87. Сколькими способами можно разложить п различных шаров

по k различным корзинам так, чтобы в первую корзину попало шаров, во вторую корзину попало шаров и в корзину попало пк шаров, где п = пх+ п2 + ... + пк?

88. Сколько существует чисел от 0 до которые не содержат две идущие друг за другом одинаковые цифры?

89. Сколько существует натуральных у которых

цифры расположены в неубывающем порядке?

90. Сколько существует натуральных чисел, не превышающих 10 , у которых цифры расположены в неубывающем порядке?

91. Сколькими способами можно расставить п нулей и k единиц так, чтобы никакие две единицы не стояли рядом?

92. Город имеет вид прямоугольника, разделенного улицами на квадраты. Число таких улиц в направлении с севера на юг равно п, а в направлении с востока на запад - к. Сколько имеется кратчайших дорог от одной из вершин прямоугольника до противоположной?

93. Как разбить квадратное поле на участки так, чтобы высеять на нем т сортов пшеницы для сравнения урожайности этих сортов, исключающего влияние изменения плодородия в пределах участка? Считаем, что плодородие убывает при удалении от одной стороны поля (неизвестно, какой именно) к противоположной.

94. Бросают т игральных костей, помеченных числами 1, 2, 3, 4, 5, 6. Сколько может получиться различных результатов (результаты, отличающиеся порядком очков, считаются одинаковыми)?

95. Имеем т различных шаров и £ различных корзин. Сколькими способами можно разместить предметы по корзинам, допускаются пустые корзины?

96. Имеем т различных шаров и различных корзин. Сколькими способами можно разместить предметы по корзинам, пустые корзины не допускаются? Указание: воспользоваться правилом включения и исключения.

97. Найти число способов разложения т шаров по k корзинам так, чтобы корзин остались пустыми. Указание:

правилом включения и исключения.

98. Имеем т различных шаров а- а2,..., ат и столько же различных корзин кь к2,..., кт. Сколькими способами можно разместить предметы по корзинам так, чтобы никакой предмет а, не попал в корзину (допускаются пустые корзины)? Указание: воспользоваться правилом включения и исключения.

99. Задача о беспорядках. Имеем т различных шаров аи а2,..., атж столько же различньгх корзин kuk2,..., km. Сколькими способами можно разместить предметы по корзинам так, чтобы никакой предмет не попал в корзину пустые корзины не допускаются? Указание: воспользоваться правилом включения и исключения.

100. Найти число перестановок т шаров, в которых ровно г элементов остаются на месте. Указание: воспользоваться правилом включения и исключения.

101. Доказать, что различных вещей можно разделить между п + р людьми так, чтобы данные п людей получили, по крайней мере, по одному предмету, способами C(n+p)r -Cl(n+p-l)r + +C;(r, +р-2)г-...+(-1) С',!(п + р-п)г Указание: воспользоваться правилом включения и исключения.

102. Рыцарские переговоры. К обеду за круглым столом приглашены п пар враждующих рыцарей, п 2. Требуется рассадить их так, чтобы никакие два врага не сидели рядом. Показать, что это мож-

сделать

правилом включения и исключения.

103. Найти число целых положительньгх чисел, не превосходящих 1000 и не делящихся ни на одно из чисел 3, 5 и 7.

104. Найти число целых положительных чисел, не превосходящих 1000 и не делящихся ни на одно из чисел 6, 10 и

105. Показать, что если п = 30т, то число целых, не превосходящих л и не делящихся ни на одно из чисел 6, 10, 15, равно 22т.

106. При обследовании читательских вкусов студентов оказалось, что 60% студентов читаютжурнал А, 50% - журнал В, 50% - журнал С, 30% - журналы и В, 20% - журналы В и С, 40% - жур-налАиС, 10% - журналы А, В и С. Сколько процентов студентов а) не читают ни одного из журналов; б) читают в точности два журнала; в) читают не менее двух журналов?

107. На одной из кафедр университета работают тринадцать человек, причем каждый из них знает хотя бы один иностранный

язык. Десять человек знают английский, семеро - немецкий, ше-

стеро - французский. Пятеро знают английский и немецкий,

четверо - английский и французский, трое - немецкий и французский. Найти: а) сколько человек знают все три языка; б) сколько знают ровно два языка; в) сколько знают только английский?

108. Имеются Зп + 1 предметов (п одинаковых, остальные различны). Доказать, что из них можно извлечь п предметов 22 способами.

109. Применяя формулу включения и исключения, определить количество целочисленных решений системы уравнений и неравенств: X] + л'2 + ... + = г, а, < х,< Ъь1 - \,п, ahxn b - целые числа.

110. Определить количество целочисленных решений системы jq + х2 + х3 = 40, хх >3,х2> О, х3 > 2.

111. Компания, состоящая из 10 супружеских пар, разбивается на 5 групп по 4 человека для лодочной прогулки. Сколькими способами можно разбить их так, чтобы в каждой лодке оказались двое

мужчин и две женщины?

112. Имеем п предметов, расположенных в ряд. Сколькими способами можно выбрать из них три предмета так, чтобы не брать

никаких двух соседних элементов?

113. Даны 2п различных предметов аь щ, аъ а2,..., ап, ап. Сколько существует перестановок из этих 2л предметов, в которых не стоят рядом одинаковые элементы?

114. В шахматной олимпиаде участвуют представители п стран по

4 представителя от каждой страны. Сколькими способами они

могут встать в ряд так, чтобы рядом с каждым был представитель

той же страны?

115. Имеется п одинаковых вещей и еще п различных вещей. Сколькими способами можно выбрать из них п вещей? Сколькими способами можно упорядочить все 2л вещей?

116. Найти число способов распределения 2л одинаковых шаров по двум неразличимым корзинам.

117. В каждой клетке шахматной доски размером п х п поставили число, указывающее количество прямоугольников, в которые входит эта клетка. Чему равна сумма всех поставленных чисел?

118. Найти число расстановок/гладей так, чтобы они не били друг друга, на доске п х л (см. случаи а, 6, в) с выколотыми или добавленными клетками. В случае в) использовать п ладей.

гтт п~т lxu

о ф

Производящие функции и рекуррентные

119. Найти производящую функцию последовательности {2(л- 5) + Т+г).

120. Применить технику производящих функций для нахождения суммы чисел 1 + 23 + ... + л .

121. Решить рекуррентные соотношения:

1) ип+2. 4ип+1 + Зип= 0, о = 8, i = 10;

2) ы„+3 - Зи +2 + н„+1 - Ъм = 0, щ = 1, щ = 3, и2 = 8;

3) ы„+2 ± 9н„ = 0, и0 = 1, = 0;

4) ы„+4 + 4и = 0, м0= 1, i=l, w2= 1, м3=1;

5) я+з + +2 - *Vi -ип = 0,щ= 1, , = 2, м2 = 3;

6) ип+2 - 4м„+1 + 4ия = 0, и0 = 1, щ = 2.

122. Решить неоднородные рекуррентные соотношения: !) un+i = ип+ п, o = li

2) +2 = -2ил+1 + 8и„ + 27 5л, ио = 0,щ = - 9;

3) ы„+2 - Зыл+1 + 2и„ = л, w0= 1, = 1;

4) м„+2 - 4и„+1 + 4и„ = 2я, м0 = 1, i = 2;

5) +2 = - - п + 2 , о = 1. Щ = 3/2;

6) и„+2 - Зил+1 + 2и„ = (-1) , щ = 1, ! = 2.

123. Последовательность Фибоначчи { } задается рекуррентным соотношением м„+2 = и„+1 + w , и0 = 1, wt = 1. Найти ы„; показать, что и„ и м„+2 - взаимно простые числа и ип делится на ит, где л = т к.

124. Найти общее решение рекуррентных соотношений:

2) - 4ия+1 + = 0;

3) и+2 - - й = 0.

125. Найти решение системы рекуррентных соотношений:

126. Найти число решений уравнениях + 2у = п, гдех, у, л е Z+ -положительные целые числа; х, у - неизвестные.

127. Найти число решений уравнения х + 2у + 4z= п, х, у, я е Z+, х, у, z - неизвестные.

соотношения

128. Найти определитель матрицы ос+р ар 1 а + р ар

1 а + р ар

а + Р ар 1 а+Ру

где а, р - произвольные числа; вне обозначенных диагоналей матрицы располагаются нули.

129. Вычислитьсумму £ (1 / 2 *) где суммирование производится

по всем натуральным к, не кратным 2, 3 и 5.

130. Найти ладейный многочлен запрещенных позиций для досок а) и Ь) и для каждого из этих случаев составить многочлен попаданий. Для доски с) составить многочлен запрещенных позиций. Для досок а), Ъ) и с) найти число расстановок трех ладей на

запрещенных позициях.

а} Ы с) d)

131. Найти число способов расставить 5 ладей на доске 5 к 5 так, чтобы ни одну из них не бил слон. Позиция слона указана на доске символом с .

132. Найти число способов расставить 5 ладей на доске 5x5 так, чтобы ни одну из них не бил конь. Позиция коня указана на доске d) символом к .

133. Найти число замкнутых маршрутов длины 2л по ребрам графа для случаев а), Ь)жс). Длина ребра равна 1. Начало и конец пути есть вершина А.

с

В

Е