Комбинаторика - разбиение на заданное число непустых частей

[vnukovinho]

Помогите люди плз. Необходимо подсчитать число разбиений натурального числа N ,с заданным числом частей разбиения K. НО части разбиения не должны быть нулевыми.
Почитал вот эту тему topic9682.html , сам допереть не могу.
Также как в той теме можно решить про количество композиций числа с заданным количеством компонент, без нулей.
Но мне нужны разбиения...

[maxal]

vnukovinho в сообщении #211184 писал(а):

Необходимо подсчитать число разбиений натурального числа N ,с заданным числом частей разбиения K.

Простой явной формулы нет, но количество таких разбиений можно выразить через функцию разбиений $q$, для которой существует простая рекуррентная формула, таким образом:

$$q(N,K) - q(N,K-1)$$

[vnukovinho]

[quote="maxal"][/quote]
Спасибо за информацию, но немного не то.
Мне необходимо получить число разбиений с НЕнулевыми частями, а в примере
по Вашей ссылке, например, q(5,3)=5 хотя в действительности оно равно 2.
Это получается из-за того, что учитываются разбиения (5), (4,1) и (3,2).
Мне удалось получить выражение для числа композиций, с заданным числом слагаемых, без нулевых компонент.
$C_{n-1}^{k-1}$ - количество композиций числа n с к частями.
К примеру (5,3)=6. Вот они все: (3,1,1) (2,2,1) (2,1,2) (1,3,1) (1,2,2) (1,1,3).
А (3,2,0) не учитывается, так как фактически состоит из двух частей.

[ewert]

vnukovinho в сообщении #211184 писал(а):

Необходимо подсчитать число разбиений натурального числа N ,с заданным числом частей разбиения K. НО части разбиения не должны быть нулевыми.

Есть гипотеза: Вам нужно разбить число $n$ на $k$ слагаемых с учётом порядка, причём все слагаемые ненулевые.

Тогда всё просто: $C_{n-1}^{k-1}.$

Если же допускаются и нулевые слагаемые, то несколько сложнее, но ненамного: $C_{n+k-1}^{k-1}.$

Кстати, в ветке, которую Вы упомянули, что-то на этот счёт говорится; правда, внимательно я не читал.

[vnukovinho]

ewert писал(а):

слагаемых с учётом порядка

Порядок не важен. Это разбиение. В композиции порядок важен, для неё действительно верна первая формула,Вами написанная.
Это количество(искомое), значительно меньше $C_{n-1}^{k-1}.$.
Например (10,5) композиций таких 126, а разбиений всего 7 или
(5,3) где композиций 6, а разбиения всего 2.

[Yu_K]

Если не нужны нулевые значения - тогда сразу поставьте по 1 в каждую - затем разбейте остаток на все ячейки http://www.nsu.ru/phorum/read.php?f=6&i=17575&t=17575.

И формула включения/исключения может помочь.

[vnukovinho]

Yu_K писал(а):

Если не нужны нулевые значения - тогда сразу поставьте по 1 в каждую - затем разбейте остаток на все ячейки http://www.nsu.ru/phorum/read.php?f=6&i=17575&t=17575.

И формула включения/исключения может помочь.

k единиц уйдёт на заполнение единицами, а дальше считаем количество
разбиений/композиций для n-k на k частей. Почти генеально. Буду пробовать.
Надеюсь до формулы вкл./выкл. не дойдёт, только тервера еще не хватает в
работе.

[maxal]

vnukovinho в сообщении #211397 писал(а):

Мне необходимо получить число разбиений с НЕнулевыми частями, а в примере
по Вашей ссылке, например, q(5,3)=5 хотя в действительности оно равно 2.

В разбиениях части всегда ненулевые. А вас интересует число $q(N,K)-q(N,K-1)$.
Для $N=5$ и $K=3$ получается:

$$q(5,3)-q(5,2)=5-3=2.$$