dm
Удален
|
    
Одна знакомая по мылу прислала вопрос, который ей встретился по работе:
Может, знаете как упростить следующее выражение:
$\sum_{i=1}^{d}\binom{d}{i} \binom{id}{k-i}$?
Мне надо от этой ерунды как функции от к найти максимум, а в таком виде как-то не очень искать хочется 
В имеющихся под рукой книжках не нашла. Вдруг где-то на глаза попадется нечто подобное, напишите, пожалуйста.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 31 мая 2005 0:39 | IP
|
|
M0rFium
Удален
|
Уважаемы dm, а нельзя ли переписать выражение в более доступном для простых смертных виде? А то мне не очень понятно (что грустно, ведь это говорит о моей безграмотности
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 31 мая 2005 7:01 | IP
|
|
Guest
Новичок
|
численно получается, что максимум достигается при k=(d^2 + 2d)/2.
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 31 мая 2005 8:09 | IP
|
|
dm
Удален
|
M0rFium
Я и переписал в описании топика:
S(k)=sum_(i=1)^d (C_d^i)*(C_(i*d)^(k-i))
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 31 мая 2005 12:12 | IP
|
|
dm
Удален
|
Я задал знакомой уточняющий вопрос:
мне не совсем понятно, как заданы слагаемые этой суммы. Предполагается, что у биноминального коэффициента оба индекса целые неотрицательные и верхний не превышает нижнего? Но тогда должно было бы быть выполнено: $i\cdot d\ge k-i\ge0$ для всех $i=1,\ldots,d$. Вроде бы это приводит к $d+1\ge k\ge d$. Или я что-то неправильно понимаю?
Её ответ:
На самом деле там есть ограничения, поскольку мне надо было посчитать ширину решетки идемпотентов одной полугруппы, что свелось к подсчету k-реберных подграфов 2-уровневого d-регулярного дерева. Лучшего способа не придумала Второй биноминальныйкоэффициент -- это уже упрощенное выражение. Там изначально была двойная сумма. Сначала k=a+b, $a \leq d, b \leq ad$, потом по $k-i=a_1+ \ldots+ a_i$. Второй биноминальный коэффициент -- это уже упрщенная внутрення сумма. Дело за всей.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 31 мая 2005 22:07 | IP
|
|
Guest
Новичок
|
Биномиальный коэффициент определен для всех целых значений обоих индексов. См. определение тут.
Поэтому данная сумма вполне определена. Значение k можно ограничить исходя из того, когда в этой сумме все слагаемые будут равны нулю. Это произойдет при k-1<d и при k-d>d^2. Поэтому возможные значения k лежат в интервале d+1<=k<=d^2+d. Как уже было указано, численно значение максимума суммы достигается при k=(d^2+2d)/2.
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 2 июня 2005 20:17 | IP
|
|
dm
Удален
|
Guest
То, что биноминальные коэффициенты можно доопределить для отрицательных, дробных и т.д. значений индексов, - это понятно.  Вопрос в том, какой комбинаторный смысл это имеет и имеет ли сейчас (в данной конкретной задаче про деревья и подграфы).
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 3 июня 2005 13:40 | IP
|
|
dm
Удален
|
Мне удалось добиться от знакомой, какая сумма с биноминальными коэффициентами ее интересовала
Сумма была такая: $\sum_{i+j=k, i \leq d, j \leq
id}\binom{d}{i} \Big( \sum_{a_1+\ldots+a_i=k-i}\prod_{m=1}^{i}
\binom{d}{a_m} \Big)=\sum_{i+j=k, i \leq d, j \leq id}\binom{d}{i}
\binom{id}{k-i}=\sum_{i=1}^{d}\binom{d}{i} \binom{id}{k-i}$
Мой ответ:
Кажется, последний переход не законен.
Должно быть $\sum_{\lceil\frac{k}{d+1}\rceil\le
i\le\min(k,d)} \binom{d}{i}\binom{id}{k-i}$.
Это было бы то же самое, что
$\sum_{i=1}^{d}\binom{d}{i}\binom{id}{k-i}$,
только при $k\le d+1$, $k\ge d$. (я не вникаю в
комбинаторный смысл твоих $k$ и $d$ ;-) )
Но тогда $k$ могло бы принимать только два значения: $d$ или $d+1$,
и найти максимум по $k$ твоей суммы не составило бы труда.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 3 июня 2005 16:30 | IP
|
|
Guest
Новичок
|
Последней сумме суммирование должно происходить по области
i <= d
i <= k
k-i <= id или i >= k/(d+1)
Все зависит от того как связаны k и d.
Если k<d+1 то суммирование должно быть по i=1..k
Если k>=d+1, то суммированиедолжно быть по i=ceil(k/(d+1))..d
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 3 июня 2005 23:02 | IP
|
|
|
Форум
Максимум суммы с биноминальными коэффициентами
