2014 dxdy logo

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

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


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


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



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


07/08/23
1203
Elijah96 в сообщении #1652135 писал(а):
Это я зачем-то полез в доказательства,хотя она уже доказана де не один раз

Затем, что вам понадобилась другая формула, которой в учебниках нет. Хотя наверняка где-то она приводится, в упражнениях внутри учебников или даже в статьях...
Elijah96 в сообщении #1652135 писал(а):
Это сочетания без повторений?

Да, $\binom n k = \mathrm C_n^k = \frac{n!}{k! (n - k)!}$ — количества сочетаний из $n$ по $k$.

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


09/01/24
274
dgwuqtj в сообщении #1652138 писал(а):
Затем, что вам понадобилась другая формула, которой в учебниках нет.


Логично

dgwuqtj в сообщении #1652138 писал(а):
Хотя наверняка где-то она приводится, в упражнениях внутри учебников или даже в статьях...


В интернете такой формулы нет,возмножно,как Вы сказали в каких-то статьях или учебниках есть
Но перебрать их все нереально
Так что считай что этой формулы "нет"

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


22/11/22
676
Elijah96
Есть формула включений-исключений. Основная. Подставляете в нее нужное - в данном случае пересечения, упрощаете, получаете нечто. На все случаи формул не напасешься.

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


20/04/10
1889
Elijah96 в сообщении #1652135 писал(а):
И как в таком случае доказать для n множеств?

Для $n$ множеств самое "массовое" возможное пересечение это пересечение $n$ множеств. Вот когда чисто $n$-арные (их может быть и несколько) будут учтены правильно, следует поставить точку. А тождество с биномиальными коэффициентами можете проверить для произвольного значения $k$, чтобы стало понятно, что включения и исключения всё время чередуются с единичным коэффициентом.

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


09/01/24
274
lel0lel в сообщении #1652144 писал(а):
Elijah96 в сообщении #1652135 писал(а):
И как в таком случае доказать для n множеств?

Для $n$ множеств самое "массовое" возможное пересечение это пересечение $n$ множеств. Вот когда чисто $n$-арные (их может быть и несколько) будут учтены правильно, следует поставить точку.


Но для этого как раз таки и нужно доказать,что формула вкл\искл и верна для n множеств

То есть не перебирать все варианты а доказать что раз верно для n то верно для n+1
В этом и есть у меня сложность

-- 28.08.2024, 17:38 --

Combat Zone в сообщении #1652142 писал(а):
Есть формула включений-исключений. Основная. Подставляете в нее нужное - в данном случае пересечения, упрощаете, получаете нечто. На все случаи формул не напасешься.


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

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


20/04/10
1889
Elijah96 в сообщении #1652146 писал(а):
То есть не перебирать все варианты а доказать что раз верно для n то верно для n+1
В этом и есть у меня сложность

Это вы сейчас об одном возможном способе доказательства -- по индукции. Я выше привёл рассуждения для произвольного натурального $n$, которые можно оформить в строгое доказательство. Потребуется только доказать тождество с числами сочетаний, но оно почти бесплатно получается из бинома Ньютона. Догадаетесь о каком тождестве речь?

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


09/01/24
274
lel0lel в сообщении #1652149 писал(а):
Догадаетесь о каком тождестве речь?


Понятия не имею

-- 28.08.2024, 18:18 --

