1. Построить биекцию из .

2. Установить взаимно однозначное соответствие между двумя отрезками.

3. Докажите, что

1. множество целых чисел счетно;

2. множество нечетных чисел четно;

3. множество рациональных чисел Q cчетно;

4. множество пар < у >, где у  Q счетно;

5. множество многочленов от одной переменной с целыми коэффициентами счетно;

6. любое множество попарно непересекающихся кругов на плоскости счетно;

7. множество алгебраических чисел, т.е. являющихся корнями многочленов от одной переменной с целыми коэффициентами, счетно;

8. интервал (а,b) имеет мощность континуум;

9. множество иррациональных чисел несчетно;

10. множество трансцендентных чисел несчетно.

Комбинаторика

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

Правило суммы. Если объект может быть выбран m способами, а объект В другими n способами, то выбор "либо , либо " может быть осуществлен способами.

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

Размещения

Размещением из n элементов по к называется любое множество, состоящее из любых к элементов, взятых в определенном порядке из данных n элементов.

.

Сочетания

Сочетанием из n элементов по к называется любое множество, состоящее из к элементов, из данных n элементов.

.

Перестановки

Перестановкой из n элементов называется каждое расположение этих элементов в определенном порядке.

.

Бином Ньютона

Здесь числа называются биномиальными коэффициентами.

Свойства бинома Ньютона:

1. степени a убывают в слагаемых правой части от n до 0;

2. степени b возрастают от 0 до n;

3. в каждом слагаемом сумма степеней a и b равна n;

4. коэффициенты при симметричны относительно середины суммы.

При a = b = 1 из формулы Ньютона получим

Если положить a = 1, b = –1, то получим

Размещения с повторениями

Число (k, n) – размещений с повторениями обозначается через .

Сочетания с повторениями

Число (k, n) – сочетаний с повторениями обозначается через и равно .

Упражнения для самостоятельного решения.

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

2. Сколько существует четырехзначных чисел, у которых все цифры нечетные? Сколько существует четырехзначных чисел, в записи которых есть хотя бы одна четная цифра?

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

4. Сколько шестизначных чисел кратных 5 можно составить из цифр 0, 1, 2, …, 9 при условии, что цифры в записи не повторяются?

5. Сколькими способами можно расставить на книжной полке десятитомник Пушкина так, чтобы том 2 стоял рядом с томом 1 и справа от него?

6. Из 15 членов группы надо выбрать 3 дежурных. Сколькими способами можно сделать этот выбор?

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

8. Хоккейная команда состоит из 2 вратарей, 7 защитников, 10 нападающих. Сколько способов у тренера для образования стартовой шестерки из 1 вратаря, 2 защитников, 3 нападающих?

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

10. Сколько различных четырехзначных чисел, в которых цфры не повторяются можно составить из цифр 0, 2, 4, 6?

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

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

а) Олег должен находиться в конце ряда;

б) Олег в начале ряда, Игорь в конце;

в) Олег и Игорь должны стоять рядом.

11. Пассажир оставил вещи в камере хранения, а когда пришел получать вещи выяснилось, что он забыл номер. Он только помнит, что в номере были числа 23 и 37. Чтобы открыть камеру нужно правильно набрать пятизначный номер. Какое наибольшее количество номеров нужно перебрать, чтобы открыть камеру?

12. Если р₁, р₂, …, р_к – различные простые числа, а а₁, а₂, …, а_к – натуральные числа, то сколько делителей имеет число .

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

14. Сколько имеется трехзначных чисел, в запись которых входит хотя бы одна цифра 5?

15. Определить коэффициент при х¹⁹ в разложении .

16. Найти наибольший коэффициент многочлена .

17. В разложении четвертый член равен 0,96. Найти значения x и n, если сумма биномиальных коэффициентов равна 1024.

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

19. Сколькими способами можно разместить в ряд шаров, из которых p белых и q черных (p > q), при условии, что черные шары не могут лежать рядом.

20. Докажите: a) ;

б) ;

в) ;

21. Определить коэффициент с в слагаемом после разложения и приведения подобных членов.

22. Определить сколько рациональных членов содержится в разложении

а) ;

б) .

23. В группе студентов 25 человек. Среди них 20 сдали сессию успешно, 12 занимаются в спортивных секциях, причем 10 из них сдали сессию успешно. Сколько неуспевающих студентов не посещает спортивных секции.

24. В классе 35 учеников, 20 из них занимаются в математическом кружке, 11 в биологическом, 10 ничем не занимаются. Сколько ребят занимается и математикой и биологией.

25. На дискотеке 80% времени был выключен свет, 90% играла музыка, 50% шел дождь. Какую наименьшую долю времени все это обязано было происходить одновременно?