Формула включений/исключений

[Elijah96]

dgwuqtj в сообщении #1654015 писал(а):

Вы их будете считать?

Пытаюсь,только не могу прийти к логическому завершению,ведь угадать формулу непросто(для меня по крайней мере),а писать наугад коэффициенты не имеет смысла
Нужно же угадать коэффициент чтобы в конце расчетов получилось 1,и чтобы этот коэффициент был верен для формулы для n множеств

Я почему и спрашивал про количество всевозможных пересечений,потому что я пытался найти коэффициент исходя из них,но теперь оказывается что расчеты не верны

Потому что по формуле для 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| + 6 |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 3 |A_i \cap A_k \cap A_j \cap A_n| + \sum 6 |A_i \cap A_k \cap A_j \cap A_n \cap A_f| - 10 |A_i \cap A_k \cap A_j \cap A_n \cap A_f \cap A_s| $

Что так же не верно

И я опять пришел к неверному решению

[dgwuqtj]

Метод неопределённых коэффициентов: обозначьте эти коэффициентами буквами и делайте расчёты. Окажется, что коэффициенты должны удовлетворять неким линейным уравнениям, чтобы всё сошлось, и из этих уравнений они и находятся единственным образом. А почему вы думаете, что две последние формулы неверны?

[Elijah96]

А брать частный случай из формулы которая была раннее:

$|\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| + 4 |A_i \cap A_k \cap A_j \cap A_n \cap A_f|$

$|\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| + \sum 4 |A_i \cap A_k \cap A_j \cap A_n \cap A_f| - 5 |A_i \cap A_k \cap A_j \cap A_n \cap A_f \cap A_s| $

Так же не будет верным решением

-- 09.09.2024, 20:14 --

dgwuqtj в сообщении #1654028 писал(а):

обозначьте эти коэффициентами буквами и делайте расчёты.

То есть взять некие коэффициенты,составить из них линейное уравнение и решить его?
А как угадать какие коэффициенты нужно брать?

[dgwuqtj]

Elijah96 в сообщении #1654029 писал(а):

А как угадать какие коэффициенты нужно брать?

В смысле? Вы думаете, что от выбора букв что-то зависит? Ну возьмите $k_3, k_4, \ldots$, то есть $|\cup \cap A_i| = k_3 \sum |A_i A_j A_k| + k_4 \sum |A_i A_j A_k A_l| + \ldots$.

Elijah96 в сообщении #1654029 писал(а):

А брать частный случай из формулы которая была раннее:

$|\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| + 4 |A_i \cap A_k \cap A_j \cap A_n \cap A_f|$

$|\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| + \sum 4 |A_i \cap A_k \cap A_j \cap A_n \cap A_f| - 5 |A_i \cap A_k \cap A_j \cap A_n \cap A_f \cap A_s| $

Так же не будет верным решением

Конечно, потому что правильные коэффициенты вы в предыдущем сообщении всё-таки угадали.

[Elijah96]

dgwuqtj в сообщении #1654028 писал(а):

А почему вы думаете, что две последние формулы неверны?

Потому что расчеты производил я,а значит они не могут быть верными))))
А если без шуток то эти формулы не верны так как я провел не верные расчеты
А именно:
В формуле В\И каждый элемент должен быть посчитан по одному разу(это вроде я как усвоил)

Если $x$ $\in$$A_i$ то в сумме он даст 1(поскольку он входит в какое-либо множество $A_i$ )

Если $x$ $\notin$$A_i$ то в сумме он даст 0(поскольку он не входит ни в какое множество $A_i$ )

Возьму свой же пример для 5 множеств:

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

Пусть $x$ $\in$ $A1 , A2 , A3 , A4 , A5$

Если $x$ $\in$ $A1 , A2 , A3 , A4 , A5$ то в сумме он даст 1

Если $x$ $\notin$ $A1 , A2 , A3 , A4 , A5$ то в сумме он даст 0

Возьмем все тройные пересечения:

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

Как видно по таблице:
Количество тройных пересечений равно 10
Количество четверных пересечений,равно 5
Количество пятерных пересечений равно 1

