Снова оценки комбинаторных выражений

[Cronopio]

Нужна какая-нибудь умная идея, требуется оценить
\sum_{m=1}^{L}\sum_{k_1+...+k_m=L, k_i>0} e^{-L} \frac{ k_1^{k_2} k_2^{k_3}\ldots k_{m-1}^{k_m}}{k_1!\ldots k_m!}(\frac{L^2}{N}+O(\frac{L^4}{N^2}))

L<\log (N), N\to \infty

Выглядит устрашающе... что делать мне не понятно. Членов в сумме, вроде, 2^{L-1}, но я даже отдельные члены не понимаю как оценивать по-хорошему.

Спасибо за любые идеи =).

[Cronopio]

А если по-проще:

Где на многообразии k_1+ k_2+\ldots+k_m=L, k_i>1 достигается максимум:
\frac{ k_1^{k_2} k_2^{k_3}\ldots k_{m-1}^{k_m}}{k_1!\ldots k_m!}

Можно выбирать наиболее удобные L,m

[maxal]

Некоторые незаконченные мысли вслух

Числитель можно оценить, пользуясь перестановочным неравенством, так:

$$\ln( k_1^{k_2} k_2^{k_3}\ldots k_{m-1}^{k_m} ) = k_2 \ln k_1 + k_3\ln k_2 + \dots + k_m\ln k_{m-1}\leq k_1 \ln k_1 + k_2\ln k_2 + \dots + k_{m-1}\ln k_{m-1} + (k_m - k_1)\ln k_{m-1}.$$

Причем равенство достигается, когда $k_1=k_2=\dots=k_{m-1}$.

В знаменателе можно для простоты считать, что

$$k! \approx \left(\frac{k}{e}\right)^k\sqrt{2\pi k}$$

. Тогда:

$$\ln(k_1!k_2!\dots k_m!)\approx k_1\ln k_1 + k_2\ln k_2 + \dots + k_m\ln k_m - L + \ln ((2\pi)^{m/2} \sqrt{k_1\dots k_m}) \leq$$

$$\leq k_1\ln k_1 + k_2\ln k_2 + \dots + k_m\ln k_m - L + \ln ((2\pi)^{m/2} (L/m)^{m/2})$$

Только вот нехорошо, что это тоже оценка сверху, и делить их друг на друга не с руки (хотя все красиво бы сократилось).

Можно попробовать получить оценку снизу, если изначально не трогать числитель, тогда:

$$\frac{ k_1^{k_2} k_2^{k_3}\ldots k_{m-1}^{k_m}}{k_1!\ldots k_m!}\geq \frac{e^{L}}{(2\pi L/m)^{m/2}} k_1^{k_2-k_1} k_2^{k_3-k_2}\ldots k_{m-1}^{k_m-k_{m-1}}k_m^{0-k_m}.$$

(где интуитивно напрашивается взять $k_1,\dots,k_m$ равной арифметической прогрессии с фиксированным шагом).
Заметим, что если $k_m$ зафиксировано, то можно попробовать последовательно вычислить оптимальным $k_{m-1}, k_{m-2}, \dots$, попробовать максимизировать на каждом шаге значение $x^{s-x}$, где $s$ - уже известная константа. Оптимальное значение $x$ в нем выражается через W-функцию Ламберта так: $e^{W(es)-1}=\frac{s}{W(es)}$.

С другой стороны, эту же оценку можно записать как:

$$\frac{e^{L}}{(2\pi L/m)^{m/2}} \left(\frac{1}{k_1}\right)^{k_1} \left(\frac{k_1}{k_2}\right)^{k_2} \left(\frac{k_2}{k_3}\right)^{k_3}\dots \left(\frac{k_{m-1}}{k_m}\right)^{k_m}$$

(и здесь напрашивается выбор $k_i$ в виде убывающей геометрической прогрессии).
Если зафиксировать $k_1$, то можно попробовать последовательно максимизировать значения $(t/y)^y$ для разных констант $t$. Оптимальное $y$ тут имеет вид $y=et$.

... продолжение следует ...

[Руст]

Основной вклад в сумму дают наборы $k_i$ каждый из которых равны одному из трёх значений 1,2,3. При этом дроби растут экспоненциально от L, например если все равны 2 дробь $2^{L/2}$ есть и значения больше когда перемешиваются двойки и тройки. Количество таких наборов так же экспоненциально растёт.

[maxal]

Руст писал(а):

Основной вклад в сумму дают наборы $k_i$ каждый из которых равны одному из трёх значений 1,2,3. При этом дроби растут экспоненциально от L, например если все равны 2 дробь $2^{L/2}$ есть и значения больше когда перемешиваются двойки и тройки. Количество таких наборов так же экспоненциально растёт.

Тут важно какое основание у этих функций роста, так как они могут в принципе "гаситься" присутствующим значением $e^{-L}$.

[Gafield]

Цитата:

Нужна какая-нибудь умная идея, требуется оценить

$$ \sum_{m=1}^{L}\sum_{k_1+...+k_m=L, k_i>0} e^{-L} \frac{ k_1^{k_2} k_2^{k_3}\ldots k_{m-1}^{k_m}}{k_1!\ldots k_m!}(\frac{L^2}{N}+O(\frac{L^4}{N^2})) $$

А зачем такая сложная запись? Вроде, надо оценить величину, зависящую тллько от одной переменной:

$$ a(n)=\sum_{m=1}^{n}\sum_{k_1+...+k_m=n,\, k_i>0}\frac{ k_1^{k_2} k_2^{k_3}\ldots k_{m-1}^{k_m}}{k_1!\ldots k_m!}. $$

Эмпирически правдоподобны гипотезы, что

$$a(n)\le e^n$$

, последовательность

$$\frac{\ln a(n)}n$$

монотонно возрастает и

$$\lim_{n\to\infty}\frac{\ln a(n)}n=1$$

,

$$\lim_{n\to\infty}a(n)e^{-n}=0$$

. Более сильные (и менее надежные:) ): $a(n)\ge n^{-3/2}e^{n}$ при $n\ge20$ и, похоже, сильно понизить показатель $\alpha$ в асимптотической оценке $a(n)\ge n^{-\alpha}e^{n}$ нельзя ($\alpha\ge1.47...$).