Комбинаторика: n различимых предметов в m неразличимых ящиков

Аватар пользователя
Ian
Сообщений: 605
Зарегистрирован: 18 янв 2016, 19:42

Комбинаторика: n различимых предметов в m неразличимых ящиков

Сообщение Ian » 12 окт 2020, 10:33

Решение для m=4 как "Number of palindromic structures using a maximum of four different symbols" здесь http://oeis.org/A007581
Оно еще и просто выводится. Рассмотрим [math]- число разбиений n различимых предметов на 4 неразличимых ящика (пустые ящики допускаются). Расположение n-го предмета даст 4 различных способа тогда и только тогда, когда 4 ящика с n-1 предметами различимы. Если в этом расположении пустых ящиков было не более одного, то все ящики различимы (один, может быть, отличим от остальных тем, что он пуст). Если пустых ящиков два, то два положения n-го предмета неразличимы и для [math] расположений будет три принципиально различных места поместить n-й предмет вместо 4-х. А для одного из указанных (когда все предыдущие n-1 предмета в одном ящике) всего 2. Получаем
[math]
Это обычная линейная неоднородная рекуррентность
[math], что совпало с формулой в oeis
Для произвольного, но фиксированного m, общая формула, видимо, нереальна, но какова асимптотика по n (при фиксированном m)?
Если бы ящики были различимы, ответ разумеется [math]

zykov
Сообщений: 871
Зарегистрирован: 06 янв 2016, 17:41

Комбинаторика: n различимых предметов в m неразличимых ящиков

Сообщение zykov » 12 окт 2020, 17:08

Да так наверно и будет $m^n$.
Вот возмите какое-то $m$ (например $10$) и случайно распределите гораздо большее количество различимых предметов $n$ (например $10^6$) в эти $m$ различимых ящиков. С подавляющей вероятностью, не будет двух ящиков с одинаковым количеством предметов. Значит количество этих комбинаций с различимыми ящиками для одной комбинации с неразличимыми ящиками равно количеству перестановок - $m!$.
Т.е. асимптотика будет $$\frac{m^n}{m!}$$.
Вот и у Вас тут асимптотика $$\frac{4^n}{3 \cdot 8} = \frac{4^n}{4!}$$.

Аватар пользователя
Ian
Сообщений: 605
Зарегистрирован: 18 янв 2016, 19:42

Комбинаторика: n различимых предметов в m неразличимых ящиков

Сообщение Ian » 13 окт 2020, 14:03

Отлично. А если бы предметы были неразличимы такая вот жуть https://ru.wikipedia.org/wiki/Разбиение_числа


Вернуться в «Математика»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: Siervajbm и 12 гостей