2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Количество 3-ичных чисел с фиксированной суммой цифр
Сообщение27.04.2010, 22:46 
Пытаюсь посчитать число различных $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).$
Вроде линейное реккурентное соотношение. Но оно разрешимо?

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

 
 
 
 Re: Количество чисел
Сообщение29.04.2010, 17:09 
Аватара пользователя
ИСН в сообщении #314099 писал(а):

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

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

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

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

 
 
 
 Re: Количество чисел
Сообщение30.04.2010, 09:02 
Аватара пользователя
$3^n$ :lol:

 
 
 
 Re: Количество чисел
Сообщение30.04.2010, 09:24 
Аватара пользователя
${3^n}/{\sqrt{n}}$, существенно лучше не оцените (это если без $L$).

 
 
 
 Re: Количество чисел
Сообщение01.05.2010, 11:06 
А есть какая-нибудь оценка, содержащая $L$?

Хорхе в сообщении #314265 писал(а):
${3^n}/{\sqrt{n}}$, существенно лучше не оцените (это если без $L$).


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

 
 
 
 Re: Количество чисел
Сообщение01.05.2010, 12:28 
Аватара пользователя
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$ из нормальной аппроксимации (ЦПТ). (Кстати, в предыдущем абзаце асимптотику можно получить из пуассоновской аппроксимации.)

 
 
 
 Re: Количество чисел
Сообщение01.05.2010, 16:23 
Хорхе в сообщении #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$? Откуда это?

 
 
 
 Re: Количество чисел
Сообщение01.05.2010, 16:58 
Аватара пользователя
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!$, подскажу, если не придумаете.

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

 
 
 
 Re: Количество чисел
Сообщение04.05.2010, 22:00 
Аватара пользователя
Через явную формулу для $f(n,1)$, $f(n,2)$, и долгие размышления.

 
 
 [ Сообщений: 12 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group