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

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску
 
(не показано 30 промежуточных версий этого же участника)
Строка 1: Строка 1:
==Пропущенная часть==
+
==Биекция и её полезные свойства==
 +
В предыдущей лекции мы условились, что для конечного множества его мощность - это количество элементов в данном множестве. Расширим это определение и для бесконечных множеств.
 +
 
 +
'''Мощность множества''' - это класс эквивалентности по отношению существования биективного отображения. Разберёмся в этом факте.
 +
 
 +
===Биекция и мощность множеств===
 +
'''Теорема.''' Если между множествами А и В можно построить биективное отображение, то их мощности равны и наоборот.
 +
 
 +
'''Доказательство'''
 +
 
 +
Доказательство проведём по индукции.
 +
 
 +
1) Рассмотрим случай пустого множества.
 +
 
 +
<math> \left | \varnothing \right | = 0</math>
 +
 
 +
Для пустого множества можно составить биекцию только с пустым множеством. Тогда <math>0=0</math>, теорема выполняется
 +
 
 +
2) Пусть <math>A=\left \{a \right \}</math>, <math>B=\left \{b \right \}</math> 
 +
 
 +
Между множествами А и В можно установить биекцию <math>\left \{a \right \} \longleftrightarrow \left \{b \right \}</math>
 +
 
 +
Из условия <math> \left |A \right | = \left |B \right | </math>, и мы смогли построить биекцию.
 +
 
 +
3) Предположение <math> \left |A \right | = \left |B \right | \Longleftrightarrow \exists f:A \longleftrightarrow B </math>
 +
 
 +
4) Пусть <math> \exists C, D:  \left | C \right | = n + 1; </math> <math>\exists f:C \longleftrightarrow D </math>
 +
 
 +
5) Из биекции следует, что <math> \forall c \in C</math>  <math>\exists f(c) = d; </math>
 +
 
 +
6) Тогда <math> f: C \backslash \left \{c \right \} \longleftrightarrow D \backslash \left \{d \right \}</math>
 +
 
 +
7) Так как мы исключили один элемент c, то <math>\left |C \backslash \left \{c \right \} \right | = n</math>. Из биекции следует, что для D <math>\left |D \backslash \left \{d \right \} \right | = n</math>
 +
 
 +
8) "Вернём" элемент d и по правилу сложения получим, что <math>\left |D \right | = n+1</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>
 +
 
 +
2) <math> A \sim B \Longrightarrow B \sim A \mbox{, так как раз это биекция, то существует обратное отображение } f^{-1} \mbox{, которое переводит B в A;} </math>
 +
 
 +
3) <math> A \sim B \mbox{ (отображение f), } B \sim C \mbox{ (отображение g), } \Longrightarrow A \sim C \mbox{ (отображение fg) } </math>
 +
 
 +
===Фактор-множество===
 +
Пусть <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>
 +
 
 +
'''Доказательство.'''
 +
 
 +
Доказательство проведём от противного
 +
[[Файл:R.jpg|мини|209x209пкс|рис.1. Разбиение множества А]]
 +
1) Пусть <math> \exists i \mbox{, } j: A_i \cap A_j = \left \{ b_1 , b_2 , ... , b_n \right \} </math>
 +
 
 +
2) Так как <math> b_1 \in A_i </math>, то <math> \forall a' \in A_i \mbox{ : } a' \rho \mbox{ } b_1 </math>
 +
 
 +
Так как <math> b_1 \in A_j </math>, то <math> \forall a'' \in A_j \mbox{ : } a'' \rho \mbox{ } b_1 </math>
 +
 
 +
Значит, так как <math>\rho </math> - отношение эквивалентности, <math> a' \rho \mbox{ } a'' </math>''
 +
 
 +
Следовательно, <math> A_i = A_j </math>
 +
 
 +
===Разбиение===
 +
Разбиение множества — это представление его в виде объединения произвольного количества попарно непересекающихся непустых подмножеств (см. рис.1) Мы доказали выше, что классы эквивалентности либо не пересекаются, либо совпадают. Значит, отношение эквивалентности задаёт разбиение множества, на котором мы задаём отношение эквивалентности.
  
 
==Бином Ньютона==
 
==Бином Ньютона==
Строка 8: Строка 77:
 
Формула для n элементов:  
 
Формула для n элементов:  
  
