неупорядоченные разбиения

[Ward]

Здравствуйте, уважаемые друзья!

Найти число неупорядоченных разбиений числа $n$ на $k$ слагаемых, т.е. $n=x_1+x_2+...+x_k,$ причем $1\leqslant n\leqslant 26,$ $1\leqslant k\leqslant 7$ и $\forall i: \quad 1\leqslant x_i\leqslant 4$,
Моя попытка решения: Я полагаю, что надо сделать здесь замену $x_i-1=y_i$ и тогда задача сведется к такой:
$n-k=y_1+y_2+...+y_k,$ причем $0\leqslant y_i\leqslant 3$, $1\leqslant n\leqslant 26$ и $1\leqslant k\leqslant 7$
А дальше как делать я пока, что не понимаю.
Есть такая мысль - использовать формулу включений-исключений и функцию разбиений $p(n)$

[Sonic86]

Можно попробовать группировать игреки с равными значениями, раз уж $y_i\leqslant 3$ - так мало. Группировки превращаются обратно в неупорядоченные суммы с помощью биномиальных коэффициентов. Потом конечный перебор.

Можно попробовать поискать 7-имерные объемы.

[Ward]

Sonic86 в сообщении #936262 писал(а):

Можно попробовать группировать игреки с равными значениями..

Можете тут пояснить, что Вы имеете ввиду? Не понял Вас

[Sonic86]

$20=1+2+0+3+0+0+2+3+1+1+1+0+3+3 = \underbrace{0+0+0+0}_{4\text{ шт.}}+\underbrace{1+1+1+1}_{4\text{ шт.}}+\underbrace{2+2}_{2\text{ шт.}}+\underbrace{3+3+3+3}_{4\text{ шт.}} = $
$=0\cdot 4 + 1\cdot 4+2\cdot 2 + 3\cdot 4$
Если сложно, то можете сначала ограничиться случаем $y_i\leqslant 1$. Потом перейдите к $y_i \leqslant 2$.

[Ward]

Допустим, что $y_i\leqslant 1$. Пусть нулей в разбиении $a$ штук, а единиц $b$ штук. Тогда получаем следующие уравнения: $a\cdot 0+b\cdot 1=n-k$ и $a+b=k$. Верно?
Но тут-то какая неувязочка...
Как я понимаю ни при всех $n$ и $k$ это возможно.

[Sonic86]

Ward в сообщении #936272 писал(а):

Допустим, что $y_i\leqslant 1$. Пусть нулей в разбиении $a$ штук, а единиц $b$ штук. Тогда получаем следующие уравнения: $a\cdot 0+b\cdot 1=n-k$ и $a+b=k$. Верно?

Ага. Теперь вопрос: какие значения пробегают $a,b$? Найдите в общем число решений.

Ward в сообщении #936272 писал(а):

Но тут-то какая неувязочка...
Как я понимаю ни при всех $n$ и $k$ это возможно.

Не при всех. Но Вам же надо задачу решить. Для пущей решаемости пока считайте, что $n,k$ подходящие. С неподходящими вариантами потом разберетесь. Правая часть пока неважна, так что сделайте замену $n_1=n-k$.

[Ward]

Уважаемый Sonic86
Имеем два уравнения $a\cdot 0+b\cdot 1=n_1$ и $a+b=k$.
Понятно, что при $n_1>k$ нет решений. Поэтому $n_1\leqslant k$
Понятно, что $a$ меняется в пределах от $0$ до $k-1$
Если $a=0$, то $b=k=n_1$
Если $a=1$, то $b=k-1=n_1$
....
Если $a=k-1$, то $b=1=n_1$
Что-то в таком роде получается

[Sonic86]

Ward в сообщении #936288 писал(а):

Что-то в таком роде получается

Да (правда $n$ if-ов можно заменить на одну лаконичную строку).
Вы свели исходное уравнение к вспомогательному, вспомогательное решили. Ну теперь решайте исходное уравнение. У меня в этом пункте спрашивать совершенно нечего.

[Ward]

Исходное это какое?
Когда все $y_i\leqslant 3$?

-- 26.11.2014, 14:13 --

Все равно случай когда $0 \leqslant y_i\leqslant 3$ рассматривается очень тяжело.
Будет уравнение $a\cdot 0+b\cdot 1+c\cdot 2+d\cdot 4=n$ и $a+b+c+d=k$
И как с такой махиной работать?

[12d3]

Касательно $y_i \le 1$. У вас два уравнения с двумя неизвестными. Их решение будет $a=k-n_1,\,\,b=n_1$. Так как $a$ и $b$ неотрицательны, появляются следующие неравенства $k \ge n_1 \ge 0$. Это значит, что при выполнении этих неравенств у вас есть ровно один способ разбиения на нули и единицы, а если хотя б одно из неравенств не выполняется, то ноль способов.
Это можно обозначить как $F_1(n_1,k)=\begin{cases}1,& k \ge n_1 \ge 0 \\ 0,& other \, cases\end{cases}$ Это функция, выражающая количество разбиений на нули и единицы в зависимости от $n_1$ и $k$.
Теперь рассмотрим игреки, не большие двух. Пусть у нас ровно $c$ двоек. Остальных чисел должно быть $k-c$ штук и в сумме они должны давать $n_1-2c$. Эти остальные числа - это нули и единицы. Количество таких разбиений на нули и единицы будет $F_1(n_1-2c,k-c)$. Теперь нужно эти количества просуммировать по всем возможным значениям $c$. То есть, если ввести аналогичную функцию $F_2(n_1,k)$, выражающую количество разбиений на нули, единицы и двойки, то $F_2(n_1,k) = \sum \limits_{c\ge 0}F_1(n_1-2c,k-c)$. Вот эту сумму вам надо посчитать. Как посчитаете, перейдем к числам, не большим трех.

[Sonic86]

Ward в сообщении #936297 писал(а):

Исходное это какое?
Когда все $y_i\leqslant 3$?

Да

Ward в сообщении #936297 писал(а):

Все равно случай когда $0 \leqslant y_i\leqslant 3$ рассматривается очень тяжело.
Будет уравнение $a\cdot 0+b\cdot 1+c\cdot 2+d\cdot 4=n$ и $a+b+c+d=k$
И как с такой махиной работать?

Ну все равно 4 переменные - это меньше, чем $k$
С линейными диофантовыми уравнениями работаем как обычно. Переменная $a$ легко исключается из рассмотрения - остается 3 переменные - еще легче.

[Ward]

12d3
Я правильно понимаю, что в случае $y_i\leqslant 1$ Вы вначале фиксируете $n_1$ и $k$?

[12d3]

Ward в сообщении #936327 писал(а):

12d3
Я правильно понимаю, что в случае $y_i\leqslant 1$ Вы фиксируете $n$ и $k$?

Да.

[Ward]

Уважаемый 12d3
как вообще посчитать такую сумму? что-то ничего в голову не лезет

[Ward]

Думал все это время, но никаких результатов.