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.
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
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}\)
@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?
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:
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!!!