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

[lel0lel]

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

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

Из поля $\mathbb{R}$. Мы ведь хотели ранее доказать некое тождество с знакопеременной суммой биномиальных коэффициентов. Вот такая удивительная догадка посетила голову -- раз в биноме тоже есть некие суммы с биномиальными коэффициентами, то надо этот бином покрутить.

[Elijah96]

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

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

Вот и я хотел получить формулу для n множеств,но чтобы ее получить нужно доказать формулу включений\исключений,а доказать я ее не могу
Замкнутый круг

[dgwuqtj]

Он не замкнутый. Во-первых, вы можете получить формулу для 3 множеств (она же так и не доказана?), и даже для 4. Во-вторых, можно разобраться в доказательстве формулы включений-исключений. Никто вас не просит с нуля придумывать это доказательство.

[Elijah96]

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

(она же так и не доказана?)

Естественно не доказана

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

Никто вас не просит с нуля придумывать это доказательство.

Тут даже дело не в придумывании,а в понимании уже существующих доказательств

-- 29.08.2024, 21:29 --

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

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

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

Из поля $\mathbb{R}$. Мы ведь хотели ранее доказать некое тождество с знакопеременной суммой биномиальных коэффициентов. Вот такая удивительная догадка посетила голову -- раз в биноме тоже есть некие суммы с биномиальными коэффициентами, то надо этот бином покрутить.

Но почему именно единицы?
И за что отвечает $a$ а за что отвечает $b$ ?

[lel0lel]

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

Но почему именно единицы?
И за что отвечает $a$ а за что отвечает $b$ ?

Иногда лучше отпустить ситуацию. Вот не понятно сейчас, ну и ладно, потом может быть поймёте. А если и нет, то тоже не так уж страшно. Начните с чего-то более простого: формулы сокращённого умножения, потом попробуйте их получить из бинома Ньютона, потом почитайте доказательство бинома.

[dgwuqtj]

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

И за что отвечает $a$ а за что отвечает $b$ ?

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

[Elijah96]

А можно ли,с учетом ошибок,для грубого доказательства формулы включений\исключений использовать следующее:

Дана формула включений\исключений:

$$|\cup A_i| = \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| -...+(-1)^{n-1} |A_1 \cap A_2 \cap A_3 \cap ... \cap A_n|$$

Введем комбинаторную интерпретацию:

Пусть есть n множеств

Тогда:

Выбрать одинарные множества из n множеств есть $C \binom{n}{1}$ способов

Выбрать двойные множества из n множеств есть $C \binom{n}{2}$ способов

Выбрать тройные множество из n множеств есть $C \binom{n}{3}$ способов

Выбрать n-ые множества из n множеств есть $C \binom{n}{n}$ способов

Тогда по формуле включений\иключений получается:

$$|\cup A_i| = C \binom{n}{1} -C \binom{n}{2} + C \binom{n}{3} \pm ... \pm C \binom{n}{n}$$

Далее нужно получить формулу

$$ C \binom{n}{1} - C \binom{n}{2} + C \binom{n}{3} \pm ... \pm C \binom{n}{n}$$

и доказать что

$$ C \binom{n}{1} - C \binom{n}{2} + C \binom{n}{3} \pm ... \pm C \binom{n}{n} = 1$$

Получить формулу

$$ C \binom{n}{1} - C \binom{n}{2} + C \binom{n}{3} \pm ... \pm C \binom{n}{n}$$

и доказать что

$$ C \binom{n}{1} - C \binom{n}{2} + C \binom{n}{3} \pm ... \pm C \binom{n}{n} = 1$$

можно из формулы знакопеременной разности биноминальных коэффициентов

Для этого возьмем саму формулу знакопеременной разности биноминальных коэффициентов:

$$C \binom {n}{0} - C \binom{n}{1} + C \binom{n}{2} - C \binom{n}{3} \pm ... \pm C \binom{n}{n} = 0$$

Обозначим

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

Тогда формула принимает вид:

$$1-C \binom{n}{1} + C \binom{n}{2} - C \binom{n}{3} \pm ... \pm C \binom{n}{n} = 0$$

Далее перенесем $ -C \binom{n}{1} + C \binom{n}{2} - C \binom{n}{3} \pm ... \pm C \binom{n}{n}$ в правую часть равенства и получим:

$$ 1=0+C \binom{n}{1} - C \binom{n}{2} + C \binom{n}{3} \pm ... \pm C \binom{n}{n}$$

или же

$$1=C \binom{n}{1} - C \binom{n}{2} + C \binom{n}{3} \pm ... \pm C \binom{n}{n} \Rightarrow C \binom{n}{1} - C \binom{n}{2} + C \binom{n}{3} \pm ... \pm C \binom{n}{n} = 1 $$

