ТГиК-2019-Лекция-16.09.2019: различия между версиями

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску
Строка 40: Строка 40:
 
<math>A \sim B \Longleftrightarrow \exists f:A \longleftrightarrow B </math>  
 
<math>A \sim B \Longleftrightarrow \exists f:A \longleftrightarrow B </math>  
  
То есть можно составить отношение эквивалентности между А и В тогда и только тогда, когда можно построить биекцию.
+
Биективное отображение - это отношение эквивалентности. Рассмотрим 3 условия отношения эквивалентности и проверим их для биекции
  
Отношение эквивалентности - это:  
+
1) <math> A \sim A \mbox{, так как } \exists f \mbox{: } A \longleftrightarrow A \mbox{: } f(a)=a; </math>
  
1) <math> A \sim A, \mbox{ так как } \exists \mbox{:
+
2) <math> A \sim B \Longrightarrow B \sim A \mbox{, так как раз это биекция, то существует обратное отображение } f^{-1} \mbox{, которое переводит B в A;} </math>
  
2)
+
3) <math> A \sim B \mbox{ (отображение f), } B \sim C \mbox{ (отображение g), } \Longrightarrow A \sim C \mbox{ (отображение fg) } </math>
  
3)
+
=== Фактор-множество ===
 +
Пусть <math>\rho </math> - отношение эквивалентности на А. Тогда фактор-множество <math> A/ \rho </math> - это набор подмножеств <math> A_i \mbox{ : } \exists a\in A : \forall a' \in A_i \Longrightarrow (a, a') \in \rho </math>
  
=== Фактор-множество ===
+
У данного набора подмножеств есть некоторое свойство: <math>A_i \cap A_j = \varnothing \Longleftrightarrow i \neq j </math>
Пусть - отношение эквивалентности на А. Тогда фактор-множество - это
 
  
Свойство:
+
Доказательство.
  
Доказательство свойства.
+
Доказательство проведём от противного
  
1) Пусть <math> \exists i j: A_i \ A_j = \left \{ b_1 , b_2 , ... , b_n \right \}  
+
1) Пусть <math> \exists i \mbox{, } j: A_i \cap A_j = \left \{ b_1 , b_2 , ... , b_n \right \} </math>
  
2) Так как b_1 \in A_i , то  
+
2) Так как <math> b_1 \in A_i </math>, то <math> \forall a' \in A_i \mbox{ : } a' \rho \mbox{ } b_1 </math>
  
Так как b_1 \in A_j , то  
+
Так как <math> b_1 \in A_j </math>, то <math> \forall a'' \in A_j \mbox{ : } a'' \rho \mbox{ } b_1 </math>
  
Значит, так как p - отношение эквивалентности,  
+
Значит, так как <math>\rho </math> - отношение эквивалентности, <math> a' \rho \mbox{ } a'' </math>
  
Следовательно, A_i = A_j
+
Следовательно, <math> A_i = A_j </math>
  
 
=== Разбиение ===
 
=== Разбиение ===
 
  
 
==Бином Ньютона==
 
==Бином Ньютона==

Версия 13:53, 15 декабря 2019

Биекция и её полезные свойства

В предыдущей лекции мы условились, что для конечного множества его мощность - это количество элементов в данном множестве. Расширим это определение.

Мощность множества - это класс эквивалентности по отношению существования биективного отображения.

Биекция и мощность множеств

Теорема. Если между множествами А и В можно построить биективное отображение, то их мощности равны и наоборот.

Доказательство

Доказательство проведём по индукции.

1) Рассмотрим случай пустого множества.

\( \left | \varnothing \right | = 0\)

Для пустого множества можно составить биекцию только с пустым множеством. Тогда \(0=0\), теорема выполняется

2) Пусть \(A=\left \{a \right \}\), \(B=\left \{b \right \}\)

Между множествами А и В можно установить биекцию \(\left \{a \right \} \longleftrightarrow \left \{b \right \}\)

Из условия \( \left |A \right | = \left |B \right | \), и мы смогли построить биекцию.

3) Предположение \( \left |A \right | = \left |B \right | \Longleftrightarrow \exists f:A \longleftrightarrow B \)

4) Пусть \( \exists C, D: \left | C \right | = n + 1; \) \(\exists f:C \longleftrightarrow D \)

5) Из биекции следует, что \( \forall c \in C\) \(\exists f(c) = d; \)

6) Тогда \( f: C \backslash \left \{c \right \} \longleftrightarrow D \backslash \left \{d \right \}\)

7) Так как мы исключили один элемент c, то \(\left |C \backslash \left \{c \right \} \right | = n\). Из биекции следует, что для D \(\left |D \backslash \left \{d \right \} \right | = n\)

8) "Вернём" элемент d и по правилу сложения получим, что \(\left |D \right | = n+1\)

Теорема доказана.

Биекция и эквивалентность множеств

\(A \sim B \Longleftrightarrow \exists f:A \longleftrightarrow B \)

