2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему На страницу Пред.  1 ... 16, 17, 18, 19, 20  След.
 
 Re: Формула включений/исключений
Сообщение05.09.2024, 18:57 


09/01/24
274
dgwuqtj в сообщении #1653388 писал(а):
Я не очень понял, что вы вообще хотите получить.


Вот Вы писали раннее формулу(я ее выше приводил)для мощности объединения пересечений 3 и 4 множеств
Из этой формулы можно вывести формулу для n множеств
Поскольку коэффициенты в этой формуле равны m-1 где m это количество множеств в пересечении(опять же,это без доказательств)
И в этой формуле учитываются все пересечения,начиная с попарных,далее идут тройные,затем четверные и так до n

Но что если нужно найти мощность объединения пересечений n множеств,при условии что будут учитываться минимум тройные или минимум четверные или минимум m-ные пересечения
Ведь в зависимости от количества множеств,будет зависеть и количество пересечений этих множеств,и следовательно коэффициенты перед пересечениями каждый раз будут разные
Вот и интересует вопрос есть ли для m-ных пересечений n множеств универсальная формула

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


07/08/23
1055
Elijah96 в сообщении #1653394 писал(а):
Из этой формулы можно вывести формулу для n множеств

Можно угадать, а не вывести.
Elijah96 в сообщении #1653394 писал(а):
Вот и интересует вопрос есть ли для m-ных пересечений n множеств универсальная формула

Есть, там коэффициенты просто будут зависеть от $m$ и от количества множеств в пересечении, перед которым коэффициент. Например,
$$|A B C \cup A B D \cup A C D \cup B C D| = |A B C| + |A B D| + |A C D| + |B C D| - 3 |A B C D|,$$
где через конкатенацию обозначено пересечение. Вот это $-3$ зависит как от того, что слева тройные пересечения, так и от того, что оно стоит при четверном пересечении.

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


09/01/24
274
Я попробовал найти коэффициенты,но так и не нашел систематику
Есть предположение что для нечетного количества множеств,коэффициент в предпоследним пересечением будет равен половине количества множеств в пересечении(например в примере для 7 множеств,коэффициент 3 перед шестерным пересечение,это половина от шести пересекающихся множеств)
А для четного количества множеств,коэффициенты в двух предпоследних пересечениях будут равны 2(например в примере для 8 множеств перед шестерным и семерным пересечением,коэффициент будет равен 2)
Верна ли мысль?
И верны ли вообще расчеты в целом?

Пример:

Для 5 множеств:

$|\cup \cap A_i| = \sum |A_i \cap A_k \cap A_j| - \sum 2 |A_i \cap A_k \cap A_j \cap A_n| + |A_i \cap A_k \cap A_j \cap A_n \cap A_f|$

Для 6 множеств:

$|\cup \cap A_i| = \sum |A_i \cap A_k \cap A_j| - \sum 2 |A_i \cap A_k \cap A_j \cap A_n| +  \sum 2 |A_i \cap A_k \cap A_j \cap A_n \cap A_f| - |A_i \cap A_k \cap A_j \cap A_n \cap A_f \cap A_x|$

Для 7 множеств:

$|\cup \cap A_i| = \sum |A_i \cap A_k \cap A_j| - \sum |A_i \cap A_k \cap A_j \cap A_n| +  \sum |A_i \cap A_k \cap A_j \cap A_n \cap A_f| - \sum 3 |A_i \cap A_k \cap A_j \cap A_n \cap A_f \cap A_x| + |A_i \cap A_k \cap A_j \cap A_n \cap A_f \cap A_x \cap A_z|$

Для 8 множеств:

$|\cup \cap A_i| = \sum |A_i \cap A_k \cap A_j| - \sum |A_i \cap A_k \cap A_j \cap A_n| +  \sum |A_i \cap A_k \cap A_j \cap A_n \cap A_f| - \sum 2 |A_i \cap A_k \cap A_j \cap A_n \cap A_f \cap A_x| + \sum 2 |A_i \cap A_k \cap A_j \cap A_n \cap A_f \cap A_x \cap A_z| - |A_i \cap A_k \cap A_j \cap A_n \cap A_f \cap A_x \cap A_z \cap A_z|$

Для 9 множеств:

$|\cup \cap A_i| = \sum |A_i \cap A_k \cap A_j| - \sum |A_i \cap A_k \cap A_j \cap A_n| +  \sum |A_i \cap A_k \cap A_j \cap A_n \cap A_f| - \sum |A_i \cap A_k \cap A_j \cap A_n \cap A_f \cap A_x| + \sum |A_i \cap A_k \cap A_j \cap A_n \cap A_f \cap A_x \cap A_z| - \sum 4 |A_i \cap A_k \cap A_j \cap A_n \cap A_f \cap A_x \cap A_z \cap A_z| + |A_i \cap A_k \cap A_j \cap A_n \cap A_f \cap A_x \cap A_z \cap A_z| \cap A_v|$

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


