Версия для печати темы

Автор: Navi1982 9.11.2007, 13:23

a1+a2+...+an=s

0 <= ai <= x
x >= 0
n >= 1
0 <= s <= s * n, естественно...

Нужно найти z - количество уникальных комбинаций для n терминов сложения, которые в сумме дают s. Любой из терминов может иметь значение от 0 до x - целые числа.

Я уже составил программу которая считает z, но методом перебора. А это долго... Очень долго! Хотя программа и дает возможность просмотра всех этих вариантов, но они мне не нужны. Нужно только их количество!

В результате простых анализов мне стало известно следующее:

1) z принимает максимум в случае когда s=x*n/2 (округлить до целого), когда же
s --> 0 или s --> s*n, то z --> 1. Меньше 1-цы быть не может.

2) обнаружил сходство с "триугольником Паскаля" (пирамида Паскаля), где одну сторону от вершины берем за s (где 0<=s<=x*n/2) а другую за n, а на пересечении получаем z. И такой же результат получаем в симетричном отражении s (когда x*n>=s>=x*n/2). Но есть маленькое НО! Когда s --> x*n/2, то z отклоняется от действительности. Т.е. почти до середины все ОК, а когда s близко к x*n/2 - отклонения. Догадываюсь почему так происходит, но незнаю ка объяснить. Могу сказать, что это связанно с ограничением задаваемым числом x.

Вопрос: Вообще выше поставленная задача выполнима или нет?

Плииз, помогите решить - очень нужно...

Автор: malk 22.11.2007, 13:36

Вам нужна аналитеческая формула для z=f(s,n,x)?
Сочуствую...
Посмотрите
http://ru.wikipedia.org/wiki/Разбиение_числа
http://www.research.att.com/~njas/sequences/A000041

Автор: Navi1982 25.11.2007, 21:45

да. Что-то вроде того...
...
Хмм... Любопытные ссылочки!
Хотя ответа в них не нашёл (возможно "пока"), но всеровно - большое СПАСИБО ! =)

А вот некоторые результаты для "z" при условии что:
n=3, x=9 (т.е. 0<=ai<=x), s=0..27 (т.е. для всех случаев в пределе 0<=s=n*x)
s=0, z=1
s=1, z=3
s=2, z=6
s=3, z=10
s=4, z=15
s=5, z=21
s=6, z=28
s=7, z=36
s=8, z=45
s=9, z=55
s=10, z=63
s=11, z=69
s=12, z=73
s=13, z=75
s=14, z=75
s=15, z=73
s=16, z=69
s=17, z=63
s=18, z=55
s=19, z=45
s=20, z=36
s=21, z=28
s=22, z=21
s=23, z=15
s=24, z=10
s=25, z=6
s=26, z=3
s=27, z=1

Автор: malk 27.11.2007, 22:29

Похоже у вас не разбиения, как я подумал, а композиции.
Вроде получается
sum(i=0..[s/(x+1)]){((-1)^i)*C(i,n)*C(n-1,s+n-ix-i-1)}

Автор: Navi1982 1.12.2007, 21:04

Прошу прощения... А в записи "C(i,n)" - что находится вверху и что внизу?
Например, я видел такие записи C_n^m , ну или из приведённой формулы как будет вернее записать:
так -> С_(n-1)^(s+n-ix-i-1)
или так -> С_(s+n-ix-i-1)^(n-1)
?
А запись "ix" - это произведение или индексация?
И если я правильно понял, то количество комбинаций (композиций?) будет равно:
z=sum(i=0..[s/(x+1)]){((-1)^i)*C(i,n)*C(n-1,s+n-ix-i-1)} ?

Заранее благодарен.

P.S.> Покамись нет времени проверить формулу, но на недельке попробую.

Автор: malk 2.12.2007, 1:40

1.C(i,n)=n!/(i!*(n-i)!)
2.ix произведение
3.Таково мое предположение.

При s,n>20 возможны ошибки в расчетах из-за переполнения,
будьте аккуратны.

Автор: Navi1982 2.12.2007, 11:32

А вот такую вещь "s/(x+1)" в какую сторону округлять?
Попробывал посчитать так:
s=13, n=3, x=9. Округляя s/(x+1) в меньшую сторону получил что

z = S_0 + S_1 = 105 - 63 = 42,

вместо того, чтобы получить z=75. Может где-то ошибся...

А можно где нибудь почитать про "композиции" и чтоб доступно было? смотрел на википедии - там тока про разбиения.

Автор: malk 2.12.2007, 19:36

В меньшую.
S_1=(-1)*C(1,3)*C(2,13+3-9-1-1)=-3*C(2,5)=-30;

Автор: Navi1982 2.12.2007, 20:51

Оу! Сорри... Вы правы! Я нашел где я ошибся... Ура! Огромное спасибо!