Математический форум Math Help Planet
http://mathhelpplanet.com/

Разбиения натурального N на k частей
http://mathhelpplanet.com/viewtopic.php?f=62&t=54795
Страница 1 из 1

Автор:  Volodislavir [ 02 июн 2017, 05:11 ]
Заголовок сообщения:  Разбиения натурального N на k частей

Собственно вопрос звучит так:
Как найти количество разбиений для натурального N на ровно k частей?
Рекурентная формула P(N,k) = P(N-1, k-1) + P(n-k, k) приводит к очень громоздким вычислениям.
Если существует общий способ, то где ознакомится?
Если не существует, то посчитать конкретное значение при N = 201 и k = 21
Может есть ресурс, где значения P(N,k) при малых N и k найдены?

Автор:  swan [ 02 июн 2017, 07:22 ]
Заголовок сообщения:  Re: Разбиения натурального N на k частей

Volodislavir писал(а):
Может есть ресурс, где значения P(N,k) при малых N и k найдены?

Есть такой ресурс. Microsoft Excel называется.

Автор:  3D Homer [ 02 июн 2017, 13:25 ]
Заголовок сообщения:  Re: Разбиения натурального N на k частей

Volodislavir писал(а):
Как найти количество разбиений для натурального N на ровно k частей?
Что значит разбить натуральное число на k частей?

Автор:  Human [ 02 июн 2017, 16:11 ]
Заголовок сообщения:  Re: Разбиения натурального N на k частей

В Wolfram Mathematica есть функция
IntegerPartitions[n, {k}]

которая вычисляет эти числа, однако мой ноут безнадежно завис в попытках посчитать эту функцию при [math]n=201,\ k=21[/math], а в wolframalpha.com эта функция не работает. Но есть альтернативный подход!

По данной ссылке приведена производящая функция чисел [math]p(n,k)[/math], которой вполне можно воспользоваться. Выбираем нужное [math]k[/math], раскладываем соответствующую производящую функцию в ряд Маклорена и смотрим на коэффициент при [math]x^n[/math]. Слава богу, wolframalpha.com умеет раскладывать сложные функции в ряды.
Если [math]k=21[/math], то в wolframalpha.com вбиваем
series for x^(21)*(product 1/(1-x^i) for i=1 to 21) at x=0

и кликаем (около 7 раз) на "More terms" до тех пор, пока не появится член степени 201. Получаем: 110 075 207 481.

Автор:  Human [ 02 июн 2017, 16:33 ]
Заголовок сообщения:  Re: Разбиения натурального N на k частей

Оказывается, эта функция работает и в wolframalpha.com, только в измененном виде. Достаточно написать
partitions of 201 with 21 parts

и все. :)

Автор:  3D Homer [ 02 июн 2017, 17:19 ]
Заголовок сообщения:  Re: Разбиения натурального N на k частей

С помощью рекуррентного отношения можно посчитать результат в любом языке программирования, где есть массивы и арифметика с целыми числами произвольной точности (но не наивной рекурсией, а с помощью мемоизации). Вот код на Java.

import java.math.BigInteger;

public class Partitions {
public BigInteger[][] array = new BigInteger[25][250];

public Partitions() {
int k, n;

array[0][0] = BigInteger.ONE;

for (n = 1; n < array[0].length; n++)
array[0][n] = BigInteger.ZERO;

for (k = 1; k < array.length; k++) {
array[k][0] = BigInteger.ZERO;

for (n = 1; n <= k; n++)
array[k][n] = array[k-1][n-1];

for (n = k+1; n < array[k].length; n++)
array[k][n] = array[k-1][n-1].add(array[k][n-k]);
}
}

public static void main(String[] args) {
Partitions p = new Partitions();
System.out.printf("p_{%d}(%d) = %s%n", 21, 201, p.array[21][201].toString());
}
}

У меня получилось то же значение для [math]p_{21}{201}[/math].

Автор:  Student Studentovich [ 02 июн 2017, 21:58 ]
Заголовок сообщения:  Re: Разбиения натурального N на k частей

На здоровье!

Автор:  Volodislavir [ 02 июн 2017, 22:08 ]
Заголовок сообщения:  Re: Разбиения натурального N на k частей

Огромное спасибо!!

Страница 1 из 1 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/