Математический форум 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; У меня получилось то же значение для [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/ |