Узнать количество комбинаций
Как можно узнать количество упорядоченных троек чисел (a, b, c) таких что
- a, b, c ∈ [0, N]
- a + b + c = N
И также интересно решение для векторов произвольной размерности k
Ответы (1 шт):
Автор решения: MBo
→ Ссылка
Есть такая рекуррентная формула для числа разбиений n на ровно k частей:
P(n, k) = P(n-1, k-1) + P(n-k, k)
На Питоне:
import functools
@functools.lru_cache(1000)
def numpartitionsintokparts(n, k):
if n < k:
return 0
if n == k:
return 1
if k == 1:
return 1
return numpartitionsintokparts(n-1, k-1) + numpartitionsintokparts(n-k, k)
print(numpartitionsintokparts(120, 3))
>>> 1200
Для конкретного случая k=3 последовательность вызовов сводится к сумме
Sum((n-1-3*i)//2) + 1 if n%3==0
и
def num3(n):
res = 1 if n%3==0 else 0
i = n - 1
while i >= 3:
res += i//2
i -= 3
return res
В принципе, Sum есть сложение сумм двух арифметических (для четных и нечетных) прогрессий, так что можно и формулу получить.
upd: уже получили:
def num33(n):
return (n*n+4)//12