2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу Пред.  1 ... 7, 8, 9, 10, 11, 12, 13 ... 20  След.
 
 Re: Формула включений/исключений
Сообщение28.08.2024, 13:31 
Заслуженный участник


07/08/23
1055
Elijah96 в сообщении #1652095 писал(а):
Если $x$ $\in$ $A \cap B$ то он посчитан ровно $|A| + |B| - |A \cap B|$ раз ( в $|A|$ , в $|B|$ и в $|A \cap B|$ )

Ну нет же!

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение28.08.2024, 13:34 


09/01/24
274
dgwuqtj в сообщении #1652097 писал(а):
Ну нет же!


В чем опять ошибка?

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение28.08.2024, 13:36 
Заслуженный участник


07/08/23
1055
Вот с чего вы взяли, что он будет посчитан только в этих трёх слагаемых?

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение28.08.2024, 13:39 


09/01/24
274
dgwuqtj в сообщении #1652099 писал(а):
Вот с чего вы взяли, что он будет посчитан только в этих трёх слагаемых?


Потому что есть только A,B и AB

И если $x$ $\in$ $A \cap B$ то следовательно он есть в А и есть в В

Не так?

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение28.08.2024, 13:41 
Заслуженный участник


07/08/23
1055
Речь идёт про формулу для $|A \cup B \cup C|$. Есть ещё $C$, $A \cap C$, $B \cap C$ и $A \cap B \cap C$.

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение28.08.2024, 13:43 


09/01/24
274
dgwuqtj в сообщении #1652101 писал(а):
Речь идёт про формулу для $|A \cup B \cup C|$. Есть ещё $C$, $A \cap C$, $B \cap C$ и $A \cap B \cap C$.


А
Я думал про формулу $|A \cup B| = |A| + |B| - |A \cap B|$

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение28.08.2024, 13:44 
Заслуженный участник


07/08/23
1055
Elijah96 в сообщении #1652102 писал(а):
Я думал про формулу $|A \cup B| = |A| + |B| - |A \cap B|$

С ней вроде всё нормально.

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение28.08.2024, 13:45 


09/01/24
274
Если $x$ только $x$ $\in$ $A \cap B$ то в других слагаемых его быть не может

Если $x$ еще и $x$ $\in$ $C$ то тогда уже $x$ $\in$ $A \cap B \cap C$

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение28.08.2024, 13:49 
Заслуженный участник


07/08/23
1055
Elijah96 в сообщении #1652104 писал(а):
Если $x$ только $x$ $\in$ $A \cap B$

Что это должно значить? Элемент $x$ не может принадлежать только одному-единственному множеству $A \cap B$, он как минимум принадлежит $\{x\}$, $A$ и $B$...

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение28.08.2024, 13:54 


09/01/24
274
dgwuqtj в сообщении #1652105 писал(а):
Что это должно значить? Элемент $x$ не может принадлежать только одному-единственному множеству $A \cap B$, он как минимум принадлежит $\{x\}$, $A$ и $B$...


Ну если $x$ $\in$ $A \cap B$ то $x$ $\in$ $A$ и $B$

Тогда $x$ $\notin$ $C$

Ведь если $x$ $\in$ $A$ , $B$ и $C$

То $x$ $\in$ $A \cap B \cap C$

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение28.08.2024, 13:56 
Заслуженный участник


07/08/23
1055
Из истинного утверждения
Elijah96 в сообщении #1652106 писал(а):
если $x$ $\in$ $A$ , $B$ и $C$

То $x$ $\in$ $A \cap B \cap C$

не следует ложное утверждение
Elijah96 в сообщении #1652106 писал(а):
если $x$ $\in$ $A \cap B$ то $x$ $\in$ $A$ и $B$

Тогда $x$ $\notin$ $C$

. Ровно потому что $x \in A \cap B$ может всё-таки попасть в $C$.

Вообще, если уж доказывать перебором случаев, то удобнее такие варианты рассматривать:
1. $x \in A$, $x \in B$ и $x \in C$;
2. $x \in A$, $x \in B$ и $x \notin C$;
3. $x \in A$, $x \notin B$ и $x \in C$;
4. $x \in A$, $x \notin B$ и $x \notin C$;
5. $x \notin A$, $x \in B$ и $x \in C$;
6. $x \notin A$, $x \in B$ и $x \notin C$;
7. $x \notin A$, $x \notin B$ и $x \in C$;
8. $x \notin A$, $x \notin B$ и $x \notin C$.
Во-первых, сразу видно, что это все возможные случаи. То есть для любого элемента $x$ какой-то из этих случаев реализуется (на самом деле ровно один). А во-вторых, для каждого из этих случаев легко проверить, каким множествам, сконструированным из $A$, $B$, $C$, будет принадлежать $x$. Просто по определению, например, в третьем случае $x \notin A \cap B$ (потому что $x \notin B$) и $x \in A \cap C$ (потому что $x \in A$ и $x \in C$).

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение28.08.2024, 15:07 


09/01/24
274
dgwuqtj в сообщении #1652107 писал(а):
Из истинного утверждения
Elijah96 в сообщении #1652106 писал(а):
если $x$ $\in$ $A$ , $B$ и $C$

То $x$ $\in$ $A \cap B \cap C$

не следует ложное утверждение
Elijah96 в сообщении #1652106 писал(а):
если $x$ $\in$ $A \cap B$ то $x$ $\in$ $A$ и $B$

Тогда $x$ $\notin$ $C$

. Ровно потому что $x \in A \cap B$ может всё-таки попасть в $C$.