Далее произведем расчеты:
Из тройных пересечений,нужно вычесть четверные и прибавить пятерное
Вычитаем:
10-5+1=6
Но четверных пересечений нужно вычесть утроенное количество,ведь если бы множеств было не 5 а 4,то перед четверным пересечением должен был бы стоять коэффициент 3,а значит он нужен и здесь(поскольку в 4 множествах,количество тройных пересечений равно 4,а значит из их количества нужно вычесть 3,чтобы получилось 1)
Получается:
10-15+1=-4
Получилось -4,а должно получиться 1
Значит перед пятерным пересечением нужно поставить некий коэффициент,чтобы в результате расчетов получилось 1
Этим коэффициентом является 6
Проверяем:
10-15+6=1
Совпало
P.S.(Для 6 и 7 множеств я пользовался той же логикой)

Формула для 7 множеств:

$|\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| + \sum 6 |A_i \cap A_k \cap A_j \cap A_n \cap A_f| - \sum 10 |A_i \cap A_k \cap A_j \cap A_n \cap A_f \cap A_x| + 15 |A_i \cap A_k \cap A_j \cap A_n \cap A_f \cap A_x \cap A_z|$

-- 09.09.2024, 20:42 --

dgwuqtj в сообщении #1654034 писал(а):

Вы думаете, что от выбора букв что-то зависит?

Я думаю что от выбора чисел что-то зависит,ведь в конечном итоге нужно же получить некое число,которое и будет коэффициентом?

[dgwuqtj]

Elijah96 в сообщении #1654041 писал(а):

Проверяем:
10-15+6=1
Совпало
P.S.(Для 6 и 7 множеств я пользовался той же логикой)

Ну да, всё в порядке. Это не доказательство, конечно, но всё-таки...

Elijah96 в сообщении #1654041 писал(а):

Я думаю что от выбора чисел что-то зависит

Тут нет выбора чисел. Вы просто обозначаете неизвестные числа буквами. Выбор будет в самом конце, при решении системы.

Скажем, пусть вы хотите получить некую формулу вида $|A \cup B \cup C| = x (|A| + |B| + |C|) + y (|AB| + |AC| + |BC|) + z |ABC|$. Числа $x, y, z$ неизвестны. Напишем все уравнения на $x, y, z$ так, чтобы выполнялось даже более сильное равенство

$$\chi_{A \cup B \cup C}(s) = x (\chi_A(s) + \chi_B(s) + \chi_C(s)) + y (\chi_{AB}(s) + \chi_{AB}(s) + \chi_{BC}(s)) + z \chi_{ABC}(s).$$

1. Если $s \notin A \cup B \cup C$, то с обеих сторон 0, никаких ограничений на коэффициенты.
2. Если $s$ принадлежит ровно одному из $A, B, C$, то получается $1 = x$.
3. Если $s$ принадлежит ровно двум из $A, B, C$, то получается $1 = 2 x + y$.
4. Если $s \in ABC$, то получается $1 = 3 x + 3 y + z$.
Решая систему, получаем $x = 1$, $y = -1$, $z = 1$.

[Elijah96]

Так же формулы для:

8 множеств:

$|\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| + \sum 6 |A_i \cap A_k \cap A_j \cap A_n \cap A_f| - \sum 10 |A_i \cap A_k \cap A_j \cap A_n \cap A_f \cap A_x| + \sum 15 |A_i \cap A_k \cap A_j \cap A_n \cap A_f \cap A_x \cap A_z| - 21 |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 3 |A_i \cap A_k \cap A_j \cap A_n| + \sum 6 |A_i \cap A_k \cap A_j \cap A_n \cap A_f| - \sum 10 |A_i \cap A_k \cap A_j \cap A_n \cap A_f \cap A_x| + \sum 15 |A_i \cap A_k \cap A_j \cap A_n \cap A_f \cap A_x \cap A_z| - \sum 21 |A_i \cap A_k \cap A_j \cap A_n \cap A_f \cap A_x \cap A_z \cap A_z| + 28 |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|$

[dgwuqtj]

Это я проверять не буду, но согласуется с моей гипотезой о том, что там за коэффициенты.

[Elijah96]

dgwuqtj в сообщении #1654048 писал(а):

Это я проверять не буду, но согласуется с моей гипотезой о том, что там за коэффициенты.

