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

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 02.12.2011, 12:47
Новичок

Отправить личное сообщение для malira Посмотреть профиль Найти все сообщения от malira
 
Регистрация: 02.09.2010
Сообщений: 12

Случайные размещения с ограничениями
Задача о случайном размещении n частиц (дробинок) по N ячейкам (ящикам) является классической (Колчин и др. Случайные размещения).

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

Подскажите есть ли работы, близкие к описанной задаче?
  #2  
Старый 02.12.2011, 14:53
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Не совсе уловил, что должно являться решением задачи.
Можно подсчитать число таких размещений, можно перечислить их (если количество разумное), можно сгенерировать случайное размещение...
  #3  
Старый 05.12.2011, 17:43
Новичок

Отправить личное сообщение для malira Посмотреть профиль Найти все сообщения от malira
 
Регистрация: 02.09.2010
Сообщений: 12

Интересует распределение вероятностей или хотя бы среднее количество занятых (возможно не до предела) ячеек.

Задачу можно интепретировать на числовой оси.
|--L--||--L--||--L--||--.........--|
|<----------- M ---------------->|
L - "длина" каждой ячейки, M - общая длина.
Кол-во ячеек N=M/L (целое)
Размещаемые частицы различны в том смысле, что они могут занять только одно "частицеместо". Иначе - размещаются случайные равномерно распределенные числа от 1 до M.

Тогда
1. Размещаем 1 частицу:
P(1|1,N)=1 - одна частица попадет в какую-либо ячейку
2. Размещаем 2 частицы:
P(1|2,N)=C(1,N)*[L/M]*[(L-1)/(M-1)] - кол-во ячеек на вероятность попадания 2 частиц в одну ячейку
P(2|2,N)=C(1,N)*[L/M]*[(M-L)/(M-1)] - здесь вероятность попадания 2 частиц в разные ячейки.
Имеем (для проверки) P(1|2,N)+P(2|2,N)=1, так как других исходов не м.б.

и т.д. для 3,4,5 частиц

Интересует выражение для P(k|n,N), k<=n
  #4  
Старый 28.11.2012, 12:12
Пользователь

Отправить личное сообщение для maxal Посмотреть профиль Найти все сообщения от maxal
 
Регистрация: 28.11.2006
Сообщений: 68

Количество размещений m неразличимых частиц по N ячейкам, каждая ёмкостью L, равно

f(m,N,L)=\sum_{k=0}^{\min\{N,\lfloor m/(L+1)\rfloor\}} (-1)^k \binom{N}{k} \binom{m-k(L+1)+N-1}{N-1}

То же самое при условии, что все ячейки заняты:

g(m,N,L)=\sum_{k=0}^{\min\{N,\lfloor m/L\rfloor\}} (-1)^k \binom{N}{k} S(m-kL,N),
где S(,) - числа Стирлинга 2-го рода.

Например, вероятность того, что все частицы попали ровно в K ячеек равно \binom{N}{K} g(m,K,L) / f(m,N,L)
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Простая задача со сожными ограничениями Rolly1992 Задачи 2 17.01.2009 12:10
Алгоритм подсчета числа перестановок с ограничениями Rusl_K Математические алгоритмы 3 23.03.2008 13:24
размещения с повторениями на с++ Норе Реализация, исходники, языки 3 14.11.2007 16:21
алгоритм разбиения числа с ограничениями незарегистрированный Математические алгоритмы 0 18.04.2007 04:00
транспортные задачи с ограничениями на магистралях Pshk Математические алгоритмы 0 14.11.2006 14:39