Как итог мы получили формулу

$$ C \binom{n}{1} - C \binom{n}{2} + C \binom{n}{3} \pm ... \pm C \binom{n}{n}$$

и доказали что

$$ C \binom{n}{1} - C \binom{n}{2} + C \binom{n}{3} \pm ... \pm C \binom{n}{n} = 1$$

Формула $ C \binom{n}{1} - C \binom{n}{2} + C \binom{n}{3} \pm ... \pm C \binom{n}{n}$ в точности равна правой части формулы включений\исключений

А как было доказано раннее $ C \binom{n}{1} - C \binom{n}{2} + C \binom{n}{3} \pm ... \pm C \binom{n}{n} = 1$

Значит в правой части формулы включений\исключений каждый элемент учитывается ровно 1 раз.

В левой части формулы включений\исключений каждый элемент так же учитывается ровно 1 раз(так как это объединение)

Следовательно левая и правая часть формулы включений\исключений равны.

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

[dgwuqtj]

Вы разве сами поняли, что написали? Что такое хотя бы "тройные множества"? И биномиальные коэффициенты не так обозначаются. Надо писать $\binom n k$ или $C_n^k$, на выбор. Первый способ из англоязычной традиции, второй из европейской, но вроде сейчас первый везде популярнее.

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

Обозначим

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

Тут не вводится обозначение, у вас обе части уже ранее введены. Левая в начале сообщения, правая в учебнике за 1 класс.

[lel0lel]

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

Выбрать одинарные множества из n множеств есть $C \binom{n}{1}$ способов

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

[Elijah96]

А если так:

Пусть есть мощность объединения $| A_i \cup A_j \cup A_k \cup ... \cup A_n|$

Выбираем произвольный элемент из объединения $|A_i \cup A_j \cup A_k \cup ... \cup A_n|$

Посчитаем сколько раз он будет учитываться в этом объединении $| A_i \cup A_j \cup A_k \cup ... \cup A_n|$

Во всех $|A_i|$ произвольный элемент будет учитываться

$$\binom n 1$$

Во всех $|A_i \cap A_j|$ произвольный элемент элемент будет учитываться

$$\binom n 2$$

Во всех $|A_i \cap A_j \cap A_k|$ произвольный элемент элемент будет учитываться

$$\binom n 3$$

Во всех $|A_i \cap A_j \cap A_k \cap ... \cap A_n|$ произвольный элемент элемент будет учитываться

$$\binom n n$$

[lel0lel]

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

из объединения $|A_i \cup A_j \cup A_k \cup ... \cup A_n|$

модуль нужно убрать, иначе, это не объединение а его мощность.

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

Во всех $|A_i|$ произвольный элемент будет учитываться

$$\binom n 1$$

Нет, произвольный элемент объединения "во всех $|A_i|$" может быть учтён от одного до $n$ раз. Нужен не совсем уж произвольный, а произвольный с указанием какому числу исходных множеств он принадлежит. Это он среди себе подобных будет произвольный.

[Elijah96]

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

модуль нужно убрать, иначе, это не объединение а его мощность.

Да,в мощности объединения,прошу прощения

[lel0lel]

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

Выбираем произвольный элемент из объединения $|A_i \cup A_j \cup A_k \cup ... \cup A_n|$

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

Да,в мощности объединения,прошу прощения

Но из мощности объединения нельзя ничего выбирать, иначе объединение рассердится, что его мощность начали уменьшать.

[Elijah96]

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

Нужен не совсем уж произвольный, а произвольный с указанием какому числу исходных множеств он принадлежит.

То есть нужно?:

Пусть есть объединение $ A_i \cup A_j \cup A_k \cup ... \cup A_n$

Выбираем произвольный элемент из объединения $A_i \cup A_j \cup A_k \cup ... \cup A_n$

Посчитаем сколько раз он будет учитываться в этом объединении $ A_i \cup A_j \cup A_k \cup ... \cup A_n$

Если $x$ $\in$ $A_i$ то он будет учитываться $\binom n 1$

Если $x$ $\in$ $A_i \cap A_j$ то он будет учитываться $\binom n 1$ - $\binom n 2$

Если $x$ $\in$ $A_i \cap A_j \cap A_k$ то он будет учитываться $\binom n 1$ - $\binom n 2$ + $\binom n 3$

Если $x$ $\in$ $A_i \cap A_j \cap A_k \cap ... \cap A_n$ то он будет учитываться $\binom n 1$ - $\binom n 2$ + $\binom n 3$ $ \pm ... \pm $ $\binom n n$

[dgwuqtj]

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

Если $x$ $\in$ $A_i$ то он будет учитываться $\binom n 1$

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