Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 8 ] 
Автор Сообщение
 Заголовок сообщения: Разбиения натурального N на k частей
СообщениеДобавлено: 02 июн 2017, 06:11 
Не в сети
Начинающий
Зарегистрирован:
30 окт 2015, 03:45
Сообщений: 30
Cпасибо сказано: 2
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 1

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Разбиения натурального N на k частей
СообщениеДобавлено: 02 июн 2017, 08:22 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 10:11
Сообщений: 3130
Cпасибо сказано: 53
Спасибо получено:
686 раз в 619 сообщениях
Очков репутации: 199

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Разбиения натурального N на k частей
СообщениеДобавлено: 02 июн 2017, 14:25 
Не в сети
Beautiful Mind
Зарегистрирован:
06 июн 2013, 17:17
Сообщений: 1119
Cпасибо сказано: 59
Спасибо получено:
320 раз в 304 сообщениях
Очков репутации: 97

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Разбиения натурального N на k частей
СообщениеДобавлено: 02 июн 2017, 17:11 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
03 апр 2012, 04:09
Сообщений: 3980
Cпасибо сказано: 111
Спасибо получено:
1768 раз в 1473 сообщениях
Очков репутации: 370

Добавить очки репутацииУменьшить очки репутации
В 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.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Human "Спасибо" сказали:
3D Homer
 Заголовок сообщения: Re: Разбиения натурального N на k частей
СообщениеДобавлено: 02 июн 2017, 17:33 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
03 апр 2012, 04:09
Сообщений: 3980
Cпасибо сказано: 111
Спасибо получено:
1768 раз в 1473 сообщениях
Очков репутации: 370

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

и все. :)

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Разбиения натурального N на k частей
СообщениеДобавлено: 02 июн 2017, 18:19 
Не в сети
Beautiful Mind
Зарегистрирован:
06 июн 2013, 17:17
Сообщений: 1119
Cпасибо сказано: 59
Спасибо получено:
320 раз в 304 сообщениях
Очков репутации: 97

Добавить очки репутацииУменьшить очки репутации
С помощью рекуррентного отношения можно посчитать результат в любом языке программирования, где есть массивы и арифметика с целыми числами произвольной точности (но не наивной рекурсией, а с помощью мемоизации). Вот код на 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].

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Разбиения натурального N на k частей
СообщениеДобавлено: 02 июн 2017, 22:58 
В сети
Оракул
Аватара пользователя
Зарегистрирован:
24 ноя 2016, 22:32
Сообщений: 785
Откуда: Махачкала
Cпасибо сказано: 42
Спасибо получено:
120 раз в 114 сообщениях
Очков репутации: 20

Добавить очки репутацииУменьшить очки репутации
Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Разбиения натурального N на k частей
СообщениеДобавлено: 02 июн 2017, 23:08 
Не в сети
Начинающий
Зарегистрирован:
30 окт 2015, 03:45
Сообщений: 30
Cпасибо сказано: 2
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Огромное спасибо!!

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Исследовать ряд разбиения пространства

в форуме Ряды

vegin

1

86

15 ноя 2016, 01:11

Разбиения конечных множеств

в форуме Дискретная математика, Теория множеств и Логика

Free Dreamer

2

274

04 апр 2013, 23:45

Точки разбиения в интеграле методом Ньютона

в форуме Интегральное исчисление

dserp18

0

220

22 июн 2014, 01:53

Выаести формулу конечного разбиения множества

в форуме Дискретная математика, Теория множеств и Логика

Fiesta18

2

168

06 янв 2013, 16:46

Объем шара и его частей

в форуме Геометрия

Olga1975

0

66

30 мар 2016, 22:42

Площадь сферы и ее частей

в форуме Геометрия

ilonka

2

330

17 янв 2014, 17:53

Объем шара и его частей

в форуме Геометрия

Olga1975

1

102

30 мар 2016, 22:27

Разделить функцию на n равных по площади частей

в форуме Интегральное исчисление

draft3

4

146

27 авг 2015, 14:16

На сколько частей и как разломать отрезок данной длины

в форуме Задачи со школьных и студенческих олимпиад

Xenia1996

5

535

03 ноя 2012, 20:41

Найти длины тех частей отрезка, которые лежат вне окружности

в форуме Геометрия

darmenden

1

346

28 май 2012, 11:58


Часовой пояс: UTC + 4 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 6


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved