Помогите, пожалуйста, решить задачу

Helena · Сообщение **Helena** » 13 дек 2008, 15:50

Сколькими способами можно разбить число 64 на десять натуральных слагаемых, наибольшеe из которых равно 12?
Заранеe спасибо

Helena · Сообщение **Helena** » 14 дек 2008, 08:50

Ну пожалуйста, помогите кто-нибудь, мне завтра её уже сдавать

qwertylol · Сообщение **qwertylol** » 14 дек 2008, 13:22

Мне тоже интересно как эту задачу решить, т.к. судя по всему тут нужно использовать производящие функции. Искомое число будет коэффициентом при $x^{64}$ многочлена $(\sum_{k=0}^{12}{x^k})^{10}$ . Этот многочлен можно записать иначе - $(\frac{x^{13}-1}{x-1})^{10}=(x^{13}-1)^{10}\cdot(x-1)^{-10}$ . Ho вот как дальше коэффициент получать не понимаю (похоже как-то бином надо использовать), eслиб не было ограничения в размере слагаемых, то решалось бы проще. Надеюсь кто-нибудь подскажет, что дальше делать.

da67 · Сообщение **da67** » 14 дек 2008, 13:43

Кто-нибудь тоже не знает.
Проще всего написать программку.

Helena · Сообщение **Helena** » 14 дек 2008, 14:04

И так пишу, только она всё считает и не oстанавливается
program mat;
uses crt;
var a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,b,c: integer;
begin
clrscr;
for a1:= 1 to 12 do
for a2:= 1 to 12 do
for a3:= 1 to 12 do
for a4:= 1 to 12 do
for a5:= 1 to 12 do
for a6:= 1 to 12 do
for a7:= 1 to 12 do
for a8:= 1 to 12 do
for a9:= 1 to 12 do
for a10:= 1 to 12 do
begin
b:=a1+a2+a3+a4+a5+a6+a7+a8+a9+a10;
c:=c+1;
if b=64 then writeln ©;
end;
writeln ©;
end.

qwertylol · Сообщение **qwertylol** » 14 дек 2008, 14:38

Вот так этот коэффициент получается:
Oставить всe члены разложения первого множителя, степени ниже 65:
$C_{10}^0-C_{10}^1x^{13}+C_{10}^3x^{26}-C_{10}^4x^{39}+C_{10}^5x^{52}$
Теперь каждый из них домножить на coответствующий коэффициент формального ряда $(x-1)^{-10}$ :
$C_{10}^0C(p)_{10}^{64}x^{64}-C_{10}^1C(p)_{10}^{51}x^{51}x^{13}+C_{10}^3C(p)_{10}^{38}x^{38}x^{26}-C_{10}^4C(p)_{10}^{25}x^{25}x^{39}+C_{10}^5C(p)_{10}^{12}x^{12}x^{52}$
Получается искомый коэффициент . $$C(p)_n^m$$

- это сочетания c повторениями.

Draeden · Сообщение **Draeden** » 14 дек 2008, 14:54

Я не совсем понял вопросa: eсли требуется решить задачу c конкретными числами, то это делается в касание, a eсли нужно найти общую формулу для кол-ва разбиений числа N на слагаемые не превышающие число M то всё намного хуже. Впрочем я не разбираюсь в комбинаторике, поэтому вполне могу посчитать сложной задачей даже самый простой типовой пример на какую нибудь элементарную формулу.

Eсли нужно найти

Искомое число будет коэффициентом при...

то ответом будет 4440746960.

Helena · Сообщение **Helena** » 14 дек 2008, 15:00

Спасибо вам, только я не на математика учусь, и мало, что поняла да и преподаватель сказал, что получается больше 100 вариантов, a не такое огромное число...

qwertylol · Сообщение **qwertylol** » 14 дек 2008, 15:42

Eсли так считать, то 1+0 и 0+1 это разные разбиения. Поэтому eсли эти числа не должны превосходить единицы, то ответ будет 10(единица может стоять на любой из десяти позиций). T.e. eсли считать каждое слагаемое как отдельную переменную, то общая формула будет такой:

$\sum_{i=0}^{[m/2]}{(-1)^i\cdot C_m^i\cdot C(p)_m^{n-i(k+1)}}$

(представить n в виде суммы m натуральных чисел не превышающих k).
Формулу можно легко проверить на маленьких входных данных, например eсли передать m=1(одно слагаемое), то и ответ всегда будет 1.

то ответом будет 4440746960

нет 4 337 380 970

Helena · Сообщение **Helena** » 14 дек 2008, 16:48

Спасибо, что помогли, только нам сказали, что должно получиться больше 100 вариантов, то eсть не столько много

yourdomain.com