Количество 3-ичных чисел с фиксированной суммой цифр

[cyb12]

Пытаюсь посчитать число различных $n$-разрядных чисел в 3-ичной системе счисления, сумма цифр которых равна $L.$ Обозначу это число за $f(n,L),$ понятно, что $L\leqslant 2n.$Хотелось бы понять можно ли получить точную формулу для этого числа.
При этом получилось:
$f(n,0)=1;$
$f(n,1)=n;$
$f(n,2)=n+\dfrac{n(n-1)}{2};$
$f(2,L)= \begin{cases}1, & L=0,4\\2, & L=1,3\\3, & L=2\end{cases};$$f(2,L)= \begin{cases}1, & L=0,6\\3, & L=1,5\\6, & L=2,4\\7,&L=3\end{cases};$
Кроме того, для $1<L\leqslant 2n-1$ справедливо:
$f(n+1,L+1)=f(n,L+1)+f(n,L)+f(n,L-1).$
Вроде линейное реккурентное соотношение. Но оно разрешимо?

[ИСН]

Триномиальные коэффициенты. Отвязаться от рекуррентности можно, но там всё равно получается выражение с суммированием.
http://www.research.att.com/~njas/sequences/A002426

[Хорхе]

ИСН в сообщении #314099 писал(а):

http://www.research.att.com/~njas/sequences/A002426

Тут последовательность с одним индексом, а не с двумя.

Вот это больше похоже на правду:
http://www.research.att.com/~njas/sequences/A027907

Там и "формулы" есть.

[cyb12]

То есть $f(n,L)$ есть коэффициент при $x^L$ в разложении $(1+x+x^2)^n.$ А можно ли его как-нибудь оценить сверху каким-нибудь выражением без суммы?

[ИСН]

$3^n$

[Хорхе]

${3^n}/{\sqrt{n}}$, существенно лучше не оцените (это если без $L$).

[cyb12]

А есть какая-нибудь оценка, содержащая $L$?

Хорхе в сообщении #314265 писал(а):

${3^n}/{\sqrt{n}}$, существенно лучше не оцените (это если без $L$).

А это Вы как получили?

[Хорхе]

cyb12 в сообщении #314609 писал(а):

А есть какая-нибудь оценка, содержащая $L$?

Хорхе в сообщении #314265 писал(а):

${3^n}/{\sqrt{n}}$, существенно лучше не оцените (это если без $L$).

А это Вы как получили?

Вообще я оценивать не умею, только асимптотику искать :)

Написал генератрису максимального из чисел, нашел ближайшую к нулю сингулярность в точке $1/3$, связанную с квадратным корнем. Заключил отсюда, что асимптотика такая: $c 3^n/\sqrt{n}$. Константу лень считать, но эмпирические наблюдения подсказывают, что она меньше единицы. То есть я не до конца уверен в своей оценке, но где-то такая.

Например, можно найти асимптотику по $n$ $f(n,L)$ при фиксированном $L$. Будет (очевидно) $C_n^L \sim n^L/L!$. То есть можно написать $f(n,L)\le C(L) n^L$. Подойдет, например, $C(L) = 3^L/L!$ (самое тупое, что пришло в голову). Для каких-то нужд это хорошая оценка. Для других не очень.

Можно (опять же, лень) найти асимптотику $f(n,an)$ при фиксированном $a$ из нормальной аппроксимации (ЦПТ). (Кстати, в предыдущем абзаце асимптотику можно получить из пуассоновской аппроксимации.)

[cyb12]

Хорхе в сообщении #314628 писал(а):

Например, можно найти асимптотику по $n$ $f(n,L)$ при фиксированном $L$. Будет (очевидно) $C_n^L \sim n^L/L!$. То есть можно написать $f(n,L)\le C(L) n^L$. Подойдет, например, $C(L) = 3^L/L!$ (самое тупое, что пришло в голову). Для каких-то нужд это хорошая оценка. Для других не очень.

Как связаны $C_n^L$ и $f(n,L)\leqslant C(L) n^L$? Откуда это?

[Хорхе]

cyb12 в сообщении #314719 писал(а):

Как связаны $C_n^L$ и $f(n,L)\leqslant C(L) n^L$? Откуда это?

Через $C_n^L\sim n^L/L!$, $n\to\infty$.

Откуда взялась асимптотика для биномиальных коэффициентов, не скажу, подумайте сами. Откуда взялось $3^L/L!$, подскажу, если не придумаете.

[cyb12]

Про биномиальный коээфициент очевидно. Но все-таки, откуда $f(n,L)\leqslant C(L)n^L$?

[ИСН]

Через явную формулу для $f(n,1)$, $f(n,2)$, и долгие размышления.