МАЛЫЙ МЕХМАТ МГУ

В классе учатся 20 человек. Сколькими способами из них можно выбрать двоих школьников: старосту и ответственного за проездные билеты? А просто двоих школьников?
 

Сколько разных слов (не только осмысленных) можно получить, переставляя буквы в словах а) РОК; б) КУРОК; в) КОЛОБОК; г) АА...АББ...Б (a букв А и b букв Б); д) б₁б₁...б₁б₂б₂...б₂ ... ... б_mб_m...б_m (k₁ букв б₁, k₂ букв б₂, ..., k_m букв б_m).
 

а) Сколькими способами можно выбрать трёх дежурных в классе из 20 человек?
б) А сколькими способами можно выбрать старосту, его помощника и трёх дежурных?
 

Докажите, что а) C_n^k=C_n^n-k; б) C_n+1^k=C_n^k+C_n^k-1.
 

Найдите формулу для C_n^k.
 

а) На рисунке изображен план города (линии — это улицы, пересечения линий — перекрестки). На улицах введено одностороннее движение: можно ехать только «вверх» или «вправо». Сколько разных маршрутов ведёт из точки A в точку B?
б) Сколько из этих маршрутов не проходят через отмеченную на плане точку внутри города?
 

Сколькими способами можно рассадить класс, если пришло 27 человек, а мест 30?
 

Сколькими способами можно высадить в ряд 3 груши и 4 яблони?
 

На рисунке выписаны первые 5 строк треугольника Паскаля. Напишите следующие 5 строк.
 

Докажите, что k-ое число n-ой строки равно C_n^k (строки нумеруются сверху вниз, начиная с нуля, а числа в строках нумеруются слева направо, также начиная с нуля).
 

Докажите, что сумма чисел в n-ой строке треугольника Паскаля равна 2ⁿ.
 

Докажите тождество: C_n¹+2C_n²+3C_n³+...+nC_nⁿ=n2^n–1.
 

а) Раскройте скобки и приведите подобные в выражениях (a+b)², (a+b)³, (a+b)⁴.
б) (Бином Ньютона) Раскроем скобки и приведём подобные в выражении (a+b)ⁿ. Возьмём любое слагаемое. Оно имеет вид C·a^k·b^n–k (почему?). Докажите, что C=C_n^k.
 

Докажите тождество C_n⁰–C_n¹+C_n²–C_n³+...+(–1)ⁿC_nⁿ=0.
 

Возьмём любое число C в треугольнике Паскаля и сложим все числа, начиная с него и идя по прямой направо-вверх. Докажите, что сумма равна числу, стоящему под C справа.
 

Выведите из задачи 15 формулы для сумм 1+...+n, T₁+...+T_n, П₁+...+П_n.
 

Как из предыдущей задачи вывести формулы для 1²+...+n², 1³+...+n³, ... ?
 

В каких строках треугольника Паскаля все числа нечётные?
 

Докажите, что C_p⁰·C_q^m+C_p¹·C_q^m–1+...+C_p^m–1·C_q¹+C_p^m·C_q⁰=C_p+q^m.
 

а) В НИИ работают 67 человек. Из них 47 знают английский язык, 35 — немецкий, и 23 — оба языка. Сколько человек в НИИ не знают ни английского, ни немецкого языков?
б) Пусть кроме этого польский знают 20 человек, английский и польский — 12, немецкий и польский — 11, все три языка — 5. Сколько человек не знают ни одного из этих языков?
в)* (Формула включений и исключений) Решите задачу в общем случае: имеется m языков, и для каждого набора языков известно, сколько человек знают все языки из этого набора.
 

В ряд записали 105 единиц, поставив перед каждой знак «+». Сначала изменили знак на противоположный перед каждой третьей единицей, затем — перед каждой пятой, а затем — перед каждой седьмой. Найдите значение полученного выражения.
 

а) На полке стоят 10 книг. Сколькими способами их можно переставить так, чтобы ни одна книга не осталась на месте? б) А если на месте должны остаться ровно 3 книги?