2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 неупорядоченные разбиения
Сообщение26.11.2014, 10:35 
Здравствуйте, уважаемые друзья!

Найти число неупорядоченных разбиений числа $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)$

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

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

 
 
 
 Re: неупорядоченные разбиения
Сообщение26.11.2014, 11:08 
Sonic86 в сообщении #936262 писал(а):
Можно попробовать группировать игреки с равными значениями..
Можете тут пояснить, что Вы имеете ввиду? Не понял Вас :-(

 
 
 
 Re: неупорядоченные разбиения
Сообщение26.11.2014, 11:15 
$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$.

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

 
 
 
 Re: неупорядоченные разбиения
Сообщение26.11.2014, 12:22 
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$.

 
 
 
 Re: неупорядоченные разбиения
Сообщение26.11.2014, 12:39 
Уважаемый 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$
Что-то в таком роде получается :?

 
 
 
 Re: неупорядоченные разбиения
Сообщение26.11.2014, 12:56 
Ward в сообщении #936288 писал(а):
Что-то в таком роде получается :?

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

 
 
 
 Re: неупорядоченные разбиения
Сообщение26.11.2014, 13:03 
Исходное это какое?
Когда все $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$
И как с такой махиной работать? :facepalm:

 
 
 
 Re: неупорядоченные разбиения
Сообщение26.11.2014, 13:28 
Касательно $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)$. Вот эту сумму вам надо посчитать. Как посчитаете, перейдем к числам, не большим трех.

 
 
 
 Re: неупорядоченные разбиения
Сообщение26.11.2014, 13:29 
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$
И как с такой махиной работать? :facepalm:
Ну все равно 4 переменные - это меньше, чем $k$ :roll:
С линейными диофантовыми уравнениями работаем как обычно. Переменная $a$ легко исключается из рассмотрения - остается 3 переменные - еще легче.

 
 
 
 Re: неупорядоченные разбиения
Сообщение26.11.2014, 14:23 
12d3
Я правильно понимаю, что в случае $y_i\leqslant 1$ Вы вначале фиксируете $n_1$ и $k$?

 
 
 
 Re: неупорядоченные разбиения
Сообщение26.11.2014, 14:23 
Ward в сообщении #936327 писал(а):
12d3
Я правильно понимаю, что в случае $y_i\leqslant 1$ Вы фиксируете $n$ и $k$?
Да.

 
 
 
 Re: неупорядоченные разбиения
Сообщение26.11.2014, 14:53 
Уважаемый 12d3
как вообще посчитать такую сумму? что-то ничего в голову не лезет :-(

 
 
 
 Re: неупорядоченные разбиения
Сообщение26.11.2014, 16:46 
Думал все это время, но никаких результатов. :oops:

 
 
 [ Сообщений: 22 ]  На страницу 1, 2  След.


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