szukanie zaawansowane

Strona główna Matematyka.pl » Matematyka - królowa nauk » Probabilistyka » Kombinatoryka i matematyka dyskretna
 Strona 1 z 1
  [ Posty: 8 ] 
Autor Wiadomość
Mężczyzna dariusz_konieczny Offline
PostNapisane: 10 kwi 2016, o 13:12 
Użytkownik

Posty: 6
Lokalizacja: Polska
Problem: na ile sposobów można podzielić liczbę naturalną n na sumę k naturalnych (z zerem) składników, przy czym kolejność gra rolę. Np. dla n=2 i k=4 mamy rozwiązania:
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 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ą):
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 k wynosi:
\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 k>1):
f(k,n)=\frac{(n+1) \cdot (n+2) \cdot ... \cdot (n+k-1)}{(k-1)!}
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna Gouranga Offline
PostNapisane: 10 kwi 2016, o 14:37 
Użytkownik
Avatar użytkownika

Posty: 1446
Lokalizacja: Trójmiasto
to jest zadanie na funkcje generujące / szeregi formalne
x_1 + x_2 + x_3 + x_4 = n
wprowadzamy sobie roboczą zmienną z i dla każdej zmiennej x_i tworzymy jeden nawias, w którym mamy sumę zmiennych z w potęgach, które reprezentują wartość możliwą dla danego x_i

\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 x_i
w przykładzie z dwójką:
\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:
\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ć 2 to patrzymy na czynnik przy z^2, jest to 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:
\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 z^2 w rozwinięciu tej funkcji
Góra
Mężczyzna Waylays Offline
PostNapisane: 10 kwi 2016, o 14:50 
Użytkownik
Avatar użytkownika

Posty: 59
Lokalizacja: Kraków
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 x_1+x_2+...+x_k=n, gdzie 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 n-elementowych ze zbioru k-elementowego (i tu trzeba uważać żeby się nie pogubić bo jeżeli przez n oznaczymy prawą stronę, a przez k liczbę niewiadomych, to tworzymy właśnie n-elementowe kombinacje ze zbioru k-elementowego). Czyli liczba takich rozwiązań to \overline {C}^n_k={{n+k-1} \choose n}={{n+k-1} \choose {k-1}}. Sytuacja analogiczna do rozmieszczania n nierozróżnialnych kulek w k rozróżnialnych pudełkach.

W twoim przypadku mamy zatem \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 n!.

~edit
Racja, niczego we wzorze nie brakuje. Nie zauważyłem, że mianownik leci od n+1 zamiast od 1, więc wszystko wygląda okay.
Góra
Mężczyzna dariusz_konieczny Offline
PostNapisane: 10 kwi 2016, o 15:28 
Użytkownik

Posty: 6
Lokalizacja: Polska
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?
Góra
Mężczyzna Hubbaser Offline
PostNapisane: 10 kwi 2016, o 15:43 
Użytkownik

Posty: 21
Lokalizacja: Warszawa
Można podejść do tego problemu kombinatorycznie. Chcesz podzielić n nierozróżnialnych kulek na bloki, przy czym ważna jest kolejność bloków.

Dodatkowo dysponujemy k-1 przegródkami.

Mamy 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 n.
Góra
Mężczyzna Gouranga Offline
PostNapisane: 10 kwi 2016, o 16:00 
Użytkownik
Avatar użytkownika

Posty: 1446
Lokalizacja: Trójmiasto
Hubbaser, to co opisałeś o kulkach i przegródkach w literaturze występuje jako rozwiązanie metodą separatorów. Rozmieszczenie k nierozróżnialnych kul do n rozróżnialnych pudełek o ile pamiętam ze studiów było oznaczane jako:
\left\langle \begin{array}{c}k\\n\end{array}\right\rangle = {n+k-1 \choose k}
czyli dokładnie to co opisałeś, mamy n+k-1 miejsc, z czego wybieramy 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. :)
Góra
Kobieta kinia7 Offline
PostNapisane: 10 kwi 2016, o 21:50 
Użytkownik
Avatar użytkownika

Posty: 654
Lokalizacja: Wrocław
Gouranga napisał(a):
Hubbaser\left\langle \begin{array}{c}k\\n\end{array}\right\rangle = {n+k-1 \choose k}

raczej

\left\langle \begin{array}{c}k\\n\end{array}\right\rangle = {n+k-1 \choose n}

edit
rzeczywiście, powinnam była napisać
\left\langle \begin{array}{c}k\\n\end{array}\right\rangle = {n+k-1 \choose n-1}
Góra
Mężczyzna Gouranga Offline
PostNapisane: 10 kwi 2016, o 23:53 
Użytkownik
Avatar użytkownika

Posty: 1446
Lokalizacja: Trójmiasto
przy wkładaniu k kul do n pudełek wybieramy k miejsc na kule.
Góra
Poprzedni | Następny 
Utwórz nowy temat Odpowiedz w temacie  Strona 1 z 1
  [ Posty: 8 ] 

Strona główna Matematyka.pl » Matematyka - królowa nauk » Probabilistyka » Kombinatoryka i matematyka dyskretna

 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ile jest dzielnikow liczby  Anonymous  6
 ustawianie osob w rzedzie, liczby n-cyfrowe itp  Anonymous  16
 liczby podzielne  BSD  9
 liczby podzielne - zasada wlaczania i wylaczania  BSD  3
 Liczby Bella - pytanie[nowe]  author  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl