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

Листок 3.  Комбинаторика

1.  

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

2.  

Сколько разных слов (не только осмысленных) можно получить, переставляя буквы в словах а) РОК; б) КУРОК; в) КОЛОБОК; г) АА...АББ...Б (a букв А и b букв Б); д) б1б1...б1б2б2...б2 ... ... бmбm...бm (k1 букв б1, k2 букв б2, ..., km букв бm).
 

3.  

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

Определение 1. Числом сочетаний из n элементов по k называется количество способов выбрать k предметов из n различных предметов. Обозначение: Cnk (читается «це из n по k»).
 
4.  

Докажите, что а) Cnk=Cnn-k; б) Cn+1k=Cnk+Cnk-1.
 

5.  

Найдите формулу для Cnk.
 

6.  

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

7.  

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

8.  

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

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

1
11
121
1331
14641
......

 
9.  

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

10.  

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

11.  

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

12.  

Докажите тождество: Cn1+2Cn2+3Cn3+...+nCnn=n2n–1.
 

13.  

а) Раскройте скобки и приведите подобные в выражениях (a+b)2, (a+b)3, (a+b)4.
б) (Бином Ньютона) Раскроем скобки и приведём подобные в выражении (a+b)n. Возьмём любое слагаемое. Оно имеет вид C·ak·bn–k (почему?). Докажите, что C=Cnk.
 

14.  

Докажите тождество Cn0Cn1+Cn2Cn3+...+(–1)nCnn=0.
 

15.  

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

16.  

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

17*.  

Как из предыдущей задачи вывести формулы для 12+...+n2, 13+...+n3, ... ?
 

18*.  

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

19*.  

Докажите, что Cp0·Cqm+Cp1·Cqm–1+...+Cpm–1·Cq1+Cpm·Cq0=Cp+qm.
 

***
20.  

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

21.  

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

22.  

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



Вы видите ошибку? Выделите её и нажмите Ctrl+Enter! Rambler's Top100
liveinternet.ru
Apache
PHP
HTML 4.01
CSS