<math>(a_1+a_2+...+a_n)^n=\sum {P^{i_1,i_2,...,i_n}_n {a^{i_1}_1 a^{i_2}_2 ... a^{i_m}_m}  </math>
+
<nowiki><math> (a_{1} + a_{2} +...+ a_{n})^{n} = \sum {P^{i1,...,im}_{n}} {a^{i1}_1 a^{i2}_2 ... a^{im}_m}  </math></nowiki>
 +
 
 +
Как найти <math>P^{i1,...,im}_{n} </math> ?
 +
 
 +
<math>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!} </math>
 +
 
 +
Число <math>P^{i1,...,im}_{n} </math> называется '''числом перестановок с повторениями.'''
 +
 
 +
==Свойства комбинаторных величин==
 +
1) <math> C^k_n = C^{n-k}_n </math>
 +
 
 +
<math> C^k_n = \frac {n!}{k!*(n-k)!} </math>
 +
 
 +
<math> C^{n-k}_n = \frac {n!}{(n-k)!*k!} </math>
 +
[[Файл:Треугольник Паскаля.jpg|мини|рис. 2. Связь треугольника Паскаля и свойства 2]]
 +
Следовательно, они равны
 +
 
 +
2) <math> C^{k+1}_{n+1} = C^k_n +C^{k+1}_n </math>
 +
 
 +
Нужно выбрать k+1 элемент из множества n+1 элементов. Вариантов выбора два:
 +
 
 +
#Фиксируем <math>a_1</math>. В множестве "свободных" элементов остается <math>n</math> штук. Так как один элемент уже зафиксирован, то остаётся выбрать ещё <math>k</math> элементов. Вариантов выбора <math>C^k_n</math>
 +
#Рассмотрим выбор, когда нет <math>a_1</math>. Нужно выбрать <math>k+1</math> элементов из <math>n</math> штук. Вариантов выбора <math>C^{k+1}_n</math>
 +
 
 +
3) <math> 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 </math>
 +
 
 +
Мемоизация - запоминание промежуточных вычислений для предотвращения повторных вычислений. Выигрыш по времени, проигрыш по памяти. <syntaxhighlight lang="cpp">
 +
#include <map>
 +
 
 +
map <int, map<int, int>> s;
 +
 
 +
int B(int n, int k){
 +
 
 +
  if (k == 0 || k == n)
 +
      return 1;
 +
 
 +
  if (s[n][k])
 +
      return s[n][k];
 +
 
 +
  int res = B(n - 1, k - 1) + B(n - 1, k);
 +
 
 +
  s[n][k] = res;
 +
 
 +
  return res;
 +
 
 +
}
 +
</syntaxhighlight>
 +
 
 +
 
 +
4) <math>(1+1)^n = 2^n = \sum^{n}_{k=0} {C^k_n} </math>
 +
 
 +
<math>2^n</math> - это количество подмножеств данного множества 
 +
 
 +
5) <math>(2+1)^n = \sum^{n}_{k=0} {C^k_n * 2^k} </math>
 +
 
 +
<math>3^n</math> - это количество подмножеств произвольного подмножества данного множества
 +
 
 +
6) <math> (1-1)^n = 0 = \sum^{n}_{k=0} {C^k_n * (-1)^k} </math>
 +
 
 +
<nowiki>7) <math>m^n = (1+1+...+1)^n = \sum_{i1+...+im=n} {P^{i1,...,im}_{n}}</math>  </nowiki>
  
 +
8) О производных
  
 +
<nowiki><math>(x+y)^n = \sum^{n}_{k=0} {C^k_n x^k*y^{n-k}}</math></nowiki>
  
<br />
+
<nowiki>Пусть у=1. Тогда <math>(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}} </math></nowiki>

Текущая версия на 18:58, 28 декабря 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. Разбиение множества А

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 \)

Разбиение

Разбиение множества — это представление его в виде объединения произвольного количества попарно непересекающихся непустых подмножеств (см. рис.1) Мы доказали выше, что классы эквивалентности либо не пересекаются, либо совпадают. Значит, отношение эквивалентности задаёт разбиение множества, на котором мы задаём отношение эквивалентности.

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

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

\( (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

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

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 \)

Мемоизация - запоминание промежуточных вычислений для предотвращения повторных вычислений. Выигрыш по времени, проигрыш по памяти.

#include <map>

map <int, map<int, int>> s;

int B(int n, int k){

  if (k == 0 || k == n) 
      return 1;

  if (s[n][k])
      return s[n][k];

  int res = B(n - 1, k - 1) + B(n - 1, k);

  s[n][k] = res;

  return res;

}


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}} \)