Wzór ogólny (klasy obiektów, kombinacje)

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
MathMaster
Użytkownik
Użytkownik
Posty: 318
Rejestracja: 23 paź 2009, o 20:17
Płeć: Mężczyzna
Lokalizacja: Gorzów Wlkp.
Podziękował: 80 razy

Wzór ogólny (klasy obiektów, kombinacje)

Post autor: MathMaster »

Witam

Mam takie zadanie
Mamy \(\displaystyle{ n}\) różnych klas obiektów, obiekty danej klasy są między sobą nierozróżnialne. Na ile sposobów można z nich utworzyć \(\displaystyle{ k}\)-elementowy zbiór.
Z góry dziękuję za pomoc
Ostatnio zmieniony 13 maja 2015, o 16:59 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Awatar użytkownika
jutrvy
Użytkownik
Użytkownik
Posty: 1202
Rejestracja: 24 lis 2014, o 18:04
Płeć: Mężczyzna
Podziękował: 10 razy
Pomógł: 239 razy

Wzór ogólny (klasy obiektów, kombinacje)

Post autor: jutrvy »

Zauważ, że właściwie pytamy się o to ile jest kombinacji z powtórzeniami długości \(\displaystyle{ k}\) ze zbioru \(\displaystyle{ n}\) - elementowego. Wskazówka - wybierz taką kombinację i uporządkuj niemalejąco. Następnie dodaj do \(\displaystyle{ i}\)-tego elementu \(\displaystyle{ i}\). Wtedy będziesz miał elementy uporządkowane rosnąco i będziesz mógł skorzystać ze wzoru na kombinację bez powtórzeń - pozdrawiam
MathMaster
Użytkownik
Użytkownik
Posty: 318
Rejestracja: 23 paź 2009, o 20:17
Płeć: Mężczyzna
Lokalizacja: Gorzów Wlkp.
Podziękował: 80 razy

Wzór ogólny (klasy obiektów, kombinacje)

Post autor: MathMaster »

No jakoś mi nie wychodzi.

Mamy np. obiekty \(\displaystyle{ a, b,c}\) i chcemy z nich utworzyć 2 - elementowe zbiory. To można z nich utworzyć następujące zbiory:
\(\displaystyle{ \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ść \(\displaystyle{ k = 2}\)
elementów \(\displaystyle{ n = 3}\)

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

\(\displaystyle{ 4 \neq 6}\)

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

Uzasadnienie: załóżmy, że \(\displaystyle{ 0}\) to "seperator", a \(\displaystyle{ 1}\) to obiekt jakiejś klasy, są one uporządkowane w jakiś tam sposób. I teraz na powyższym przykładzie mamy \(\displaystyle{ 3-1=2}\) separatorów, \(\displaystyle{ 2}\) elementy, czyli że na przykład \(\displaystyle{ \left\{ a,a\right\}}\) to \(\displaystyle{ 1100}\), a\(\displaystyle{ \left\{ a,c\right\}}\)\(\displaystyle{ 1001}\). Czyli nasze zadanie polega na ilości możliwości wstawienia dwóch zer pomiędzy dwie jedynki. Dobrze rozumuje?
Awatar użytkownika
jutrvy
Użytkownik
Użytkownik
Posty: 1202
Rejestracja: 24 lis 2014, o 18:04
Płeć: Mężczyzna
Podziękował: 10 razy
Pomógł: 239 razy

Wzór ogólny (klasy obiektów, kombinacje)

Post autor: jutrvy »

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

\(\displaystyle{ 1 \le n_1 \le n_2\le \ldots \le n_k \le n}\). Hura.

Teras robimy tak:

\(\displaystyle{ 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 \(\displaystyle{ k}\) bez powtoren ze zbiru \(\displaystyle{ n+k-1}\) elementowego. I jeszcze wikipedia mówi, że dobrze. Jupi!!!
ODPOWIEDZ