|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 25 Dec 2001 19:02:20
To : Medvedev Michael
Subject : Помогите найти решение
--------------------------------------------------------------------------------
Replying to a message of Medvedev Michael to Vitaly Slobodskoy:
MM> Это упорядоченные числа Бэлла.
MM> a(0) = 1,
MM> a(n) = Sum from k=1 to n of C(n,k)*a(n-k),
MM> где C(n,k) - биномиальные коэффициенты.
MM> 1, 1, 3, 13, 75,541, 4683, 47293, 545835, 7087261, 102247563,
MM> 1622632573, 28091567595, ...
MM> Эта последовательность имеет номер A000670 в
MM> The On-Line Encyclopedia of Integer Sequences
MM> http://www.research.att.com/~njas/sequences/
MM> -----------------------------------
MM> Только не могу понять как она строится (откуда берется)
Пусть у нас есть n элементов, которые нам надо упорядочить. Рассмотрим
произвольное упорядочение. В нем есть ровно k наибольших (равных между собой)
элементов. Выкинем все эти равные элементы, тогда количество упорядочений
остальных равно a(n-k). Если заметить, что наибольшие элементы мы можем выбрать
C(n,k) способами, то сразу получим формулу
a(n) = Sum from k=1 to n of C(n,k)*a(n-k).
Regards, ш.ш
Max ~
--- FleetStreet 1.27.3.7
* Origin: (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
