2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему
 
 Вывод формулы сочетания с повторениями
Сообщение20.09.2024, 23:23 


17/10/23
53
Как вывести формулу сочетания с повторениями?


В интернете есть выводы, в которых используются "разделитель" между множеством элементов разных типов, после чего задачу сводят к формуле перестановки с повторениями. Вывод понятен, но, быть может, кто-то предложит что-то ещё ? Мне почему-то казалось что тут много вариантов вывода, но я терпел фиаско при попытке придумать нечто альтернативное.

 Профиль  
                  
 
 Re: Вывод формулы сочетания с повторениями
Сообщение21.09.2024, 08:41 


17/10/16
4759
Cosmochelik
Допустим, мы выбираем $m$ шаров из урны, содержащей $n$ разных шаров. Видно, что случай сочетаний с повторениями $\frac{(n+m-1)!}{m!(n-1)!}$ сводится к случаю сочетаний без повторений $\frac{n!}{m!(n-m)!}$, нужно только добавить в исходную урну с $n$ разными шарами еще $m-1$ других разных шаров, которые и будут играть роль "дубликаторов". Т.е. если они попадают в нашу выборку, то это означает, что какой-то шар (из исходного не пополненного множества $n$) был выбран повторно. Скажем, если в выборку попали все $m-1$ "дубликаторов" и 1 шар из исходного множества, то это значит, что этот 1 шар был выбран $m$ раз.

 Профиль  
                  
 
 Re: Вывод формулы сочетания с повторениями
Сообщение21.09.2024, 10:02 
Заслуженный участник


07/08/23
1055
Обозначим через $f(m, n)$ количество сочетаний с повторениями (в терминологии sergey zhukov$m$ шаров выбирается из урны с шарами $n$ типов). При каждом таком сочетании либо последний $n$-й тип не используется, либо можно считать, что последний выбранный шар ровно $n$-го типа, то есть $f(m, n) = f(m, n - 1) + f(m - 1, n)$. Отсюда формула выводится по индукции, ну и нужна база $f(0, n) = 1$, $f(m, 0) = 0$ при $m > 0$.

А ещё можно через производящие функции. Так как $f(m, n)$ — это количество представлений $m$ в виде суммы $n$ натуральных чисел (0 считается натуральным), то $\sum_{m = 0}^\infty f(m, n) t^m = (\sum_{i = 0}^\infty t^i)^n = (1 - t)^{-n}$. Дальше раскрываем по биному Ньютона, $(1 - t)^{-n} = \sum_{m = 0}^\infty (-1)^m \binom {-n} m$, ну и $(-1)^m \binom {-n} m = \binom {n + m - 1} m = \frac{(n + m - 1)!}{m! (n - 1)!}$. Только формулу с факториалами надо творчески понимать при $n = 0$.

 Профиль  
                  
 
 Re: Вывод формулы сочетания с повторениями
Сообщение21.09.2024, 13:03 


17/10/23
53
sergey zhukov
А как доказать что нужно добавить именно $m - 1$ ?
dgwuqtj
Да, спасибо. Я пытался получить какую-то рекуррентную формулу, но тогда что-то пошло не так)

 Профиль  
                  
 
 Re: Вывод формулы сочетания с повторениями
Сообщение22.09.2024, 07:40 


17/10/16
4759
Cosmochelik
Ну, тут можно сказать, что сочетания с повторениями - это то же, что выборка с возвращением. При выборке с возвращением после выборки последнего шара (который уже не возвращается), в урне остается $n-1$ шаров. Значит (в нашем подохде с добавлением шаров), туда нужно было изначально добавить $m-1$ шаров.

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

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



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

Сейчас этот форум просматривают: DariaRychenkova


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

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