Выбираем m подмножеств из n элементов

[Diom]

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

[Capella]

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

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

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

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

[PAV]

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

[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 \]

Вероятность что в попарном пересечении второго со всеми последующими подмножествами элементов не более чем 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 \]

Проверяй - я в этом не очень уверен.

[Dan_Te]

Bod
Гм, как вы ее!

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

[PAV]

Bod писал(а):

Учитывая что события являются не зависимыми то можно перемножить:

\[ {\text{P}}_{\text{3}} = P_1 ^m \cdot P_1 ^{m - 1} \cdot ...P_1 ^1 \]

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

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

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

[Bod]

Цитата:

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

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

[PAV]

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

[Bod]

Цитата:

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

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

Ну тогда в голову приходит только такое:

\[ 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 }}} \]

[PAV]

Не понимаю. В чем смысл чисел $i$?

[Bod]

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

[PAV]

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

[esperanto]

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

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

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


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

[Diom]

А если в такой постановке:
Имеется конечное множество, состоящее из 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