Mam do rozwiązania zadanie o treści:
Liczbę naturalną \(\displaystyle{ C}\) można przedstawić jako sumę parami różnych liczb naturalnych. Na przykład jeśli \(\displaystyle{ C = 6}\), to możemy \(\displaystyle{ C}\) przedstawić na cztery sposoby:
\(\displaystyle{ 1 + 2 + 3\\
1 + 5\\
2 + 4\\
6}\)
Skonstruuj algorytm wyczerpujący z nawrotami, generujący wszystkie podziały podanej liczby naturalnej \(\displaystyle{ C}\).
Algorytm napisałem, jednak chciałbym sprawdzić jego poprawność. Dlatego potrzebuje jakiegoś wzoru, który pozwoli policzyć wszystkie takie podziały.
Niestety nie udało mi się nic takiego znaleźć, a sam też takiego wzoru wyprowadzić nie potrafię.
Bardzo proszę o pomoc.
Podział liczby naturalnej na sumę parami różnych liczb.
Podział liczby naturalnej na sumę parami różnych liczb.
Ostatnio zmieniony 7 maja 2015, o 20:24 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
-
Medea 2
- Użytkownik
- Posty: 2491
- Rejestracja: 30 lis 2014, o 11:03
- Płeć: Kobieta
- Podziękował: 23 razy
- Pomógł: 479 razy
Podział liczby naturalnej na sumę parami różnych liczb.
Wzoru nie ma i raczej nie będzie, ale są funkcje tworzące:
\(\displaystyle{ \prod_{m=1}^\infty 1 + x^m = \left[ \prod_{m=0}^\infty 1 - x^{2m+1} \right ]^{-1}= \sum_{k=0}^\infty \prod_{i=1}^k \frac{x^i}{1-x^i}.}\)
Jak chcesz sprawdzić poprawność algorytmu, policz \(\displaystyle{ f(50) = 3658}\) albo \(\displaystyle{ f(100) = 444793}\). Szybko rośnie, bo \(\displaystyle{ f(1000)}\) to już \(\displaystyle{ 8635565795744155161506}\)
\(\displaystyle{ \prod_{m=1}^\infty 1 + x^m = \left[ \prod_{m=0}^\infty 1 - x^{2m+1} \right ]^{-1}= \sum_{k=0}^\infty \prod_{i=1}^k \frac{x^i}{1-x^i}.}\)
Jak chcesz sprawdzić poprawność algorytmu, policz \(\displaystyle{ f(50) = 3658}\) albo \(\displaystyle{ f(100) = 444793}\). Szybko rośnie, bo \(\displaystyle{ f(1000)}\) to już \(\displaystyle{ 8635565795744155161506}\)
Podział liczby naturalnej na sumę parami różnych liczb.
Mogę prosić o objaśnienie tego wzoru? Bo nie bardzo rozumiem szczerze.