2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему На страницу Пред.  1 ... 10, 11, 12, 13, 14, 15, 16 ... 20  След.
 
 Re: Формула включений/исключений
Сообщение30.08.2024, 20:53 


09/01/24
274
dgwuqtj в сообщении #1652415 писал(а):
Elijah96 в сообщении #1652407 писал(а):
Если $x$ $\in$ $A_i$ то он будет учитываться $\binom n 1$

Нет, это же зависит от того, каким ещё множествам принадлежит $x$.


Тогда нужно сложить всевозможные варианты его учтений?

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


20/04/10
1867
Elijah96 в сообщении #1652407 писал(а):
Если $x$ $\in$ $A_i$ то он будет учитываться $\binom n 1$
Во - первых, мне кажется, вы хотели сказать, что принадлежит только некоторому $A_i$ и никому больше из исходных множеств. Если это хочется записать кванторами, то можно использовать симметрическуя разность исходных множеств. Во-вторых, не нужно пока биномиальных коэффициентов (чисел сочетаний) считайте честно, прямо руками, сколько раз он учитывается формулой. В-третьих, напишите чему равен $\binom{n}{1}$.

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


09/01/24
274
lel0lel в сообщении #1652418 писал(а):
В-третьих, напишите чему равен $\binom{n}{1}$.


Это число сочетаний из n по k

$$\binom {n}{1} = 1 $$

lel0lel в сообщении #1652418 писал(а):
считайте честно, прямо руками, сколько раз он учитывается формулой


$x$ $\notin$ $A_i$ $ \quad $ , $ \quad $ $x$ $\notin$ $A_i \cap A_j$ $ \quad $ , $ \quad $ $x$ $\notin$ $A_i \cap A_j \cap A_k$ $ \quad $ , $ \quad $ $ $ $x$ $\notin$ $A_i \cap A_j \cap A_k \cap ... \cap A_n$

$x$ $\in$ $A_i$ $ \quad $ , $ \quad $ $x$ $\notin$ $A_i \cap A_j$ $ \quad $ , $ \quad $ $x$ $\notin$ $A_i \cap A_j \cap A_k$ $ \quad $ , $ \quad $ $x$ $\notin$ $A_i \cap A_j \cap A_k \cap ... \cap A_n$

$x$ $\in$ $A_i$ $ \quad $ , $ \quad $ $x$ $\in$ $A_i \cap A_j$ $ \quad $ , $ \quad $ $x$ $\notin$ $A_i \cap A_j \cap A_k$ $ \quad $ , $ \quad $ $ $ $x$ $\notin$ $A_i \cap A_j \cap A_k \cap ... \cap A_n$

$x$ $\in$ $A_i$ $ \quad $ , $ \quad $ $x$ $\in$ $A_i \cap A_j$ $ \quad $ , $ \quad $ $x$ $\in$ $A_i \cap A_j \cap A_k$ $ \quad $ , $ \quad $ $x$ $\notin$ $A_i \cap A_j \cap A_k \cap ... \cap A_n$

$x$ $\in$ $A_i$ $ \quad $ , $ \quad $ $x$ $\in$ $A_i \cap A_j$ $ \quad $ , $ \quad $ $x$ $\in$ $A_i \cap A_j \cap A_k$ $ \quad $ , $ \quad $ $ $ $x$ $\in$ $A_i \cap A_j \cap A_k \cap ... \cap A_n$

Так?

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


20/04/10
1867
Elijah96 в сообщении #1652424 писал(а):
Это число сочетаний из n по k
$$\binom {n}{1} = 1 $$

Выбрать один объект из $n$ различных можно $n$ способами. Ищите ошибку в расчетах, если они вообще были.

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


09/01/24
274
lel0lel в сообщении #1652429 писал(а):
Выбрать один объект из $n$ различных можно $n$ способами. Ищите ошибку в расчетах, если они вообще были.


Да,точно,спасибо
Я опять ошибся

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


07/08/23
1055
Elijah96 в сообщении #1652424 писал(а):
Так?

У вас каждая строка — это какой-то вариант? Так не пойдёт. Эти строки не исчерпывают все возможности.

