Определение: множество А называется счетным, если оно равномощно множеству натуральных чисел.
Т1: Множество А счетное ⇔ его элементы можно расположить в виде бесконечной последовательности, тоесть занумеровать: А={a1,a2…}
Т2: Из всякого бесконечного множества можно выделить счетное подмножество
Т3:Объединение двух счетных множеств – счетно
Т4: Объединение счетного числа счетных множеств- счетно
Теорема Кантора: Интервал (0,1) – несчетное множество.
Докозательство: Пусть (0,1) – счетное множество, значит элементы можно пронумеровать. Будем каждый элемент записывать в виде бесконечной дроби
1 элемент:0, a11,a12,a13…….a1n
2 элемент:0, a21,a22,a13…….a2n
…………………………..
n элемент:0, an1,an2,an3…….ann
все эти элементы находятся в интервале (0,1). Возьмем такое число e которое присутствует в интервале (0,1), но отсутствует в нашем перечислении:
0, b1,b2,b3…..bn, очевидно, что элемент b1 не совпадает с элементом a11, аналагично и для других элементов, тоесть мы перечислили не все числа, что и требовалось доказать.
Действительных чисел больше
Оперделение: мощность множества действительных чисел называется мощностью континуума
Определение: множество, не являющееся счетным называется несчетным.
Основной принцип комбинаторики. Перестановки, сочетания, размещения. Перестановки и сочетания с повторениями. Формула включений и исключений, число беспорядков. Биномиальная и полиномиальная формулы.
Определение: Комбинаторика – часть математики, изучающая способы подсчета количества расположений или комбинаций элементов, удовлетворяющих заданным условиям.
Принципы:
1) Основной принцип умножения:
A – выбрать, n – способами, после этого нужно выбрать ситуацию B m – способами. Сколькими способами выбрать А и В? (А;В) – декартов квадрат, значит это можно сделать m*n способами
2) Принцип сложения:
Пусть для А и В n и m способов соотвественно и они различны, значит А или В можно выбрать n+m способами
Пример: сколько 3х значных чисел? 9*10*10=900
Определение: перестановками называют комбинации, состоящие из одних и тех же n различных элементов и отличающиеся только порядком их расположения: Pn=n!;
Пример: сколько 3х значных чисел можно составить из цифр 1,2,3, если каждая цифра входит в изображение числа только 1 раз: P3=1*2*3=3!=6;
Определение: размещением называют комбинации, составленные из n различных элементов по m элементов, отличающихся либо составом элементов, либо их порядком:
Пример: сколько можно составить сигналов из 6 флажков, взятых по 2?
A26= 6*5=30;
Определение: сочетаниями называются комбинации составленные из различных элементов n по m, отличающихся хотя бы одним элементом:
Пример: сколькими способами можно вытащить из ящика, содержащих 10 деталей, 2 детали:
С210=10!/(2!*8!)=45
Мы предполагали, что все n элементов различны. Если же некоторые из элементов повторяются, то комбинации с повторениями вычисляются иначе.