Вообще формула включений\исключений это ничто иное как знакопеременная сумма сочетаний без повторений
А сочетания без повторений есть биноминальный коэффициент
А знакопеременная сумма биноминальных коэффициентов равна 0
Но только потому что первым слагаемым идет $\mathrm C_n^0$
А $\mathrm C_n^0$ = 1
А так как в формуле вкл\искл нельзя выбрать нуль множеств(минимум должно быть одно множество(то есть на первые слагаемые в формуле вкл\искл выбираются $\mathrm C_n^1$ множеств),то первым слагаемым в знакопеременной сумме биноминальных коэффициентов и будет $\mathrm C_n^1$ а не $\mathrm C_n^0$
А теперь когда первым слагаемым идет $\mathrm C_n^1$ а не $\mathrm C_n^0$ то знакопеременная сумма биноминальных коэффициентов будет равна 1.

З.Ы.(Вопросы не ко мне,все взято из тырнета)

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


20/04/10
1889
Elijah96 в сообщении #1652153 писал(а):
З.Ы.(Вопросы не ко мне,все взято из тырнета)

Лучше ссылаться на то, что вы поняли или кажется, что поняли.

Пусть произвольный элемент $x$ объединения исходных множеств принадлежит только $k$ из них, $1\leq k\leq n$. В формуле включений-исключений, очевидно, он может учитываться только в мощностях пересечения не более чем $k$ множеств. В первых $n$ слагаемых формулы его посчитали $k$ раз. Затем, если $k>1$, в двойных пересечениях посчитали $\binom{k}{2}$ раз и вычли из предыдущего количества. В итоге, в формуле он всего учитывается $\sum\limits_{i=1}^{k}(-1)^{i-1}\binom{k}{i}$=-((1-1)^k-1)=1.

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


09/01/24
274
lel0lel в сообщении #1652205 писал(а):
Лучше ссылаться на то, что вы поняли или кажется, что поняли.


Эх если бы я что-то понял(

lel0lel в сообщении #1652205 писал(а):
сть произвольный элемент $x$ объединения исходных множеств принадлежит только $k$ из них, $1\leq k\leq n$. В формуле включений-исключений, очевидно, он может учитываться только в мощностях пересечения не более чем $k$ множеств. В первых $n$ слагаемых формулы его посчитали $k$ раз. Затем, если $k>1$, в двойных пересечениях посчитали $\binom{k}{2}$ раз и вычли из предыдущего количества. В итоге, в формуле он всего учитывается $\sum\limits_{i=1}^{k}(-1)^{i-1}\binom{k}{i}$=-((1-1)^k-1)=1.


Это Вы доказали формулу вкл\искл?

lel0lel в сообщении #1652205 писал(а):
$\sum\limits_{i=1}^{k}(-1)^{i-1}\binom{k}{i}$=-((1-1)^k-1)=1.


А как Вы получили эту формулу?
Это уже готовая формула или ее нужно специально выводить?

dgwuqtj в сообщении #1651371 писал(а):
Вообще давайте введём обозначение $\cup_{\geq 2}(A_1, \ldots, A_n) = \bigcup_{1 \leq i < j \leq n} (A_i \cap A_j)$, то есть множество тех элементов, которые входят в хотя бы два множества из $A_1, \ldots, A_n$ (вам вроде именно это надо). Можно руками получить такие формулы: $|\cup_{\geq 2}(A)| = 0$, $|\cup_{\geq 2}(A, B)| = |A \cap B|$, $|\cup_{\geq 2}(A, B, C)| = |A \cap B| + |A \cap C| + |B \cap C| - 2 |A \cap B \cap C|$,
$$\substack{|\cup_{\geq 2}(A, B, C, D)| = |A \cap B| + |A \cap C| + |A \cap D| + |B \cap C| + |B \cap D| + |C \cap D|\\ - 2 |A \cap B \cap C| - 2 |A \cap B \cap D| - 2 |A \cap C \cap D| - 2 |B \cap C \cap D| + 3 |A \cap B \cap C \cap D|}.$$


dgwuqtj,Вы говорили что такие формулы можно получить руками?
Не подскажите как?
Или это очень сложно и нужно делать какие-то большие вычисления?

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


07/08/23
1203
Elijah96 в сообщении #1652269 писал(а):
dgwuqtj,Вы говорили что такие формулы можно получить руками?
Не подскажите как?

Вот вы же доказали что-то руками, для $|A \cup B \cup C|$. Так же можно и эти формулы доказать, даже в уме при некотором опыте. А коэффициенты подобрать так, чтобы доказательство работало.

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


20/04/10
1889
Elijah96 в сообщении #1652269 писал(а):
Это Вы доказали формулу вкл\искл?
Да, ведь показано же, что каждый элемент из объединения учитывается формулой ровно один раз в мощности объединения.
Elijah96 в сообщении #1652269 писал(а):
А как Вы получили эту формулу?
Это уже готовая формула или ее нужно специально выводить?
Есть бином Ньютона $$0=(1-1)^k=\sum\limits_{i=0}^{k}\binom{k}{i}1^{k-i}(-1)^i=\sum\limits_{i=0}^{k}\binom{k}{i}(-1)^{i}=1+\sum\limits_{i=1}^{k}\binom{k}{i}(-1)^i=1-\sum\limits_{i=1}^{k}\binom{k}{i}(-1)^{i-1}$$
Понимаю, конечно, что это всё выглядит как злая шутка, но поверьте, что это не сложная вещь.

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


09/01/24
274
lel0lel в сообщении #1652296 писал(а):
Есть бином Ньютона $$0=(1-1)^k=\sum\limits_{i=0}^{k}\binom{k}{i}1^{k-i}(-1)^i=\sum\limits_{i=0}^{k}\binom{k}{i}(-1)^{i}=1+\sum\limits_{i=1}^{k}\binom{k}{i}(-1)^i=1-\sum\limits_{i=1}^{k}\binom{k}{i}(-1)^{i-1}$$
Понимаю, конечно, что это всё выглядит как злая шутка, но поверьте, что это не сложная вещь.



А почему у Вас $(1-1)^k$?
Я почему спрашиваю
Я нашел формулу бинома Ньютона в википедии,и она выглядит чуть по другому

$$(a+b)^n=\sum\limits_{k=0}^{n}\binom{n}{k}a^{n-k}b^k$$

То есть тут $(a+b)^n$ а у Вас $(1-1)^k$

Не подскажите почему так?

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


20/04/10
1889
Положите $a=1, b=-1$. Этот частный случай как раз и доказывает тождество с биномиальными коэффициентами.

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


09/01/24
274
dgwuqtj в сообщении #1652286 писал(а):
вы же доказали что-то руками, для $|A \cup B \cup C|$. Так же можно и эти формулы доказать, даже в уме при некотором опыте. А коэффициенты подобрать так, чтобы доказательство работало.


Я "доказал" для трех множеств,но Вы сами говорили что доказать нужно для n-множеств,что я собственно не сделал
Я понимаю что формула верна(которую Вы написали для трех и четырех множеств),но вот доказать ее не доказал
Я так понял что нужно найти просто ситуацию когда расчеты по одной и той же формуле будут верны для разного количества множеств?

-- 29.08.2024, 20:58 --

lel0lel в сообщении #1652304 писал(а):
Положите $a=1, b=-1$


Это первое пришло в голову
Но откуда они взялись?)

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


07/08/23
1203
Elijah96 в сообщении #1652305 писал(а):
Я "доказал" для трех множеств,но Вы сами говорили что доказать нужно для n-множеств,что я собственно не сделал

Для того, чтобы доказывать всякие формулы для 3, 4, да хоть 10 множеств, общая формула включений-исключений не нужна. Её надо уметь доказывать, если вы хотите иметь сразу общую формулу для $n$ множеств, $|\bigcup_{i < j} (A_i \cap A_j)| = \ldots$.
Elijah96 в сообщении #1652305 писал(а):
Но откуда они взялись?)

Просто придумались так, чтобы можно было это использовать в доказательстве. Сначала надо научиться читать доказательства и отличать правильные доказательства от ошибочных. Потом уже пробовать придумывать доказательства самостоятельно (для конкретной области математики, а вообще же доказывать что-то учат аж с 7 класса). Придумывание — это творческий процесс, он не алгоритмизуется.

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

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



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

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


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

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