Биективное отображение - это отношение эквивалентности. Рассмотрим 3 условия отношения эквивалентности и проверим их для биекции

1) \( A \sim A \mbox{, так как } \exists f \mbox{: } A \longleftrightarrow A \mbox{: } f(a)=a; \)

2) \( A \sim B \Longrightarrow B \sim A \mbox{, так как раз это биекция, то существует обратное отображение } f^{-1} \mbox{, которое переводит B в A;} \)

3) \( A \sim B \mbox{ (отображение f), } B \sim C \mbox{ (отображение g), } \Longrightarrow A \sim C \mbox{ (отображение fg) } \)

Фактор-множество

Пусть \(\rho \) - отношение эквивалентности на А. Тогда фактор-множество \( A/ \rho \) - это набор подмножеств \( A_i \mbox{ : } \exists a\in A : \forall a' \in A_i \Longrightarrow (a, a') \in \rho \)

У данного набора подмножеств есть некоторое свойство\[A_i \cap A_j = \varnothing \Longleftrightarrow i \neq j \]

Доказательство.

Доказательство проведём от противного

1) Пусть \( \exists i \mbox{, } j: A_i \cap A_j = \left \{ b_1 , b_2 , ... , b_n \right \} \)

2) Так как \( b_1 \in A_i \), то \( \forall a' \in A_i \mbox{ : } a' \rho \mbox{ } b_1 \)

Так как \( b_1 \in A_j \), то \( \forall a'' \in A_j \mbox{ : } a'' \rho \mbox{ } b_1 \)

Значит, так как \(\rho \) - отношение эквивалентности, \( a' \rho \mbox{ } a'' \)

Следовательно, \( A_i = A_j \)

Разбиение

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

Формула для двух элементов:

\( (a+b)^n=(a+b)*(a+b)*...*(a+b)=\sum^{n}_{k=0} {C^k_n*a^k*b^{n-k}}\)

Формула для n элементов:

\( (a_{1} + a_{2} +...+ a_{n})^{n} = \sum {P^{i1,...,im}_{n}} {a^{i1}_1 a^{i2}_2 ... a^{im}_m} \)

Как найти \(P^{i1,...,im}_{n} \) ?

\(P^{i1,...,im}_{n} = C^{i1}_n * C^{i2}_{n-i1} * C^{i3}_{n-i1-i2} *...* C^{im}_{n-i1-...-im} = \frac{n!}{i1!*(n-i1)!} * \frac{(n-i1)!}{i2!*(n-i1-i2)!} * \frac{(n-i1-i2)!}{i3!*(n-i1-i2-i3)!} *...* \frac{(n-i1-...-i(m-1))!}{im!*0!} = \frac {n!}{i1!*i2!*...*im!} \)

Число \(P^{i1,...,im}_{n} \) называется числом перестановок с повторениями.

Свойства комбинаторных величин

1) \( C^k_n = C^{n-k}_n \)

\( C^k_n = \frac {n!}{k!*(n-k)!} \)

\( C^{n-k}_n = \frac {n!}{(n-k)!*k!} \)

Связь треугольника Паскаля и свойства 2

Следовательно, они равны

2) \( C^{k+1}_{n+1} = C^k_n +C^{k+1}_n \)

Нужно выбрать k+1 элемент из множества n+1 элементов. Вариантов выбора два:

  1. Фиксируем \(a_1\). В множестве "свободных" элементов остается \(n\) штук. Так как один элемент уже зафиксирован, то остаётся выбрать ещё \(k\) элементов. Вариантов выбора \(C^k_n\)
  2. Рассмотрим выбор, когда нет \(a_1\). Нужно выбрать \(k+1\) элементов из \(n\) штук. Вариантов выбора \(C^{k+1}_n\)

3) \( C^{k+1}_{n+1} = \frac {(n+1)!}{(k+1)!*(n-k)!} = \frac {n!}{k!*(n-k)!} * \frac{n+1}{k+1} = \frac{n+1}{k+1} * C^k_n \)

Здесь часть кода

4) \((1+1)^n = 2^n = \sum^{n}_{k=0} {C^k_n} \)

\(2^n\) - это количество подмножеств данного множества

5) \((2+1)^n = \sum^{n}_{k=0} {C^k_n * 2^k} \)

\(3^n\) - это количество подмножеств произвольного подмножества данного множества

6) \( (1-1)^n = 0 = \sum^{n}_{k=0} {C^k_n * (-1)^k} \)

7) \(m^n = (1+1+...+1)^n = \sum_{i1+...+im=n} {P^{i1,...,im}_{n}}\)

8) О производных

\((x+y)^n = \sum^{n}_{k=0} {C^k_n x^k*y^{n-k}}\)

Пусть у=1. Тогда \((x+1)^n = \sum^{n}_{k=0} {C^k_n x^k} = f(x) \frac {df(x)}{dx} = n(x+1)^{n-1} = \sum^{n}_{k=0} {k C^k_n x^{k-1}} \)