Число разбиений n на части заданного размера

[maximkarimov]

Известна ли формула для числа разбиений $n$ на части заданного размера?
Например сколько разбиений 10 содержат 1 и 3?

P.S. Мне удалось найти только формулу разбиения $n$ на части, не превышающие $m$.

[kotenok gav]

maximkarimov в сообщении #1495825 писал(а):

сколько разбиений 10 содержат 1 и 3?

Очевидно, это равно количеству разбиений числа 6.

[maximkarimov]

Это общий случай? То есть находим разницу между $n$ и суммой длин всех заданных частей и для нее вычисляем число разбиений (по известной формуле)?

-- 09.12.2020, 14:37 --

kotenok gav в сообщении #1495839 писал(а):

maximkarimov в сообщении #1495825 писал(а):

сколько разбиений 10 содержат 1 и 3?

Очевидно, это равно количеству разбиений числа 6.

Я имел ввиду разбиения, которые содержат ТОЛЬКО 1 и 3. Таких разбиений для 10 ровно 3.
Сории за неаккуратность формулировки!)))

[maximkarimov]

Эмпирически нашел решение для случая разбиения $n$ на 1 и 3 - соответствующий ряд выглядит следующим образом (первый столбец - n, второй - число разбиений n, которые содержат только 1 и 3):
1 - 0
2 - 0
3 - 0
4 - 1
5 - 1
6 - 1
7 - 2
8 - 2
9 - 2
10 - 3
11 - 3
12 - 3
13 - 4
14 - 4
15 - 4
16 - 5
... ...

Любопытно можно ли вывести формулу в общем виде для произвольного набора частей, например: каково число разбиений n, которые содержат ТОЛЬКО числа 2, 4 и 7 (совместно)?

[kotenok gav]

maximkarimov в сообщении #1495853 писал(а):

1 - 0
2 - 0
3 - 0
4 - 1
5 - 1
6 - 1
7 - 2
8 - 2
9 - 2
10 - 3
11 - 3
12 - 3
13 - 4
14 - 4
15 - 4
16 - 5

$\lfloor\dfrac{n-1}3\rfloor$?

-- 09 дек 2020, 21:31 --

Для случая двух частей всё сводится к простому диафантовому уравнению.

[maximkarimov]

Да, только нужно взять округление вниз до ближайшего целого - floor.
Но общий случай (для произвольного набора частей) я даже представить не в состоянии!)))
К счастью, для моей текущей задачи он не нужен (мне достаточно разбиений n на только 1 и 3).
Спасибо.

[пианист]

Это же задача о размене?
Мне кажется, она должна быть хорошо изучена.
Я ею никогда не интересовался, но как-то встречал одно интересное решение в книжечке Кац, Улам "Математика и логика".

[Andrey A]

Решается алгоритмически https://dxdy.ru/post1241711.html (если это то что нужно).

[maximkarimov]

пианист в сообщении #1495858 писал(а):

Это же задача о размене?
Мне кажется, она должна быть хорошо изучена.
Я ею никогда не интересовался, но как-то встречал одно интересное решение в книжечке Кац, Улам "Математика и логика".

Да, похоже. Правда мне не просто надо было получить число разбиений n, которые содержат только 1 и 3, но и их список (в данном случае - пар), с указанием числа повторений для каждого элемента.
В итоге, соответствующую функцию реализовал так (на выходе - список пар):

Используется синтаксис Matlab M

function [res] = get1_3(n)
% получаем все разбиения n, которые содержат только 1 и 3 (совместно)
% (число единиц - первое, число троек - второе)
res=zeros(floor((n-1)/3), 2);
t=1;
for i=1:n-3
    if mod(n-i,3)==0
        res(t,1)=i;
        res(t,2)=(n-i)/3;
        t=t+1;
    end
end
end

Любопытно можно ли реализовать получение такого списка в общем виде, то есть функцию для двух входных аргументов - n и произвольного набора натуральных чисел?

[wrest]

maximkarimov
Раз можно написать функцию перечисляющую все разбиения, то можно написать и фильтр к ней. Вопрос только в оптимизации.

[maximkarimov]

Вы знаете каким темпом растет число разбиений n? Поэтому идея генерить все и фильтровать практического смысла не имеет.

-- 09.12.2020, 17:39 --

Andrey A в сообщении #1495859 писал(а):

Решается алгоритмически https://dxdy.ru/post1241711.html (если это то что нужно).

Нет, по Вашей ссылке речь идет об упорядоченных наборах (о числе композиций n).

[wrest]

maximkarimov в сообщении #1495868 писал(а):

Вы знаете каким темпом растет число разбиений n? Поэтому идея генерить все и фильтровать практического смысла не имеет.

Знаем... Ну, мало ли.

Вот вам oneliner для вашей задачи поиска количества разбиений из единиц и троек, на pari/gp

part13(n)=my (v=partitions(n,[1,3]),count=0);for(i=1,#v,if(Set(v[i])==[1,3],count++));count

Для $n=100$ считает ответ (равный 33) за 0 миллисекунд.
Для $n=1000$ считает ответ (равный 333) за 1 секунду.
Для $n=10000$ не считает -- не хватает стека в 3 гигабайта.

Вот универсальный oneliner для подсчета любого набора

part_n_s(n,s)=my (v=partitions(n),count=0);for(i=1,#v,if(Set(v[i])==s,count++));count

его вызывать так part_n_s(10,[1,3]), работает до $n<75$ при стеке в 3 гигабайта.

[maximkarimov]

На выходе число (скаляр) или список, с указанием числа повторений для каждого элемента?
В любом случае - есть к чему стремиться! И мне и онлайнеру!
Спасибо.

[wrest]

maximkarimov в сообщении #1495870 писал(а):

На выходе число (скаляр) или список,

Число (количество). Ну можно и список какой вы хотите, это немного удлиннит код.

maximkarimov в сообщении #1495870 писал(а):

И мне и онлайнеру

Не "онлайнеру", а "oneliner"-у - т.е. программе из одной строчки, не знаю русскоязычного аналога.

[maximkarimov]

Вот здесь http://zonakoda.ru/zadacha-o-razmene-tysyacherublyovoj-kupyury.html очень хорошо показана разница между различными способами решения похожей задачи.