Ilość kombinacji w zbiorze z warunkiem sumy

numerix · Post autor: **numerix** » 3 paź 2018, o 17:36

Witam.
Mam pewien zbiór liczb naturalnych \(\displaystyle{ A=\{1,2,3,...40\}.}\)
Potrzebuję metody zliczającej ilość kombinacji w tym zbiorze takich , że każda kombinacja (bez powtórzeń) będzie równać się pewnej sumie ( np \(\displaystyle{ 50}\)) Wtedy jedna z takich kombinacji to np : \(\displaystyle{ 5+7+8+14+16}\) .
Inaczej, gdyby suma wynosiła \(\displaystyle{ 15}\), to wówczas liczba kombinacji \(\displaystyle{ = 1}\).

Zordon · Post autor: **Zordon** » 3 paź 2018, o 21:43

Wzoru jawnego na liczbę takich kombinacji raczej nie uzyskasz, chyba, że dla jakichś konkretnych (małych) parametrów. Natomiast można napisać efektywny program który takie coś potrafi obliczyć, używając programowania dynamicznego.

arek1357 · Post autor: **arek1357** » 4 paź 2018, o 11:22

Na siłę można by cosik ugnieść korzystając z partycji z ograniczeniami:

\(\displaystyle{ x_{1}+x_{2}+...+x_{k}=50, 40 \ge x_{1}>x_{2}>...>x_{k} \ge 1}\)

\(\displaystyle{ 1 \le k \le 40}\)

Potem zliczasz ilości po k.

Można posłużyć się wielomianami...

Matematyka.pl