Вообще, если уж доказывать перебором случаев, то удобнее такие варианты рассматривать:
1. $x \in A$, $x \in B$ и $x \in C$;
2. $x \in A$, $x \in B$ и $x \notin C$;
3. $x \in A$, $x \notin B$ и $x \in C$;
4. $x \in A$, $x \notin B$ и $x \notin C$;
5. $x \notin A$, $x \in B$ и $x \in C$;
6. $x \notin A$, $x \in B$ и $x \notin C$;
7. $x \notin A$, $x \notin B$ и $x \in C$;
8. $x \notin A$, $x \notin B$ и $x \notin C$.
Во-первых, сразу видно, что это все возможные случаи. То есть для любого элемента $x$ какой-то из этих случаев реализуется (на самом деле ровно один). А во-вторых, для каждого из этих случаев легко проверить, каким множествам, сконструированным из $A$, $B$, $C$, будет принадлежать $x$. Просто по определению, например, в третьем случае $x \notin A \cap B$ (потому что $x \notin B$) и $x \in A \cap C$ (потому что $x \in A$ и $x \in C$).


Ваш вариант перебора оказался даже более легкий и быстрый

-- 28.08.2024, 15:09 --

Но к доказательству формулы вкл\искл я так и не приблизился
Но и ладно
Все равно спасибо всем что попытались помочь с этой формулой

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение28.08.2024, 16:28 
Заслуженный участник


07/08/23
1055
Elijah96 в сообщении #1652115 писал(а):
Но к доказательству формулы вкл\искл я так и не приблизился

Там, если делать в лоб, надо для каждого $n$ написать перебор $2^n$ вариантов. Чтобы не писать бесконечно много текста, используют какие-то общие рассуждения. Можете прочитать доказательство в какой-нибудь книжке, типа Дж. Андерсон, Дискретная математика и комбинаторика, теорема 12.7. Разумеется, там возникают какие-то суммы с биномиальными коэффициентами, их надо уметь считать. Вам вообще стоило бы прочитать побольше всяких теорем с доказательствами из дискретной математики (и порешать задач!), опыта набраться.

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение28.08.2024, 16:59 
Заслуженный участник


20/04/10
1867
Elijah96 в сообщении #1652115 писал(а):
Но к доказательству формулы вкл\искл я так и не приблизился
Но и ладно

Может так: посчитав сумму мощностей объединяемых множеств, все области с чисто двойным пересечением учли дважды. Поэтому, вычитаем мощности всевозможных двойных пересечений, но вместе с этим выкинули мощности чисто тройных пересечений, так как $3-\binom{3}{2}=3-3=0$, поэтому добавляем мощности всевозможных тройных пересечений. Теперь у нас чисто единичные :-), чисто двойные и чисто тройные учтены правильно. А что с чисто четвертыми? Так как $4-\binom{4}{2}+\binom{4}{3}=4-6+4=2$, оказывается, они учтены дважды. Чтобы справедливость восторжествовала, выкидываем всевозможные четверные, теперь с чисто четверными полный порядок! Но не накосячили ли мы с чисто пятерными (это хорошо если их нет, а вдруг есть). Проверяем $5-\binom{5}{2}+\binom{5}{3}-\binom{5}{4}=5-30+30-5=0$, накосячили, они не учтены в мощности объединения! Ворочаем их назад добавлением мощностей всевозможных пятерых пересечений. И т.д.

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение28.08.2024, 17:11 


09/01/24
274
dgwuqtj в сообщении #1652127 писал(а):
Elijah96 в сообщении #1652115 писал(а):
Но к доказательству формулы вкл\искл я так и не приблизился

Там, если делать в лоб, надо для каждого $n$ написать перебор $2^n$ вариантов. Чтобы не писать бесконечно много текста, используют какие-то общие рассуждения. Можете прочитать доказательство в какой-нибудь книжке, типа Дж. Андерсон, Дискретная математика и комбинаторика, теорема 12.7. Разумеется, там возникают какие-то суммы с биномиальными коэффициентами, их надо уметь считать. Вам вообще стоило бы прочитать побольше всяких теорем с доказательствами из дискретной математики (и порешать задач!), опыта набраться.


А вообще,можно было принять на веру эту формулу,ведь ее кто-то открыл и доказал
А потом ее доказывали еще очень много-много раз
Это я зачем-то полез в доказательства,хотя она уже доказана да и не один раз

-- 28.08.2024, 17:16 --

lel0lel в сообщении #1652131 писал(а):
Elijah96 в сообщении #1652115 писал(а):
Но к доказательству формулы вкл\искл я так и не приблизился
Но и ладно

Может так: посчитав сумму мощностей объединяемых множеств, все области с чисто двойным пересечением учли дважды. Поэтому, вычитаем мощности всевозможных двойных пересечений, но вместе с этим выкинули мощности чисто тройных пересечений, так как $3-\binom{3}{2}=3-3=0$, поэтому добавляем мощности всевозможных тройных пересечений. Теперь у нас чисто единичные :-), чисто двойные и чисто тройные учтены правильно. А что с чисто четвертыми? Так как $4-\binom{4}{2}+\binom{4}{3}=4-6+4=2$, оказывается, они учтены дважды. Чтобы справедливость восторжествовала, выкидываем всевозможные четверные, теперь с чисто четверными полный порядок! Но не накосячили ли мы с чисто пятерными (это хорошо если их нет, а вдруг есть). Проверяем $5-\binom{5}{2}+\binom{5}{3}-\binom{5}{4}=5-30+30-5=0$, накосячили, они не учтены в мощности объединения! Ворочаем их назад добавлением мощностей всевозможных пятерых пересечений. И т.д.


Это сочетания без повторений?

И как в таком случае доказать для n множеств?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 298 ]  На страницу Пред.  1 ... 7, 8, 9, 10, 11, 12, 13 ... 20  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group