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  След.

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



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

Сейчас этот форум просматривают: Padawan


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

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