То есть я просто искал количество всех пересечений,начиная с тройных и заканчивая n
А потом просто складывал и вычитал их как по формуле В/И
А последний коэффициент остался таким чтобы в результате получилось 1

-- 09.09.2024, 21:01 --

Я пользовался просто частным случаем формулы знакопеременной суммы биноминальных коэффициентов
Там как раз поочередное сложение\вычитание
Но такое мне говорили не верно

-- 09.09.2024, 21:04 --

И раз уж мои расчеты совпали(хоть и без доказательно)
То как тогда эти расчеты распространить на n множеств,ведь искать каждый раз коэффициенты замучаешься
Есть ли более простой способ получить эти коэффициенты,кроме Вашех уравнений или моих длинных расчетов?

[dgwuqtj]

Elijah96 в сообщении #1654050 писал(а):

Есть ли более простой способ получить эти коэффициенты,кроме Вашех уравнений или моих длинных расчетов?

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

[Elijah96]

dgwuqtj в сообщении #1654057 писал(а):

Я бы просто угадал формулу в общем виде и доказал. Раз вам доказывать не надо, можно просто придумать какую-то формулу, вдруг это нужная.

Коэффициенты перед пересечениями равны:

$\binom{n-1}{k-1}$

Где:
$n$ - Количество множеств в пересечении
$k$ - Множества,с которых начинается формула(например одинарные множества,двойные пересечения,тройные пересечения и n-ные пересечения)

Например возьмем формулу В\И для 3 множеств,начинающуюся с одинарных множеств:

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

Так как формула начинается с одинарных множеств то $k$ будет равно 1
А $n$ будет равно количеству множеств в пересечении

Подставляем значения в $\binom{n-1}{k-1}$ и получаем:

Коэффициент перед одинарными множествами $\binom{1-1}{1-1}$

Коэффициент перед двойными двойными пересечениями $\binom{2-1}{1-1}$

Коэффициент перед тройным пересечением $\binom{3-1}{1-1}$

Как видно из расчетов,коэффициенты для формулы В\И которая начинается с одинарных множеств будут равен 1

Возьмем формулу В\И для 4 множеств,начинающуюся с двойных пересечений:

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

Так как формула начинается с двойных пересечений то $k$ будет равно 2
А $n$ будет равно количеству множеств в пересечении

Подставляем значения в $\binom{n-1}{k-1}$ и получаем:

Коэффициент перед двойными пересечениями $\binom{2-1}{2-1}$

Коэффициент перед тройными пересечениями $\binom{3-1}{2-1}$

Коэффициент перед четверным пересечением $\binom{4-1}{2-1}$

Как видно из расчетов,коэффициенты для формулы В\И которая начинается с двойных множеств будут равны 1(для двойных пересечений),2(для тройных пересечений),3(для четверного пересечения)

Возьмем формулу В\И для 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| + 6 |A_i \cap A_k \cap A_j \cap A_n \cap A_f|$

Так как формула начинается с тройных пересечений то $k$ будет равно 3
А $n$ будет равно количеству множеств в пересечении

Подставляем значения в $\binom{n-1}{k-1}$ и получаем:

Коэффициент перед тройными пересечениями $\binom{3-1}{3-1}$

Коэффициент перед четверными пересечениями $\binom{4-1}{3-1}$

Коэффициент перед пятерным пересечением $\binom{5-1}{3-1}$

Как видно из расчетов,коэффициенты для формулы В\И которая начинается с двойных множеств будут равны 1(для тройных пересечений),3(для четверных пересечений),6(для пятерного пересечения)

Верно ли это?

[dgwuqtj]

Ну да, в этих примерах подходит. Хотя вы не знаете наверняка, что эти формулы верны, раз доказательства нет. Только это абсолютное значение коэффициента, а знак там будет чередоваться, видимо. Верно ли это в общем случае — без понятия.

[Elijah96]

dgwuqtj в сообщении #1654164 писал(а):

Ну да, в этих примерах подходит. Хотя вы не знаете наверняка, что эти формулы верны, раз доказательства нет. Только это абсолютное значение коэффициента, а знак там будет чередоваться, видимо. Верно ли это в общем случае — без понятия

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