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}\).
Ilość kombinacji w zbiorze z warunkiem sumy
-
- Użytkownik
- Posty: 3
- Rejestracja: 28 wrz 2018, o 14:39
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 1 raz
Ilość kombinacji w zbiorze z warunkiem sumy
Ostatnio zmieniony 4 paź 2018, o 01:28 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .
Powód: Brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
Ilość kombinacji w zbiorze z warunkiem sumy
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
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Ilość kombinacji w zbiorze z warunkiem sumy
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...
\(\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...