szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 13 maja 2015, o 14:27 
Użytkownik

Posty: 319
Lokalizacja: Gorzów Wlkp.
Witam

Mam takie zadanie
Cytuj:
Mamy n różnych klas obiektów, obiekty danej klasy są między sobą nierozróżnialne. Na ile sposobów można z nich utworzyć k-elementowy zbiór.

Z góry dziękuję za pomoc
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 13 maja 2015, o 15:36 
Użytkownik
Avatar użytkownika

Posty: 1229
Zauważ, że właściwie pytamy się o to ile jest kombinacji z powtórzeniami długości k ze zbioru n - elementowego. Wskazówka - wybierz taką kombinację i uporządkuj niemalejąco. Następnie dodaj do i-tego elementu i. Wtedy będziesz miał elementy uporządkowane rosnąco i będziesz mógł skorzystać ze wzoru na kombinację bez powtórzeń - pozdrawiam :)
Góra
Mężczyzna Offline
PostNapisane: 13 maja 2015, o 20:03 
Użytkownik

Posty: 319
Lokalizacja: Gorzów Wlkp.
No jakoś mi nie wychodzi.

Mamy np. obiekty a, b,c i chcemy z nich utworzyć 2 - elementowe zbiory. To można z nich utworzyć następujące zbiory:
\left\{ a,a\right\} ,\left\{ b,b\right\} , \left\{ c,c\right\} , \left\{ a,b\right\} \right\}, \left\{ a,c\right\},\left\{ b,c\right\}, czyli 6.

Teraz liczę kombinację z powtórzeniami
długość k = 2
elementów n = 3

{n+k-1 \choose n} =  {3+2-1 \choose 3} = 4

4 \neq 6 :)

@edit:
dobra ogarnąłem, jeśli przyjąć za k ilość klas obiektów, a za n długość to wszystko to wzór to
{k+n-1 \choose k}

Uzasadnienie: załóżmy, że 0 to "seperator", a 1 to obiekt jakiejś klasy, są one uporządkowane w jakiś tam sposób. I teraz na powyższym przykładzie mamy 3-1=2 separatorów, 2 elementy, czyli że na przykład \left\{ a,a\right\} to 1100, a\left\{ a,c\right\}1001. Czyli nasze zadanie polega na ilości możliwości wstawienia dwóch zer pomiędzy dwie jedynki. Dobrze rozumuje?
Góra
Mężczyzna Offline
PostNapisane: 14 maja 2015, o 00:03 
Użytkownik
Avatar użytkownika

Posty: 1229
Nie wiem, bo jestem pijany. Ale wiem jedno. Można to rozwalić tak. Zbiór \lbrace 1, 2, \ldots , n\rbrace. Wybieramy z niego kombinacje z powtórzeniami długości k. Możemy elementy tej kombinacji ustwić w niemlejący ciąg:

1 \le n_1 \le n_2\le \ldots \le n_k \le n. Hura.

Teras robimy tak:

1 \le n_1 < n_2 + 1 < \ldots < n_k + (k-1)\le n+(k-1)

Czyli sprowadziliśmy problem do przypadku brania kombinacji długości k bez powtoren ze zbiru n+k-1 elementowego. I jeszcze wikipedia mówi, że dobrze. Jupi!!!
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Gdzie jest błąd - kombinacje  Tasoth  7
 Rozdawanie Pączków, kombinacje  Lokaty Lokacz  1
 Kombinacje: losujemy 3 cyfry, ile jest wyników...?  escargot  3
 jaki jest wzor na... - zadanie 2  TobiWan  5
 kombinacje - zajmowanie miejsc w kinie  micho90  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl