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

[dgwuqtj]

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

Это я зачем-то полез в доказательства,хотя она уже доказана де не один раз

Затем, что вам понадобилась другая формула, которой в учебниках нет. Хотя наверняка где-то она приводится, в упражнениях внутри учебников или даже в статьях...

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

Это сочетания без повторений?

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

[Elijah96]

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

Затем, что вам понадобилась другая формула, которой в учебниках нет.

Логично

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

Хотя наверняка где-то она приводится, в упражнениях внутри учебников или даже в статьях...

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

[Combat Zone]

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

[lel0lel]

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

И как в таком случае доказать для n множеств?

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

[Elijah96]

lel0lel в сообщении #1652144 писал(а):

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

И как в таком случае доказать для n множеств?

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

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

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

-- 28.08.2024, 17:38 --

Combat Zone в сообщении #1652142 писал(а):

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

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

[lel0lel]

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

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

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

[Elijah96]

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.

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

[lel0lel]

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.

[Elijah96]

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,Вы говорили что такие формулы можно получить руками?
Не подскажите как?
Или это очень сложно и нужно делать какие-то большие вычисления?

[dgwuqtj]

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

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

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

[lel0lel]

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

Понимаю, конечно, что это всё выглядит как злая шутка, но поверьте, что это не сложная вещь.

[Elijah96]

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$

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

[lel0lel]

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

[Elijah96]

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

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

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

-- 29.08.2024, 20:58 --

lel0lel в сообщении #1652304 писал(а):

Положите $a=1, b=-1$

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

[dgwuqtj]

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

Я "доказал" для трех множеств,но Вы сами говорили что доказать нужно для n-множеств,что я собственно не сделал

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

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

Но откуда они взялись?)

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