Почему бы просто не написать все $2^n$ случаев? Для них хотя бы легко доказать, что они всё покрывают. Вы бы с этого начали, что у вас именно полный перебор и ничего не пропущено.
$$
\begin{cases}
x \in A_1,\, \ldots,\, x \in A_{n - 1},\, x \in A_n; \\
x \in A_1,\, \ldots,\, x \in A_{n - 1},\, x \notin A_n; \\
x \in A_1,\, \ldots,\, x \notin A_{n - 1},\, x \in A_n; \\
x \in A_1,\, \ldots,\, x \notin A_{n - 1},\, x \notin A_n; \\
\ldots \\
x \notin A_1,\, \ldots,\, x \notin A_{n - 1},\, x \in A_n; \\
x \notin A_1,\, \ldots,\, x \notin A_{n - 1},\, x \notin A_n.
\end{cases}
$$

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


09/01/24
274
dgwuqtj в сообщении #1652436 писал(а):
Почему бы просто не написать все $2^n$ случаев?


А как написать весь перебор если множеств n?
Я имею ввиду их не конкретно "сколько-то"
Их n

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


07/08/23
1055
Elijah96 в сообщении #1652437 писал(а):
А как написать весь перебор если множеств n?

А раньше вы как это писали??? Мысленно пишите, а в реальности оставляйте многоточия. Видели доказательства чего-то в духе $(a_1 + \ldots + a_n)^2 = a_1^2 + \ldots + a_n^2 + 2 a_1 a_2 + \ldots + 2 a_{n - 1} a_n$?

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


09/01/24
274
dgwuqtj в сообщении #1652439 писал(а):
А раньше вы как это писали???


Раньше я писал для конкретного количества множеств
А для n множеств не писал

-- 30.08.2024, 23:09 --

dgwuqtj в сообщении #1652439 писал(а):
Видели доказательства чего-то в духе $(a_1 + \ldots + a_n)^2 = a_1^2 + \ldots + a_n^2 + 2 a_1 a_2 + \ldots + 2 a_{n - 1} a_n$?


Таких доказательств я не видел

-- 30.08.2024, 23:16 --

И что даст всевозможный перебор?

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


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

Ну... Если вы не поняли, как доказывать для трёх множеств, то ничего. Это же просто обобщение.

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


09/01/24
274
dgwuqtj в сообщении #1652107 писал(а):
Вообще, если уж доказывать перебором случаев, то удобнее такие варианты рассматривать:
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: Формула включений/исключений
Сообщение30.08.2024, 23:40 
Заслуженный участник


07/08/23
1055
Да, ровно такая же табличка при $n = 3$. С ней удобнее перебирать и доказывать, что перебор полный.

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


09/01/24
274
То есть если перебрать все возможные случаи то можно визуально увидеть а потом посчитать их
А мощность объединения это сумма всех возможных случаев за исключением случая когда $x$ никуда не будет включен(в Вашем примере это случай 8)
А в любом отдельно взятом случае, $x$ будет учтен ровно один раз

Или я опять не туда свернул?

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


07/08/23
1055
Elijah96 в сообщении #1652446 писал(а):
то можно визуально увидеть

В каком смысле? Формулы вы буквально напишете, их "видеть" не надо. Какую-нибудь диаграмму Венна вы и для 4 множеств не нарисуете, по крайней мере, вот так вот просто.

В остальном как-то так. Вы это понимаете или просто состыковываете слова, как нейросеть, чтобы было грамматически корректно?

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


09/01/24
274
Поправка

Elijah96 в сообщении #1652446 писал(а):
А в любом отдельно взятом случае, $x$ будет учтен ровно один раз


"Не учтен один раз"

А "сценарий",при котором $x$ будет "хоть куда-то включен" может реализоваться только один из 7(1-7 в таблице)
В 8 случае $x$ никуда не включен,значит и в объединении его быть не может

-- 30.08.2024, 23:52 --

dgwuqtj в сообщении #1652447 писал(а):
Вы это понимаете или просто состыковываете слова, как нейросеть, чтобы было грамматически корректно?


Пытаюсь понять

В левой части формулы В/И(то есть в объединении всех множеств),"сценарий" для $x$ только один,это собственно само объединение
А в правой части для $x$ ,"сценариев" может быть множество,но произойдет только один
Значит в левой и правой части для $x$ будет по одному "сценарию"

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

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



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

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


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

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