Podział liczby 'n' na sumę 'k' nieujemnych składników (kol.)
-
- Użytkownik
- Posty: 6
- Rejestracja: 10 kwie 2016, o 09:53
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 2 razy
Podział liczby 'n' na sumę 'k' nieujemnych składników (kol.)
Problem: na ile sposobów można podzielić liczbę naturalną \(\displaystyle{ n}\) na sumę \(\displaystyle{ k}\) naturalnych (z zerem) składników, przy czym kolejność gra rolę. Np. dla \(\displaystyle{ n=2}\) i \(\displaystyle{ k=4}\) mamy rozwiązania:
\(\displaystyle{ 2+0+0+0\\
0+2+0+0\\
0+0+2+0\\
0+0+0+2\\
1+1+0+0\\
1+0+1+0\\
1+0+0+1\\
0+1+1+0\\
0+1+0+1\\
0+0+1+1}\)
czyli \(\displaystyle{ 10}\) możliwości
1) czy ten problem ma jaką inną nazwę?
2) czy jego rozwiązanie jest gdzieś na sieci (w książce) wytłumaczone
3) ew. jak go rozwiązać
Osiągnąłem równanie rekurencyjne (zakładając, że jednostkę wstawiam na pewną pozycję, a kolejne jednostki mogę wstawić tylko na pozycję nie wcześniej niż pierwszą):
\(\displaystyle{ f(k,n)=
\begin{cases}
1 &\text{dla } n=0 \\
1 &\text{dla } k=1 \\
\sum_{i=1}^{k} f(i,n-1) &\text{dla } k>1, n \neq 0
\end{cases}}\)
Które po rozwiązaniu dla trzech pierwszych \(\displaystyle{ k}\) wynosi:
\(\displaystyle{ \begin{array}{l}
f(1,n)=1 \\
f(2,n)=n+1 \\
f(3,n)= \frac{(n+1) \cdot (n+2)}{2} \\
\end{array}}\)
czy to możliwe, że ogólny wzór będzie (dla \(\displaystyle{ k>1}\)):
\(\displaystyle{ f(k,n)=\frac{(n+1) \cdot (n+2) \cdot ... \cdot (n+k-1)}{(k-1)!}}\)
\(\displaystyle{ 2+0+0+0\\
0+2+0+0\\
0+0+2+0\\
0+0+0+2\\
1+1+0+0\\
1+0+1+0\\
1+0+0+1\\
0+1+1+0\\
0+1+0+1\\
0+0+1+1}\)
czyli \(\displaystyle{ 10}\) możliwości
1) czy ten problem ma jaką inną nazwę?
2) czy jego rozwiązanie jest gdzieś na sieci (w książce) wytłumaczone
3) ew. jak go rozwiązać
Osiągnąłem równanie rekurencyjne (zakładając, że jednostkę wstawiam na pewną pozycję, a kolejne jednostki mogę wstawić tylko na pozycję nie wcześniej niż pierwszą):
\(\displaystyle{ f(k,n)=
\begin{cases}
1 &\text{dla } n=0 \\
1 &\text{dla } k=1 \\
\sum_{i=1}^{k} f(i,n-1) &\text{dla } k>1, n \neq 0
\end{cases}}\)
Które po rozwiązaniu dla trzech pierwszych \(\displaystyle{ k}\) wynosi:
\(\displaystyle{ \begin{array}{l}
f(1,n)=1 \\
f(2,n)=n+1 \\
f(3,n)= \frac{(n+1) \cdot (n+2)}{2} \\
\end{array}}\)
czy to możliwe, że ogólny wzór będzie (dla \(\displaystyle{ k>1}\)):
\(\displaystyle{ f(k,n)=\frac{(n+1) \cdot (n+2) \cdot ... \cdot (n+k-1)}{(k-1)!}}\)
Ostatnio zmieniony 11 kwie 2016, o 00:02 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych. Symbol mnożenia to \cdot.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych. Symbol mnożenia to \cdot.
-
- Użytkownik
- Posty: 1594
- Rejestracja: 16 maja 2013, o 17:56
- Płeć: Mężczyzna
- Lokalizacja: Trójmiasto
- Podziękował: 11 razy
- Pomógł: 247 razy
Podział liczby 'n' na sumę 'k' nieujemnych składników (kol.)
to jest zadanie na funkcje generujące / szeregi formalne
\(\displaystyle{ x_1 + x_2 + x_3 + x_4 = n}\)
wprowadzamy sobie roboczą zmienną \(\displaystyle{ z}\) i dla każdej zmiennej \(\displaystyle{ x_i}\) tworzymy jeden nawias, w którym mamy sumę zmiennych \(\displaystyle{ z}\) w potęgach, które reprezentują wartość możliwą dla danego \(\displaystyle{ x_i}\)
\(\displaystyle{ \left(z^0 + z^1 + z^2 + \ldots + z^n\right) \cdot \left(z^0 + z^1 + z^2 + \ldots + z^n\right) \cdot \ldots}\)
i tak nawias dla każdego \(\displaystyle{ x_i}\)
w przykładzie z dwójką:
\(\displaystyle{ \left(z^0 + z^1 + z^2\right)\left(z^0 + z^1 + z^2\right)\left(z^0 + z^1 + z^2\right)\left(z^0 + z^1 + z^2\right)}\)
bo rozkładamy na 4 składniki, z których każdy może mieć wartość od 0 do 2 i teraz co jest dla nas kluczowe, to jak przemnożymy to wszystko to wyjdzie nam:
\(\displaystyle{ \left(z^0 + z^1 + z^2\right)^4 = z^8 + 4z^7 + 10z^6 + 16z^5 + 19z^4 + 16z^3 + 10z^2 + 4z + 1}\)
i skoro suma ma być \(\displaystyle{ 2}\) to patrzymy na czynnik przy \(\displaystyle{ z^2}\), jest to \(\displaystyle{ 10}\) więc na 10 sposobów można to rozłożyć
wiadomo, że dla dużych liczb nikt nie będzie tego wszystkiego mnożył, więc na wyższym poziomie wystarczająco dokładną odpowiedzią jest zapis:
\(\displaystyle{ \left(z^0 + z^1 + z^2\right)^4 \quad \left[z^2\right]}\)
czyli ten nawias kwadratowy po prawej mówi, że odpowiedzią jest czynnik przy \(\displaystyle{ z^2}\) w rozwinięciu tej funkcji
\(\displaystyle{ x_1 + x_2 + x_3 + x_4 = n}\)
wprowadzamy sobie roboczą zmienną \(\displaystyle{ z}\) i dla każdej zmiennej \(\displaystyle{ x_i}\) tworzymy jeden nawias, w którym mamy sumę zmiennych \(\displaystyle{ z}\) w potęgach, które reprezentują wartość możliwą dla danego \(\displaystyle{ x_i}\)
\(\displaystyle{ \left(z^0 + z^1 + z^2 + \ldots + z^n\right) \cdot \left(z^0 + z^1 + z^2 + \ldots + z^n\right) \cdot \ldots}\)
i tak nawias dla każdego \(\displaystyle{ x_i}\)
w przykładzie z dwójką:
\(\displaystyle{ \left(z^0 + z^1 + z^2\right)\left(z^0 + z^1 + z^2\right)\left(z^0 + z^1 + z^2\right)\left(z^0 + z^1 + z^2\right)}\)
bo rozkładamy na 4 składniki, z których każdy może mieć wartość od 0 do 2 i teraz co jest dla nas kluczowe, to jak przemnożymy to wszystko to wyjdzie nam:
\(\displaystyle{ \left(z^0 + z^1 + z^2\right)^4 = z^8 + 4z^7 + 10z^6 + 16z^5 + 19z^4 + 16z^3 + 10z^2 + 4z + 1}\)
i skoro suma ma być \(\displaystyle{ 2}\) to patrzymy na czynnik przy \(\displaystyle{ z^2}\), jest to \(\displaystyle{ 10}\) więc na 10 sposobów można to rozłożyć
wiadomo, że dla dużych liczb nikt nie będzie tego wszystkiego mnożył, więc na wyższym poziomie wystarczająco dokładną odpowiedzią jest zapis:
\(\displaystyle{ \left(z^0 + z^1 + z^2\right)^4 \quad \left[z^2\right]}\)
czyli ten nawias kwadratowy po prawej mówi, że odpowiedzią jest czynnik przy \(\displaystyle{ z^2}\) w rozwinięciu tej funkcji
- Waylays
- Użytkownik
- Posty: 59
- Rejestracja: 26 lis 2014, o 19:14
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 19 razy
- Pomógł: 8 razy
Podział liczby 'n' na sumę 'k' nieujemnych składników (kol.)
Kolega wyżej podał rozwiązanie za pomocą funkcji tworzących, a ja podejde to tego zagadnienia inaczej. O ile dobrze myślę, to chodzi ci o znalezienie liczby rozwiązań równania \(\displaystyle{ x_1+x_2+...+x_k=n}\), gdzie \(\displaystyle{ x_i \in \{0, 1, 2, ...\}}\). Ponieważ rozwiązań szukamy w liczbach naturalnych, to równanie nazywa się równaniem diofantycznym. Odpowiedź na twoje pytanie jest bardzo prosta, lecz niekoniecznie łatwa - liczbę takich rozwiązań możemy wyrazić za pomocą liczby kombinacji z powtórzeniami \(\displaystyle{ n}\)-elementowych ze zbioru \(\displaystyle{ k}\)-elementowego (i tu trzeba uważać żeby się nie pogubić bo jeżeli przez \(\displaystyle{ n}\) oznaczymy prawą stronę, a przez \(\displaystyle{ k}\) liczbę niewiadomych, to tworzymy właśnie \(\displaystyle{ n}\)-elementowe kombinacje ze zbioru \(\displaystyle{ k}\)-elementowego). Czyli liczba takich rozwiązań to \(\displaystyle{ \overline {C}^n_k={{n+k-1} \choose n}={{n+k-1} \choose {k-1}}}\). Sytuacja analogiczna do rozmieszczania \(\displaystyle{ n}\) nierozróżnialnych kulek w \(\displaystyle{ k}\) rozróżnialnych pudełkach.
W twoim przypadku mamy zatem \(\displaystyle{ \overline {C}^2_4={{2+4-1} \choose 2}= \frac{4\cdot 5}{2} =10}\).
Co do twojego rozwiązania, jak rozpiszesz sobie ogólną liczbę kombinacji za pomocą silni, to zauważysz, że brakuje ci czegoś w mianowniku, a mianowicie \(\displaystyle{ n!}\).
~edit
Racja, niczego we wzorze nie brakuje. Nie zauważyłem, że mianownik leci od \(\displaystyle{ n+1}\) zamiast od \(\displaystyle{ 1}\), więc wszystko wygląda okay.
W twoim przypadku mamy zatem \(\displaystyle{ \overline {C}^2_4={{2+4-1} \choose 2}= \frac{4\cdot 5}{2} =10}\).
Co do twojego rozwiązania, jak rozpiszesz sobie ogólną liczbę kombinacji za pomocą silni, to zauważysz, że brakuje ci czegoś w mianowniku, a mianowicie \(\displaystyle{ n!}\).
~edit
Racja, niczego we wzorze nie brakuje. Nie zauważyłem, że mianownik leci od \(\displaystyle{ n+1}\) zamiast od \(\displaystyle{ 1}\), więc wszystko wygląda okay.
Ostatnio zmieniony 10 kwie 2016, o 16:34 przez Waylays, łącznie zmieniany 1 raz.
-
- Użytkownik
- Posty: 6
- Rejestracja: 10 kwie 2016, o 09:53
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 2 razy
Podział liczby 'n' na sumę 'k' nieujemnych składników (kol.)
Dzięki obydwóm Kolegom!
Pierwsze tłumaczenie jest piękne matematycznie - suma zamieniona na iloczyn, jeszcze do tego potęgi itp. Ale, tak - zrozumiałem o co chodzi. Tylko to trochę strzelanie z armaty do muchy.
Drugie rozwiązanie bardziej mi się podoba, dlatego tu wpisałem ten problem, bo coś czułem że to można wzorami kombinatorycznymi rozwiązać. Tylko nie spojrzałem na ten problem pod właściwym kątem, jak drugi z Panów (a gdzieś mi się plątała od wczoraj po głowie zasada szufladkowa Dirichleta). I niczego w moim ostatecznym wzorze nie brakuje, bo to jest dokładnie rozwinięcie tego C z kreską nad. Więc wszystko się zgadza.
Sam problem pojawił mi się wczoraj, gdy żona załapała bakcyla w rozwiązywaniu "obrazków logicznych". Za młodu napisałem program, który dla każdej linii generował możliwe układy punktów i wyznaczał, gdzie na pewno są pola zaczernione, a gdzie na pewno puste (i ostatecznie lecąc po kolumnach, wierszach, kolumnach etc. rozwiązywał całe zadanie). Ale dopiero dzisiaj zacząłem się zastanawiać, ile takich kombinacji właściwie dla danej linii istnieje. I mój wzór rekurencyjny wynika ze sposobu w jaki mój program generował kolejne układy. Po przeformułowaniu to jest właśnie problem, który przedstawiłem powyżej.
Problem uznaję za rozwiązany, aczkolwiek ciekawe, czy istnieją jeszcze inne sposoby rozwiązania tego problemu?
Pierwsze tłumaczenie jest piękne matematycznie - suma zamieniona na iloczyn, jeszcze do tego potęgi itp. Ale, tak - zrozumiałem o co chodzi. Tylko to trochę strzelanie z armaty do muchy.
Drugie rozwiązanie bardziej mi się podoba, dlatego tu wpisałem ten problem, bo coś czułem że to można wzorami kombinatorycznymi rozwiązać. Tylko nie spojrzałem na ten problem pod właściwym kątem, jak drugi z Panów (a gdzieś mi się plątała od wczoraj po głowie zasada szufladkowa Dirichleta). I niczego w moim ostatecznym wzorze nie brakuje, bo to jest dokładnie rozwinięcie tego C z kreską nad. Więc wszystko się zgadza.
Sam problem pojawił mi się wczoraj, gdy żona załapała bakcyla w rozwiązywaniu "obrazków logicznych". Za młodu napisałem program, który dla każdej linii generował możliwe układy punktów i wyznaczał, gdzie na pewno są pola zaczernione, a gdzie na pewno puste (i ostatecznie lecąc po kolumnach, wierszach, kolumnach etc. rozwiązywał całe zadanie). Ale dopiero dzisiaj zacząłem się zastanawiać, ile takich kombinacji właściwie dla danej linii istnieje. I mój wzór rekurencyjny wynika ze sposobu w jaki mój program generował kolejne układy. Po przeformułowaniu to jest właśnie problem, który przedstawiłem powyżej.
Problem uznaję za rozwiązany, aczkolwiek ciekawe, czy istnieją jeszcze inne sposoby rozwiązania tego problemu?
-
- Użytkownik
- Posty: 21
- Rejestracja: 10 kwie 2016, o 01:21
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 1 raz
- Pomógł: 7 razy
Podział liczby 'n' na sumę 'k' nieujemnych składników (kol.)
Można podejść do tego problemu kombinatorycznie. Chcesz podzielić \(\displaystyle{ n}\) nierozróżnialnych kulek na bloki, przy czym ważna jest kolejność bloków.
Dodatkowo dysponujemy \(\displaystyle{ k-1}\) przegródkami.
Mamy \(\displaystyle{ n+k-1}\) miejsc - w każdej znajdzie się przegródka lub kulka. Wybieramy więc miejsca w których mają być kulki, a na pozostałych umieszczamy przegródki.
Łatwo zauważyć, że istnieje bijekcja między układami kulek i podziałami liczby \(\displaystyle{ n}\).
Dodatkowo dysponujemy \(\displaystyle{ k-1}\) przegródkami.
Mamy \(\displaystyle{ n+k-1}\) miejsc - w każdej znajdzie się przegródka lub kulka. Wybieramy więc miejsca w których mają być kulki, a na pozostałych umieszczamy przegródki.
Łatwo zauważyć, że istnieje bijekcja między układami kulek i podziałami liczby \(\displaystyle{ n}\).
Ostatnio zmieniony 11 kwie 2016, o 00:03 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.
-
- Użytkownik
- Posty: 1594
- Rejestracja: 16 maja 2013, o 17:56
- Płeć: Mężczyzna
- Lokalizacja: Trójmiasto
- Podziękował: 11 razy
- Pomógł: 247 razy
Podział liczby 'n' na sumę 'k' nieujemnych składników (kol.)
Hubbaser, to co opisałeś o kulkach i przegródkach w literaturze występuje jako rozwiązanie metodą separatorów. Rozmieszczenie \(\displaystyle{ k}\) nierozróżnialnych kul do \(\displaystyle{ n}\) rozróżnialnych pudełek o ile pamiętam ze studiów było oznaczane jako:
\(\displaystyle{ \left\langle \begin{array}{c}k\\n\end{array}\right\rangle = {n+k-1 \choose k}}\)
czyli dokładnie to co opisałeś, mamy \(\displaystyle{ n+k-1}\) miejsc, z czego wybieramy \(\displaystyle{ k}\) na kule.
A co do "strzelania do muchy z armaty" to jak akurat nic prostszego nie przychodzi do głowy to można strzelać, grunt, żeby trafić. Tak długo jak rozwiązanie jest poprawne jest ok.
\(\displaystyle{ \left\langle \begin{array}{c}k\\n\end{array}\right\rangle = {n+k-1 \choose k}}\)
czyli dokładnie to co opisałeś, mamy \(\displaystyle{ n+k-1}\) miejsc, z czego wybieramy \(\displaystyle{ k}\) na kule.
A co do "strzelania do muchy z armaty" to jak akurat nic prostszego nie przychodzi do głowy to można strzelać, grunt, żeby trafić. Tak długo jak rozwiązanie jest poprawne jest ok.
- kinia7
- Użytkownik
- Posty: 704
- Rejestracja: 28 lis 2012, o 11:58
- Płeć: Kobieta
- Lokalizacja: Wrocław
- Podziękował: 89 razy
- Pomógł: 94 razy
Podział liczby 'n' na sumę 'k' nieujemnych składników (kol.)
raczejGouranga pisze:Hubbaser\(\displaystyle{ \left\langle \begin{array}{c}k\\n\end{array}\right\rangle = {n+k-1 \choose k}}\)
\(\displaystyle{ \left\langle \begin{array}{c}k\\n\end{array}\right\rangle = {n+k-1 \choose n}}\)
edit
rzeczywiście, powinnam była napisać
\(\displaystyle{ \left\langle \begin{array}{c}k\\n\end{array}\right\rangle = {n+k-1 \choose n-1}}\)
Ostatnio zmieniony 11 kwie 2016, o 20:39 przez kinia7, łącznie zmieniany 1 raz.
-
- Użytkownik
- Posty: 1594
- Rejestracja: 16 maja 2013, o 17:56
- Płeć: Mężczyzna
- Lokalizacja: Trójmiasto
- Podziękował: 11 razy
- Pomógł: 247 razy
Podział liczby 'n' na sumę 'k' nieujemnych składników (kol.)
przy wkładaniu \(\displaystyle{ k}\) kul do \(\displaystyle{ n}\) pudełek wybieramy \(\displaystyle{ k}\) miejsc na kule.