Помогите с конечной суммой

[nwbie]

Всем привет и с Новым Годом. Есть частичная (конечная) сумма, и я совсем не знаю, как к ней подобраться. Ее проще всего выразить рекурсивно:
$F_0 = 1; F_{k+1} = \sum\limits_{x_k = 1}^{p - 1 - x_{k+1}} F_k$,
где p - параметр и $k_{\max} = p$, а $F_p$ - и есть та самая сумма.
Если это по сути элементарно - подскажите, куда копать и что для решения надо бы знать. Заранее спасибо.

[provincialka]

А что такое $x_k$?

[nwbie]

$x_k$ - целое, лежащее в пределах от 1 до $p-1-x_{k-1}$.
В целом сумма имеет вид $\sum\limits_{\{x_k = 1\}_{k=1}^p}^{\{x_k = p - 1 - x_{k-1}\}_{k=1}^p} 1$ (что и мне самому, хм, кажется довольно странным).

[INGELRII]

Что вы хотите получить-то? Общую формулу для всех $F$, или только для $F_{k_\max}$, или еще чего?
Вообще, попробуйте сначала рассмотреть простые частные случаи. Возьмите $p=1, 2, 3$ и посмотрите, чего там происходит с $F$.

[iifat]

Не припоминаю такой записи. Может, имеется в виду набор переменных $x_1,\dots,x_p$, начинающиёся с $1,\dots,1$ и $x_k\le p-1-x_{k-1}$... Но для $x_1$ формула неприменима — он докуда изменяется?

[svv]

nwbie
Ваши суммы пока записаны с нарушением правил и не имеют смысла, причем невозможно догадаться, что Вы имеете в виду.

Давайте так сделаем. Пусть $p=5$. Напишите $F_0, F_1, F_2$ и ещё несколько (чем больше, тем лучше) без всяких $x_k$ и знаков суммы.

[nwbie]

INGELRII
Второе ($F_p$).

iifat
Да, именно такой набор переменных я и имел в виду.
Признаю, что условие неверное. Чтобы суммы вообще имели смысл, нужно, чтобы индекс k изменялся в пределах от 0 до p. Тогда $F_0 \equiv F_0 (x_0) = \operatorname{const}$, и $ F_1 (x_1) = \sum\limits_{x_0=1}^{p-1-x_1} F_0 = p-1-x_1 $.
$ F_k $ - полиномы от $x_k$:
$ F_2 = \frac{1}{2} ( p(p-1) - x_2 (x_2 -1)) $,
$F_3 = \frac{p}{6} \left[ 1 + p(2p-3) \right] - x_3 (x_3-1) (x_3 +1 -3p) $.

svv
Хорошо, пусть $p=5$. Тогда
$F_1 = 4 - x_1$,
$F_2 = 6 - \frac{1}{2}(x_2 (x_2 -1))$,
$F_3 = 14 - x_3 (x_3 -1) (x_3 - 11)$
$F_4 = -\frac{1}{4} (x_4 - 4) (x_4^3 + 2 x_4^2 -65 x_4 + 206)$

[svv]

Понятно. Это так обозначается:
$F_0(x)=1$
$F_{k+1}(x)=\sum\limits_{j=1}^{p-1-x} F_k(j)$
Вам может показаться, что я выбросил что-то очень важное, но на самом деле нет.

[Sonic86]

svv в сообщении #808557 писал(а):

$F_0(x)=1$
$F_{k+1}(x)=\sum\limits_{j=1}^{p-1-x} F_k(j)$

В такой формулировке могу посоветовать выражать многочлены не через базис $\{x^k\}$, а через базис $\{x^{\underline{k}}\}$, где $x^{\underline{k}}=x(x-1)...(x-k+1)$. Это удобно для суммирования:

$$\sum\limits_{a\leqslant j<b}j^{\underline{k}}=\frac{j^{\underline{k+1}}}{k+1}\bigg|_{a}^{b}=\frac{1}{k+1}(b^{\underline{k+1}}-a^{\underline{k+1}})$$

В крайнем случае, если нужно, можете вернуться к обычному базису раскрытием скобок через числа Стирлинга.
Правда, я пока общую формулу не вижу. Могу только сказать, что выражения для $F_{2k}$ и $F_{2k+1}$ будут довольно разные (и слагаемых как-то пока дофига - $2^k$). Зато у меня в суммах получаются показатели только одной четности с $k$.

(Оффтоп)

Перечитал еще раз. Возникло ощущение, что все-таки в формулировке задания есть какая-то ошибка.

[svv]

Зафиксируем $p$. Зафиксируем целое $x$, $1\leqslant x\leqslant p-2$.
Тогда элементы последовательности $a_k=F^{(p)}_k(x)$ удовлетворяют некоторой рекуррентной формуле. Эта формула определяется значением $p$, но не зависит от $x$. Например,
$p=4: a_k=a_{k-1}+a_{k-2}$
$p=5: a_k=2a_{k-1}+a_{k-2}-a_{k-3}$
$p=6: a_k=2a_{k-1}+3a_{k-2}-a_{k-3}-a_{k-4}$

Различные последовательности, удовлетворяющие таким формулам, есть в OEIS. В том числе точно такие, которые получаются при $x=1$, т.е. $F^{(p)}_k(1)$ для разных $p$:
A006356 (p=5), A006357 (p=6), A006358 (p=7)
Даже для $p=10$ есть! В OEIS сказано, что $F^{(p)}_k(1)$ — это число различных путей света при отражении от $p-2$ пластин, с количеством отражений $k$. А также количество дистрибутивных решеток.

Всё здорово, нет только общей формулы.

[svv]

Типа явная формула (для $p=5$, легко обобщается):
$\begin{bmatrix}F_k(1)\\F_k(2)\\F_k(3)\end{bmatrix}={\begin{bmatrix}0&0&1\\0&1&1\\1&1&1\end{bmatrix}}^k\begin{bmatrix}1\\1\\1\end{bmatrix}$