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
1099
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
621
Elijah96
Есть формула включений-исключений. Основная. Подставляете в нее нужное - в данном случае пересечения, упрощаете, получаете нечто. На все случаи формул не напасешься.

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


20/04/10
1878
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
1878
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
1878
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
1099
Elijah96 в сообщении #1652269 писал(а):
dgwuqtj,Вы говорили что такие формулы можно получить руками?
Не подскажите как?

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

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


20/04/10
1878
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
1878
Положите $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
1099
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  След.

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



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

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


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

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