2014 dxdy logo

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

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


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


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



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


20/04/10
1867
Elijah96 в сообщении #1652305 писал(а):
Но откуда они взялись?)
Из поля $\mathbb{R}$. Мы ведь хотели ранее доказать некое тождество с знакопеременной суммой биномиальных коэффициентов. Вот такая удивительная догадка посетила голову -- раз в биноме тоже есть некие суммы с биномиальными коэффициентами, то надо этот бином покрутить.

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


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


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

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


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

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


09/01/24
274
dgwuqtj в сообщении #1652317 писал(а):
(она же так и не доказана?)


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

dgwuqtj в сообщении #1652317 писал(а):
Никто вас не просит с нуля придумывать это доказательство.


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

-- 29.08.2024, 21:29 --

lel0lel в сообщении #1652310 писал(а):
Elijah96 в сообщении #1652305 писал(а):
Но откуда они взялись?)
Из поля $\mathbb{R}$. Мы ведь хотели ранее доказать некое тождество с знакопеременной суммой биномиальных коэффициентов. Вот такая удивительная догадка посетила голову -- раз в биноме тоже есть некие суммы с биномиальными коэффициентами, то надо этот бином покрутить.


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

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


20/04/10
1867
Elijah96 в сообщении #1652319 писал(а):
Но почему именно единицы?
И за что отвечает $a$ а за что отвечает $b$ ?
Иногда лучше отпустить ситуацию. Вот не понятно сейчас, ну и ладно, потом может быть поймёте. А если и нет, то тоже не так уж страшно. Начните с чего-то более простого: формулы сокращённого умножения, потом попробуйте их получить из бинома Ньютона, потом почитайте доказательство бинома.

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


07/08/23
1055
Elijah96 в сообщении #1652319 писал(а):
И за что отвечает $a$ а за что отвечает $b$ ?

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

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


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

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

$$|\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 раз(так как это объединение)

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

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

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


07/08/23
1055
Вы разве сами поняли, что написали? Что такое хотя бы "тройные множества"? И биномиальные коэффициенты не так обозначаются. Надо писать $\binom n k$ или $C_n^k$, на выбор. Первый способ из англоязычной традиции, второй из европейской, но вроде сейчас первый везде популярнее.
Elijah96 в сообщении #1652398 писал(а):
Обозначим $$C \binom {n}{0} = 1 $$

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

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


20/04/10
1867
Elijah96 в сообщении #1652398 писал(а):
Выбрать одинарные множества из n множеств есть $C \binom{n}{1}$ способов

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

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


09/01/24
274
А если так:

Пусть есть мощность объединения $| 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$$

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


20/04/10
1867
Elijah96 в сообщении #1652402 писал(а):
из объединения $|A_i \cup A_j \cup A_k \cup ... \cup A_n|$
модуль нужно убрать, иначе, это не объединение а его мощность.
Elijah96 в сообщении #1652402 писал(а):
Во всех $|A_i|$ произвольный элемент будет учитываться $$\binom n 1$$
Нет, произвольный элемент объединения "во всех $|A_i|$" может быть учтён от одного до $n$ раз. Нужен не совсем уж произвольный, а произвольный с указанием какому числу исходных множеств он принадлежит. Это он среди себе подобных будет произвольный.

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


09/01/24
274
lel0lel в сообщении #1652404 писал(а):
модуль нужно убрать, иначе, это не объединение а его мощность.


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

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


20/04/10
1867
Elijah96 в сообщении #1652402 писал(а):
Выбираем произвольный элемент из объединения $|A_i \cup A_j \cup A_k \cup ... \cup A_n|$

Elijah96 в сообщении #1652405 писал(а):
Да,в мощности объединения,прошу прощения

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

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


09/01/24
274
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$

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


07/08/23
1055
Elijah96 в сообщении #1652407 писал(а):
Если $x$ $\in$ $A_i$ то он будет учитываться $\binom n 1$

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

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

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



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

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


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

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