07/08/23
1055
Вот для 2, 3 и 4 множеств: 0, $|A_1 A_2 A_3|$ и $\sum_{i < j < k} |A_i A_j  A_k| - 3 |A_1 A_2 A_3 A_4|$. Ваши формулы все неправильные, вторым коэффициентом должно быть $-3$. Собственно, я умею доказывать, что коэффициенты не зависят от количества всех множеств, только от номера слагаемого.

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


09/01/24
274
dgwuqtj в сообщении #1653773 писал(а):
Вот для 2, 3 и 4 множеств: 0, $|A_1 A_2 A_3|$ и $\sum_{i < j < k} |A_i A_j  A_k| - 3 |A_1 A_2 A_3 A_4|$. Ваши формулы все неправильные, вторым коэффициентом должно быть $-3$. Собственно, я умею доказывать, что коэффициенты не зависят от количества всех множеств, только от номера слагаемого.


А от чего тогда должны зависеть коэффициенты?
От количества множеств в пересечении перед которым он стоит?
От номера слагаемого(как Вы сказли),то есть от того каким по счету стоит определенное пересечение?
На чем основываться?

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


07/08/23
1055
Elijah96 в сообщении #1653775 писал(а):
От количества множеств в пересечении перед которым он стоит?

Ну конечно. Вы сейчас хотите угадать общую формулу? Посчитайте её правильно хотя бы для 5 и 6 множеств.

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


09/01/24
274
dgwuqtj в сообщении #1653778 писал(а):
Вы сейчас хотите угадать общую формулу?

Да,я хочу угадать общую формулу,только пока не получается

-- 08.09.2024, 18:26 --

Я попробовал посчитать:

Для 5 множеств:

$|\cup \cap A_i| = \sum |A_i \cap A_k \cap A_j| - \sum 3 |A_i \cap A_k \cap A_j \cap A_n| + 7 |A_i \cap A_k \cap A_j \cap A_n \cap A_f|$

В чем ошибка?

Таблица для 5 множеств:

Пусть есть множества $A1,A2,A3,A4,A5$

Все тройные пересечения:

$\\
A1 \cap A2\cap A3\\
A1 \cap A2 \cap A4\\
A1 \cap A2 \cap A5\\
A1 \cap A3 \cap A4\\
A1 \cap A3 \cap A5\\
A1 \cap A4 \cap A5\\
A2 \cap A3 \cap A4\\
A2 \cap A3 \cap A5\\
A2 \cap A4 \cap A5\\
A3 \cap A4 \cap A5$

Все четверные пересечения:

$\\
A1 \cap A2 \cap A3 \cap A4\\
A1 \cap A2 \cap A3 \cap A5\\
A1 \cap A3 \cap A4 \cap A5\\
A1 \cap A2 \cap A4 \cap A5\\
A2 \cap A3 \cap A4 \cap A5$

Пятерное пересечение:

$A1 \cap A2 \cap A3 \cap A4 \cap A5 $

Как из этой таблицы получить нужные коэффициенты?
На что обращать внимание?

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


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

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


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


Если бы...
Я просто пытался посчитать таким способом:
Скажем $x$ $\in$ $A1$

Тогда в тройных пересечениях он учтен 6 раз
В четверных пересечениях $x$ учтен 4 раза,но так как надо вычесть утроенное количество четверных пересечений то 4 нужно умножить на 3 получается 12
Из тройных пересечений вычитаем четверные и получается 6-12=-6
А чтобы получить 1 нужно прибавить 7
Вот у меня и получилось 7

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


07/08/23
1055
Elijah96 в сообщении #1653815 писал(а):
Скажем $x$ $\in$ $A1$

Тогда в тройных пересечениях он учтен 6 раз

Хотя это не так, он там может быть не учтён ни разу вообще. Я про это уже подробно объяснял.

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


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$).


Вы про этот пример?

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


07/08/23
1055
Ага.

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


09/01/24
274
dgwuqtj в сообщении #1653830 писал(а):
Хотя это не так, он там может быть не учтён ни разу вообще. Я про это уже подробно объяснял.


Это те случаи когда $x$ $\notin$ $ A_i \cap A_j \cap A_k$ ?

-- 08.09.2024, 21:48 --

И все равно легче не стало(
А можно ли коэффициенты выразить через формулу сочетаний без повторений?

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


09/01/24
274
И зависят ли коэффициенты от количества всевозможных пересечений?
Например есть 5 множеств
Из них возможно составить некоторое количество всевозможных тройных и четверных пересечений,а так же одно пятерное пересечение
Так вот,влияет ли количество всех этих пересечений на коэффициенты?

-- 09.09.2024, 19:02 --

Я имел ввиду следующее:
Для 5 множеств есть:

10 тройных пересечений
5 четверных пересечений
1 пятерное
Влияет это количество на коэффициенты перед пересечениями?

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


07/08/23
1055
Elijah96 в сообщении #1654008 писал(а):
Влияет это количество на коэффициенты перед пересечениями?

Не влияет. Вы их будете считать?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 298 ]  На страницу Пред.  1 ... 16, 17, 18, 19, 20  След.

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



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

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


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

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