Форум
» Назад на решение задач по физике и термеху
Регистрация | Профиль | Войти | Забытый пароль | Присутствующие | Справка | Поиск

» Добро пожаловать, Гость: Войти | Регистрация
    Форум
    Математика
        Максимум суммы с биноминальными коэффициентами
Отметить все сообщения как прочитанные   [ Помощь ]
» Добро пожаловать на форум "Математика" «

Переход к теме
<< Назад Вперед >>
Одна страница
Модераторы: Roman Osipov, RKI, attention, paradise
  

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

Отправка ответа:
Имя пользователя   Вы зарегистрировались?
Пароль   Забыли пароль?
Сообщение

Использование HTML запрещено

Использование IkonCode разрешено

Смайлики разрешены

Опции отправки

Добавить подпись?
Получать ответы по e-mail?
Разрешить смайлики в этом сообщении?
Просмотреть сообщение перед отправкой? Да   Нет
 

Переход к теме
<< Назад Вперед >>
Одна страница

Форум работает на скрипте © Ikonboard.com