S>Вы слегка наивны — не понимаете суть задачи. То, что вы пишете также не верно: S>p(n) = 2^n — это мощность множества подмножеств, а не число разбиений. Числа Каталана в этой задаче вообще ни к селу ни к городу, вы уж извините. Кроме того, с каких пор Википедия является хоть сколь-нибудь авторитетным источником?
с некоторых пор является
PI>>с некоторых пор является
S>Назовите мне в таком случа, пожалуйста, хоть один научный труд, ссылающийся на википедию.
не ссылаются, потому что там известные вещи опубликованы в соответствующих областях
и когда не работаешь в какой-то области, удобно посмотреть (на вики), о чем в ней речь идет
математик Вербицкий пользуется википедией, если Вам эта фамилия о чем-то говорит
а вот Вам, должен заметить, с таким гонором ещё долго искать соавторов решения одной математической задачи
Смысл этого поста – поиск соавторов решения одной математической задачи, о важности которой я сам могу лишь догадываться.
Очень давно в 1988 году на всесоюзной олимпиаде по программированию ставилась задача о подсчете числа способов разбиения конечного множества на непустые подмножества. Эквивалентная задача — для числа n найти количество образующих его различных сумм (без учета порядка слагаемых). Например, для числа 4 их всего 5: 1+1+1+1, 2+1+1, 3+1, 2+2, 4. Задача не новая и много где обсуждалась, но везде, кде я находил о ней информацию, уклон идет в ненужную мне сторону.
Меня эта задача интересует в основном потому, что я знаю, как она может быть связана с задачей о дезинтеграции дискретных систем, это, так сказать, то, что не дает мне спать спокойно на протяжении нескольких лет. Суть дезинтеграции дискретных систем в следующем: есть множество элементов, каждый из которых связан со всеми остальными в этом множестве. Число связей, соответственно, n*(n-1)/2. В некоторый момент времени каждая из связей исчезает с вероятностью p. После исчезновения части связей система разваливается на несвязанные сегменты, число которых варьируется от 1 (система не развалилась) до n (система развалилась полностью). Вопрос в том, как посчитать вероятности образования сегментов с числом элементов k. Задача дезинтеграции имеет продолжение в области фрактальной геометрии и кристаллографии. Я не уверен в русском термине “дезинтеграция”, т.к. в основном работаю с англоязычной литературой.
Пусть J(n,k) – число разбиений n-элементного множества на k непустых подмножеств, или число k-сумм равных n. (k-сумма содержит ровно k натуральных слагаемых).
На данный момент мне известны следующие факты:
1. J(n,k) = [сумма i := от 1 до k] J(n-k,i)
2. из п.2 следует J(n,k) = J(n-1,k-1) + J(n-k,k)
3. из п.2 следует, что полное число разбиений n-множества есть p(n) = J(2n,n)
Меня интересует функция вида j(n,k)=J(n,k)/J(2n,n). Для тех, кому еще интересен этот топик, я думаю, понятно, что она выражает. Еще более интересная функция – f(x)=lim j(n,floor(nx)) при n стремящимся в бесконечность. Я стоил эту функцию для n порядка 4000, график напоминает что-то вроде x*exp(-x), но распределение явно иное. Фокус в том, что у распределения f(x) есть достаточно узкий (и, соответственно, высокий) пик в районе x=0.6, имеющий характерный крутой подъем и более пологий скат, как у распределения Планка
Мне не известно, существует ли у функции f(x) аналитическое представление, точнее, мне известно лишь то, что она имеет пикообразный максимум, находящийся вблизи нуля. Хотелось бы найти хотя бы уравнение, задающее функцию f(x). Исследовать её связи со специальными функциями и т.п. Если кто заинтересовался, давайте поищем решения и напишем совместную работу.
Здравствуйте, seabeer, Вы писали:
S>Смысл этого поста – поиск соавторов решения одной математической задачи, о важности которой я сам могу лишь догадываться.
ну а это...
понятно надеюся, что S>1. J(n,k) = [сумма i := от 0 до k] С(n,i) ? (сумма биномиальных коэффициентов)
что число разбиений n-множества есть p(n) = 2^n ?
ну и т.д.... если непонятно, надо в википедии посмотреть про биномиальные коэффициенты, числа каталана и пр.
Здравствуйте, PhantomIvan, Вы писали:
PI>ну а это... PI>понятно надеюся, что S>1. J(n,k) = [сумма i := от 0 до k] С(n,i) ? (сумма биномиальных коэффициентов) PI>что число разбиений n-множества есть p(n) = 2^n ? PI>ну и т.д.... если непонятно, надо в википедии посмотреть про биномиальные коэффициенты, числа каталана и пр.
Вы слегка наивны — не понимаете суть задачи. То, что вы пишете также не верно:
p(n) = 2^n — это мощность множества подмножеств, а не число разбиений. Числа Каталана в этой задаче вообще ни к селу ни к городу, вы уж извините. Кроме того, с каких пор Википедия является хоть сколь-нибудь авторитетным источником?
Что такое число разбиений множества? Сначала нужно определиться с тем, различимы ли элементы исходного множества.
Пусть элементы различимы, тогда из множества {a,b,c} можно построить 5 различных разбиений: ({a},{b},{c}), ({a},{bc}), ({b},{ca}), ({c},{ab}), ({abc}).
Пусть элементы не различимы, тогда из множества {a,a,a} можно построить 3 различных разбиения: ({a},{a},{a}), ({a},{aa}), ({aaa}).
В моей задаче речь идет именно о разбиениях множества тождественных элементов. Они тождественны как атомы в однородном кристаллическом домене, перестановка их местами ничего не меняет. J(n,k) — число разбиений множества тождественных элементов на k подмножеств, которые будут отличаться только мощностью и ничем иным.
Здравствуйте, PhantomIvan, Вы писали:
S>>>Назовите мне в таком случа, пожалуйста, хоть один научный труд, ссылающийся на википедию.
PI>пресловутый хоть один научный трудздесь PI>эт в порядке добивания
В целом ссылки на статьи в интернете давно
уже присутствуют в различных научных трудах...
