Найти количество комбинаций

[Vedr]

Имеется $p$ целых неотрицательных чисел таких, что $u_1+2u_2+...+pu_p=x$, причем, все $u \le k$, k, p - натуральные, x - целое неотрицательное. Требуется, зная $x, k, p$, определить количество комбинаций чисел $u_1+...+pu_p$, которые бы в указанной сумме давали $x$
Пример для случая $p = 3, x = 4, k = 6$:
$u_3 = 1, u_2 = 0, u_1 = 1$
$u_3 = 0, u_2 = 0, u_1 = 4$
$u_3 = 0, u_2 = 1, u_1 = 2$
$u_3 = 0, u_2 = 2, u_1 = 0$
Всего 4 комбинации.

[Sonic86]

Рекуррентная формула Вас удовлетворит?

[Vedr]

Да. Мне неизвестно, есть ли там явная формула вообще, хотя, думается, что что-то должно быть. В принципе, подойдет даже оценка сверху. Навскидку, кол-во комбинаций не превосходит $x^p/p!$, но это очень грубо.

[Sonic86]

Ну рекуррентная формула-то строится просто: перебираете $u_p$ значения $u_p$ от нуля до $k$ и выражаете число решений от $p$ через число решений от $p-1$.
Если бы $u_j \leq k$ не было, то была бы задача о поиске числа представлений натурального числа, а для нее простой явной формулы точно нету.

-- Пт май 06, 2011 20:05:31 --

Приближенно можно оценить как число целых точек в $p-1$-мерном симплексе $2u_2+...+pu_p \leq x, u_j \geq 1$, его стороны равны $a_j:\frac{x}{2}-1;...;\frac{x}{p}-1$, тогда $V_{p-1}=\frac{\prod\limits_j a_j}{(p-1)!} \leq \frac{x^p}{p(p-1)!^2}$. Это с точностью до $O(x^{p-1})$. Еще полезно следить, чтобы при этом было $p \leq x$, но это уже детали.

[Vedr]

Огромное спасибо за идею с объемом симплекса и оценку сверху, как раз для $p \leq x $. Это то, что нужно!

-- Пт май 06, 2011 18:47:02 --

Только мне несовсем ясно, почему рассматривается $n-1$-мерный симплекс?

[Sonic86]

Vedr писал(а):

Только мне несовсем ясно, почему рассматривается $n-1$-мерный симплекс?

Чтобы от равенства $1u_1+...+pu_p=x$ перейти к неравенству $2u_2+...+pu_p=x-u_1 \leq x$.

[Leox]

Vedr в сообщении #442699 писал(а):

Имеется $p$ целых неотрицательных чисел таких, что $u_1+2u_2+...+pu_p=x$, причем, все $u \le k$, k, p - натуральные, x - целое неотрицательное. Требуется, зная $x, k, p$, определить количество комбинаций чисел $u_1+...+pu_p$, которые бы в указанной сумме давали $x$
Пример для случая $p = 3, x = 4, k = 6$:
$u_3 = 1, u_2 = 0, u_1 = 1$
$u_3 = 0, u_2 = 0, u_1 = 4$
$u_3 = 0, u_2 = 1, u_1 = 2$
$u_3 = 0, u_2 = 2, u_1 = 0$
Всего 4 комбинации.

Если $k \geq x$ то залача решается при помощи производящих функций. Для указанного примера количество комбинаций равно коеффициенту при $z^4$ разложения в ряд дроби

$$ {\frac {1}{ \left( 1-z \right) \left( 1-{z}^{2} \right) \left( 1-{z} ^{3} \right) }}=1+z+2\,{z}^{2}+3\,{z}^{3}+{\bf 4}\,{z}^{4}+O \left( {z}^{5} \right) $$

