2014 dxdy logo

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

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


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


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Выбираем m подмножеств из n элементов
Сообщение02.05.2007, 11:28 
Аватара пользователя


02/05/07
144
Граждане помогите разобраться с решением задачи, что то не соображу с какой стороны к ней подойти:
Имеется конечное множество, состоящее из V элементов. В нем произвольным образом выбирается m подмножеств, каждое из которых состоит из n элементов. Найти вероятность того, что в попарном пересечении каждого из этих подмножеств содержится не более чем k элементов.
Заранее благодарен.

 Профиль  
                  
 
 
Сообщение02.05.2007, 14:03 
Заслуженный участник
Аватара пользователя


09/10/05
1142
Аналогичная задачка приводилась уже здесь

Отличие в том, что у Вас известно, что все подмножества имеют равное количество элементов, но сдаётся мне, что это не сильно облегчает дело... Насчёт знаменателя легко: он делается по примеру: сколькими способами выбрать 5 пловцов из 10 для команды.
Насчёт числителя труднее. Дело в том, что как уже заметил RIP пересечение могут быть разными. Возможно такой подход: снова выбрать все подмножества $k$-элементов из первоначального (аналогично знаменателю, только теперь уже для $k$) и рассмотреть их как подмножества подмножеств из $n$ элементов. Понятно, что те, которые не имеют в себе этих подмножеств являются не счастливыми случаями.

Добавлено спустя 3 минуты 27 секунд:

К тому-же у Вас оговаривается важное условие: не более, чем $k$ элементов.

 Профиль  
                  
 
 
Сообщение02.05.2007, 15:33 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
По-моему, эта задача в общем виде замкнутой формулой не решается.

 Профиль  
                  
 
 
Сообщение03.05.2007, 03:06 


04/02/07
164
Можно попробовать следующие рассуждения (я в этом не спец так что проверяйте):
Вероятность что в пересечении первой области со второй i элементов:
\[
\frac{{C_N^i  \cdot C_{V - N}^{N - i} }}
{{C_V^N }}
\]
Вероятность что в пересечении первой области со второй не больше чем k элементов:
\[
P_1  = \sum\limits_{i = 0}^k {\frac{{C_N^i  \cdot C_{V - N}^{N - i} }}
{{C_V^N }}} 
\]
Вероятность что в попарном пересечении первой области со всеми последующими не больше чем k элементов:

\[
{\text{P}}_{\text{2}}  = P_1 ^m 
\]

Вероятность что в попарном пересечении второго со всеми последующими подмножествами элементов не более чем k:
\[
{\text{P'}}_{\text{2}}  = P_1 ^{m - 1} 
\]
Учитывая что события являются не зависимыми то можно перемножить:
\[
{\text{P}}_{\text{3}}  = P_1 ^m  \cdot P_1 ^{m - 1}  \cdot ...P_1 ^1 
\]
Проверяй - я в этом не очень уверен.

 Профиль  
                  
 
 
Сообщение03.05.2007, 03:54 
Экс-модератор


12/06/05
1595
MSU
Bod
Гм, как вы ее!

Я бы сказал, что это очень похоже на правду. По крайней мере, я вот так навскидку не вижу в этом рассуждении ошибку.

 Профиль  
                  
 
 
Сообщение03.05.2007, 11:53 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Bod писал(а):
Учитывая что события являются не зависимыми то можно перемножить:
\[
{\text{P}}_{\text{3}}  = P_1 ^m  \cdot P_1 ^{m - 1}  \cdot ...P_1 ^1 
\]


А почему события независимы?

Добавлено спустя 56 секунд:

Вообще говоря, это неверно.

 Профиль  
                  
 
 
Сообщение03.05.2007, 14:04 


04/02/07
164
Цитата:
А почему события независимы?

А в чем вы видите зависимость данных событий?

 Профиль  
                  
 
 
Сообщение03.05.2007, 14:40 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Простой гипотетический пример: если первый со вторым пересекается более чем по половине и первый с третьим пересекается более чем по половине, то второй с третьим достоверно пересекаются друг с другом.

 Профиль  
                  
 
 
Сообщение03.05.2007, 14:44 


04/02/07
164
Цитата:
Простой гипотетический пример: если первый со вторым пересекается более чем по половине и первый с третьим пересекается более чем по половине, то второй с третьим достоверно пересекаются друг с другом.


Согласен, согласен - я проверил лишь попарную независимость а про независимость в целом забыл :oops:

Ну тогда в голову приходит только такое:
\[
P = \sum\limits_{i_1  \leqslant k...i_m  \leqslant k} {\frac{{\left( {C_N^{i_1 }  \cdot C_{V - N}^{N - i_1 } } \right) \cdot \left( {C_N^{i_2 }  \cdot C_{V - N}^{N - i_2 } } \right) \cdot ... \cdot \left( {C_N^{i_m }  \cdot C_{V - N}^{N - i_m } } \right)}}
{{\left( {C_V^N } \right)^m }}} 
\]

 Профиль  
                  
 
 
Сообщение03.05.2007, 15:14 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Не понимаю. В чем смысл чисел $i$?

 Профиль  
                  
 
 
Сообщение03.05.2007, 16:37 


04/02/07
164
Это я очередной раз не подумав написал, извините.

 Профиль  
                  
 
 
Сообщение03.05.2007, 19:08 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Я точно могу сказать, что простой формулой это не описать. Это вообще часть большой науки, ключевые слова extremal sets, superimposed codes (дизъюнктные коды), планы поиска и т.д.

 Профиль  
                  
 
 
Сообщение04.05.2007, 06:52 


12/10/06
56
"В нем произвольным образом выбирается m подмножеств"

Для такой постановки вообще нет решения.

Или же вы имеет ввиду равномерное распределение? Но равномерное распределение не есть произвольное.


пс: теория вероятностей

 Профиль  
                  
 
 
Сообщение04.05.2007, 11:25 
Аватара пользователя


02/05/07
144
А если в такой постановке:
Имеется конечное множество, состоящее из V элементов. В нем произвольным образом выбирается m подмножеств, каждое из которых состоит из n элементов. Найти вероятность того, что в попарном пересечении первого подмножества с последующими подмножествами содержится не более чем k элементов.

Вообще задача имеет практическое применение и хотелось бы конечно решить её в первоначальной постановке, но если не получается то в общем то и такая постановка возможна. Вот это будет правильно? :

Bod писал(а):
Можно попробовать следующие рассуждения (я в этом не спец так что проверяйте):
Вероятность что в пересечении первой области со второй i элементов:
\[
\frac{{C_N^i  \cdot C_{V - N}^{N - i} }}
{{C_V^N }}
\]
Вероятность что в пересечении первой области со второй не больше чем k элементов:
\[
P_1  = \sum\limits_{i = 0}^k {\frac{{C_N^i  \cdot C_{V - N}^{N - i} }}
{{C_V^N }}} 
\]
Вероятность что в попарном пересечении первой области со всеми последующими не больше чем k элементов:

\[
{\text{P}}_{\text{2}}  = P_1 ^m 
\]


Только в конце там по моему не в степени m а в степени m-1

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

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



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

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


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

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