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

Определение: множество А называется счетным, если оно равномощно множеству натуральных чисел.

Т1: Множество А счетное ⇔ его элементы можно расположить в виде бесконечной последовательности, тоесть занумеровать: А={a1,a2…}

Т2: Из всякого бесконечного множества можно выделить счетное подмножество

Т3:Объединение двух счетных множеств – счетно

Т4: Объединение счетного числа счетных множеств- счетно

Теорема Кантора: Интервал (0,1) – несчетное множество.

Докозательство: Пусть (0,1) – счетное множество, значит элементы можно пронумеровать. Будем каждый элемент записывать в виде бесконечной дроби

1 элемент:0, a₁₁,a₁₂,a₁₃…….a_1n

2 элемент:0, a₂₁,a₂₂,a₁₃…….a_2n

_{…………………………..}

_n элемент:0, a_n1,a_n2,a_n3…….a_nn

все эти элементы находятся в интервале (0,1). Возьмем такое число e которое присутствует в интервале (0,1), но отсутствует в нашем перечислении:

0, b₁,b₂,b₃…..bn, очевидно, что элемент b₁ не совпадает с элементом a_11, аналагично и для других элементов, тоесть мы перечислили не все числа, что и требовалось доказать.

 

Действительных чисел больше

Оперделение: мощность множества действительных чисел называется мощностью континуума

Определение: множество, не являющееся счетным называется несчетным.

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

 

Определение: Комбинаторика – часть математики, изучающая способы подсчета количества расположений или комбинаций элементов, удовлетворяющих заданным условиям.

 

Принципы:

1) Основной принцип умножения:

A – выбрать, n – способами, после этого нужно выбрать ситуацию B m – способами. Сколькими способами выбрать А и В? (А;В) – декартов квадрат, значит это можно сделать m*n способами

 

2) Принцип сложения:

Пусть для А и В n и m способов соотвественно и они различны, значит А или В можно выбрать n+m способами

Пример: сколько 3х значных чисел? 9*10*10=900

 

Определение: перестановками называют комбинации, состоящие из одних и тех же n различных элементов и отличающиеся только порядком их расположения: P_n=n!;

 

Пример: сколько 3х значных чисел можно составить из цифр 1,2,3, если каждая цифра входит в изображение числа только 1 раз: P₃=1*2*3=3!=6;

 

Определение: размещением называют комбинации, составленные из n различных элементов по m элементов, отличающихся либо составом элементов, либо их порядком:

Пример: сколько можно составить сигналов из 6 флажков, взятых по 2?

A²₆= 6*5=30;

 

Определение: сочетаниями называются комбинации составленные из различных элементов n по m, отличающихся хотя бы одним элементом:

Пример: сколькими способами можно вытащить из ящика, содержащих 10 деталей, 2 детали:

 

С²₁₀=10!/(2!*8!)=45

 

Мы предполагали, что все n элементов различны. Если же некоторые из элементов повторяются, то комбинации с повторениями вычисляются иначе.