Можно и явную формулу состряпать, для етого же примера - количество решений уравнения $u_1+2 u_2+3 u_2 =n $ равно
\begin{gather*} {\frac {17}{172800}}\,{n}^{5}+{\frac {17}{7680}}\,{n}^{4}+{\frac {1033 }{51840}}\,{n}^{3}+ \left( {\frac {1}{512}}\,\cos \left( \pi \,n \right) +{\frac {689}{7680}} \right) {n}^{2}+{\frac {4}{243}}\,\sqrt {3}\sin \left( 2/3\,\pi \,n \right) +2/9\,\cos \left( 2/3\,\pi \,n \right) -3/16\,\sin \left( 1/2\,\pi \,n \right) +\\+{\frac {15}{64}}\, \cos \left( 1/2\,\pi \,n \right) +{\frac {1}{50}}\,\sqrt {5}\cos \left( 4/5\,\pi \,n \right) +{\frac {3}{50}}\,\cos \left( 4/5\,\pi \, n \right) -{\frac {1}{500}}\,\sqrt {5}\sqrt {10-2\,\sqrt {5}}\sin \left( 4/5\,\pi \,n \right) -{\frac {1}{100}}\,\sqrt {10-2\,\sqrt {5} }\sin \left( 4/5\,\pi \,n \right) +\\+{\frac {141}{1024}}\,\cos \left( \pi \,n \right) -{\frac {1}{100}}\,\sqrt {10+2\,\sqrt {5}}\sin \left( 2/5\,\pi \,n \right) +{\frac {1}{500}}\,\sqrt {5}\sqrt {10+2\,\sqrt {5 }}\sin \left( 2/5\,\pi \,n \right) -{\frac {1}{50}}\,\sqrt {5}\cos \left( 2/5\,\pi \,n \right) +{\frac {3}{50}}\,\cos \left( 2/5\,\pi \, n \right) + \\+\left( {\frac {4}{81}}\,\cos \left( 2/3\,\pi \,n \right) - {\frac {3}{64}}\,\sin \left( 1/2\,\pi \,n \right) +{\frac {3}{64}}\, \cos \left( 1/2\,\pi \,n \right) +{\frac {9}{512}}\,\cos \left( \pi \, n \right) +{\frac {46667}{207360}} \right) n+{\frac {65827}{230400}} \end{gather*}

[Sonic86]

(Оффтоп)

Leox, неужели Вы это ручками набирали? Кстати, для $p=3$ можно и попроще формулу замутить через целые части.

Интересно, программистам такое дают или нет? Если да, то как они такое считают?

[Vedr]

Спасибо за разъяснение

[Leox]

(Оффтоп)

не ручками, maple помог.
Да, возможно через целые части и попроще формула будет.

пограммисты решают перебором, насколько я знаю.

[Vedr]

а откуда следует условие $u_j \ge 1 $?

[Casaubon]

Производящей функцией можно воспользоваться и для случая, когда наложено ограничение $u_i\leqslant k$.
Для примера c тремя слагаемыми:

$$ f(z)=\frac{\left(1-z^{k+1}\right)\left(1-z^{2(k+1)}\right)\left(1-z^{3(k+1)}\right)}{(1-z) \left(1-z^2\right) \left(1-z^3\right)} $$

Тогда количество вариантов для данного $n$ будет равно

$$ P(n)-P(n-(k+1))-P(n-2(k+1))+P(n-4(k+1))+P(n-5(k+1))-P(n-6(k+1)) $$

где $P(n)$ --- количество вариантов для случая без ограничения

$$ P(n)= \frac1{72} \left(6 n (n+6)+9 (-1)^n+16 \cos \left(\frac{2 \pi n}3\right)+47\right) $$

(для $n<0$ положим $P=0$).
Такое ощущение, что исходная постановка задачи и предполагала использование производящих функций.

[Vedr]

Увы, но количество слагаемых строго фиксировано величиной $p$, не зависящей от $k$. Эта задача всплыла при возведении полинома степени $p$ в степень $k$.

[Leox]

Casaubon в сообщении #442855 писал(а):

$$ P(n)= \frac1{72} \left(6 n (n+6)+9 (-1)^n+16 \cos \left(\frac{2 \pi n}3\right)+47\right) $$

(для $n<0$ положим $P=0$).

Интересная формула, намного проще моей. Из каких соображений получается?

[Sonic86]

Vedr писал(а):

а откуда следует условие $u_j \ge 1 $?

Блин, это меня глюкнуло. Соответственно $a_j = \frac{x}{j+1}$ и дальше переписать. Но на итоговую оценку не повлияет