rozmieszczanie k przedmiotow w n miejscach

[bejola]

Moje przemyślenia dotyczące rozmieszczania \(\displaystyle{ k}\) przedmiotów w \(\displaystyle{ n}\) miejscach. Mamy tu cztery różne przypadki :
A. rozmieszczamy \(\displaystyle{ k}\) elementów nierozróżnialnych w \(\displaystyle{ n}\) nierozróżnialnych miejscach , np na ile sposobów można rozmieścić cztery jednakowe cukierki ( np cztery jednakowe michałki) w pięciu jednakowych ( nierozróżnialnych torebkach, po włożeniu cukierków, torebki kładziemy w sposób przypadkowy, więc nie możemy ich rozróżnić)
B. rozmieszczamy \(\displaystyle{ k}\) nierozróżnialnych elementów w \(\displaystyle{ n}\) rozróżnialnych miejscach, np na ile sposobów można rozmieścić cztery jednakowe, nierozróżnialne kule w pięciu rozróżnialnych przegródkach ( lub szufladach lub pudełkach o różnych kolorach, albo na przykład na ile sposobów może wysiąść z windy czteroosobowa brygada antyterrorystyczna na \(\displaystyle{ 7}\) piętrach) ludzie są zamaskowani, więc nie można ich rozróżnić, a pietra są ponumerowane, więc rozróżnialne)
C. rozmieszczamy \(\displaystyle{ k}\) rozróżnialnych elementów w \(\displaystyle{ n}\) nierozróżnialnych miejscach. np kule, każda w innym kolorze w \(\displaystyle{ n}\) jednakowych woreczkach i po umieszczeniu kuli ( lub pusty ) woreczek odkładamy w sposób przypadkowy gdziekolwiek.
D. rozmieszczamy \(\displaystyle{ k}\) rozróżnialnych elementów w \(\displaystyle{ n}\) rozróżnialnych miejscach. np cztery ponumerowane kule ( albo kule w różnych kolorach) do czterech ponumerowanych pudełek, albo do pudełek w różnych kolorach. Innym przykładem może być takie zadanie: na ile sposobów może wysiąść z windy \(\displaystyle{ 5}\) osób na \(\displaystyle{ 7}\) piętrach) Osoby są rozróżnialne a piętra są ponumerowane.
Jak obliczyć ilość możliwości w przykładzie A ?
1. wszystkie takie same elementy do jednego takiego samego woreczka - jedna możliwość ( nie ma znaczenia do którego woreczka je włożymy bo wszystkie są jednakowe i odkładamy go w sposób przypadkowy, gdziekolwiek)
2. dzielimy \(\displaystyle{ k}\) elementów na dwie części, potem na trzy części ... aż na \(\displaystyle{ k}\) części (czyli po jednym elemencie) .
np. ile jest możliwości włożenia \(\displaystyle{ 4}\) jednakowych, nierozróżnialnych kul do pięciu jednakowych, nierozróżnialnych woreczków? wszystkie do jednego ( \(\displaystyle{ 4 + 0}\) kul więc jedna możliwość) trzy do jednego i jedna do innego woreczka ( jedna możliwość) dwie do jednego z woreczków i dwie do innego z woreczków ( czyli po dwie kulki) wiec jedna możliwość , dwie do jednego woreczka i jedna do drugiego i jedna do trzeciego woreczka , czyli jedna możliwość no i po jednej kulce do \(\displaystyle{ 4}\) woreczków ( \(\displaystyle{ 1}\) możliwość) czyli w sumie odpowiedź: jest \(\displaystyle{ 5}\) możliwości włożenia czterech jednakowych kul do pięciu jednakowych woreczków.
B Ile jest możliwości umieszczenia \(\displaystyle{ 4}\) jednakowych kul w pięciu rozróżnialnych pudełkach ( szufladach, przegródkach, ponumerowanych urnach itd. ) tu mamy wzór : dwumian Newtona \(\displaystyle{ n + k - 1}\) nad \(\displaystyle{ n - 1}\) gdzie \(\displaystyle{ k}\) to ilość elementów , \(\displaystyle{ n}\) ilość miejsc; \(\displaystyle{ {n+k-1 \choose n-1}}\) . więc stosując wzór mamy \(\displaystyle{ 8}\) nad \(\displaystyle{ 4}\); \(\displaystyle{ {8 \choose 4}}\) mamy \(\displaystyle{ 70}\) możliwości
C. Ile jest możliwości rozmieszczenia \(\displaystyle{ 4}\) różnych kul w \(\displaystyle{ 5}\) jednakowych woreczkach, które po włożeniu elementów lub pozostawieniu pustym odkładamy w dowolne przypadkowe miejsce.
1. Wszystkie kulki wkładamy do jednego woreczka ( dwumian Newtona \(\displaystyle{ 4}\) nad \(\displaystyle{ 4}\); \(\displaystyle{ {4 \choose 4}}\) , jedna możliwość)
2. Do jednego z woreczków wkładamy trzy kulki do innego jedną kulkę , tu mamy dwumian Newtona \(\displaystyle{ 4}\) nad \(\displaystyle{ 1}\); \(\displaystyle{ {4 \choose 1}}\) więc \(\displaystyle{ 4}\) możliwości ( wybieramy jedna kulkę z czterech na cztery sposoby )
3. Wkładamy dwie kulki do jednego z woreczków i dwie pozostałe do drugiego woreczka, możemy wybrać dwie kulki z czterech, ale musimy połączyć je w pary bo do jednego woreczka dwie i do drugiego dwie, więc \(\displaystyle{ \frac12 \cdot}\) dwumian Newtona \(\displaystyle{ 4}\) nad \(\displaystyle{ 2}\) ; \(\displaystyle{ \frac{1}{2} \cdot {4 \choose 2}}\) więc mamy trzy możliwości
4. wkładamy po jednej kulce do czterech woreczków, więc mamy \(\displaystyle{ 1}\) możliwość ( woreczki są nierozróżnialne i odkładamy je w sposób przypadkowy na stole, wiec wszystko jedno do którego woreczka wkładamy kulkę, byle po jednej kulce)
Odpowiedź : \(\displaystyle{ 4}\) różne kulki w pięciu jednakowych woreczkach możemy rozmieścić na \(\displaystyle{ 1+4+3 +1}\) czyli na \(\displaystyle{ 9}\) sposobów
D. Na ile sposobów można rozmieścić \(\displaystyle{ 4}\) różne kule w pięciu różnych ( np. ponumerowanych) pudełkach ? Albo na ile możliwości mogą wysiąść z windy \(\displaystyle{ 4}\) rozróżnialne osoby ( mające identyfikatory lub np. swoje dowody osobiste przy sobie, albo osoby, które akurat znamy, albo umiemy je w jakiś sposób rozróżnić: np każdy pasażer windy ma inny kolor oczu itp. , bo jak ja bym na przykład jechała tą windą z nimi i bym nie założyła okularów, to by były te osoby dla mnie nierozróżnialne ) na \(\displaystyle{ 5}\) piętrach ? ( może to być np piwnica, parter i trzy piętra domu , są takie domy u mnie w Tychach ... trzypiętrowe budynki z podziemnym garażem i oczywiście z parterem więc są takie przyciski w windzie : \(\displaystyle{ -1, p , 1 ,2 ,3}\) ) I tu obliczamy ilość możliwości wzorem na wariację z powtórzeniami więc \(\displaystyle{ n}\) do potęgi \(\displaystyle{ k}\); \(\displaystyle{ W = n^{k}}\) czyli \(\displaystyle{ 5^{4} = 625}\) możliwości ( w tym przypadku można narysować drzewko potęgowe: z jednego punktu wyprowadzamy \(\displaystyle{ 5}\) gałęzi potem z każdego z pięciu punktów znowu po \(\displaystyle{ 5}\) gałęzi , następnie z każdego z \(\displaystyle{ 25}\) punktów znowu po \(\displaystyle{ 5}\) gałęzi i na koniec z każdego ze \(\displaystyle{ 125}\) punktów znowu po \(\displaystyle{ 5}\) gałęzi czyli \(\displaystyle{ 625}\) gałęzi)
dla przypomnienia : \(\displaystyle{ k=}\) ilość elementów, które rozmieszczamy; \(\displaystyle{ n =}\) ilość miejsc do rozmieszczania tych elementów (ilość pudełek, woreczków, urn itd), Podobnie przy rzutach monetą : \(\displaystyle{ k =}\) ilość rzutów ( albo ilość monet przy jednokrotnym rzucie) . \(\displaystyle{ n =}\) ilość możliwości, czyli wypadnie albo orzeł albo reszka, więc \(\displaystyle{ n =2}\) , innym przykładem rzuty kostką do gry : \(\displaystyle{ k}\)- ilość rzutów jedną kostką do gry (albo ilość kostek przy jednokrotnym rzucie tymi kostkami) \(\displaystyle{ n =}\) ilość możliwości a więc tu \(\displaystyle{ n=6}\) ( \(\displaystyle{ 1}\) oczko albo \(\displaystyle{ 2}\) oczka albo \(\displaystyle{ 3}\) albo \(\displaystyle{ 4}\) albo \(\displaystyle{ 5}\) albo \(\displaystyle{ 6}\) oczek ) w takich przypadkach również mamy do czynienia z wariacją z powtórzeniami ( ciągi \(\displaystyle{ k}\) elementowe ze zbioru \(\displaystyle{ n}\) elementowego)
Jolanta Pokrzywińska, Tychy

[mat_61]

Czy masz do tego jakieś pytanie?

W przykładzie C nie uwzględniłaś przypadku dla podziału kulek \(\displaystyle{ 2+1+1}\)

[krzeslo789]

Co do przypadku A baw się wzorem:

\(\displaystyle{ P(n+k,k)= \sum_{i=1}^{k}P(n,i)}\)

gdzie:

\(\displaystyle{ P(n,k)=0, n<k}\)

\(\displaystyle{ P(n,2)=[ \frac{n}{2} ]}\) część całkowita

\(\displaystyle{ P(n,1)=1}\)


Gwoli ścisłości:

I kule rozróżnialne i urny rozróżnialne

a) wszystkie urny zajęte
b) mogą być puste.


II kule rozróżnialne i urny nierozróżnialne

a) wszystkie urny zajęte
b) mogą być puste.

III kule nierozróżnialne i urny rozróżnialne

a) wszystkie urny zajęte
b) mogą być puste.

IV kule nierozróżnialne i urny nierozróżnialne

a) wszystkie urny zajęte
b) mogą być puste.

W sumie jest osiem przypadków , do każdego przypadku jest ładny wzór!

[ludozyad]

Sory że odkopuje temat, ale mógłby ktoś podać wzory na te osiem przypadków? Nie będe nowego zakładał jak już znalazłem /z góry dzięki/-- 16 maja 2015, o 13:00 --Sory że odkopuje temat, ale mógłby ktoś podać wzory na te osiem przypadków? Nie będe nowego zakładał jak już znalazłem /z góry dzięki/

[adeater]

Hej

Mam problem z podobnym zadaniem

Na ile sposobów można umieścić 4 kule w 2 pudełkach przy założeniu, że:
(a) kule i pudełka są rozróżnialne;
(b) kule są rozróżnialne, ale pudełka są nierozróżnialne;
(c) pudełka są rozróżnialne, ale kule są nierozróżnialne;
(d) kule i pudełka są nierozróżnialne?

W a) mam to rozumieć, że pierwszą kulę mogę wybrać na 2 sposoby (bo 2 pudełka), drugą tak samo, trzecią tak samo i czwartą tak samo, czyli 2*2*2*2?

Co do b) c) i d) nie mam kompletnie pojęcia

Mógłby ktoś pomóc?

[arek1357]

a) Wariacje z powtórzeniami:

\(\displaystyle{ 2^4}\)


b)Podziały zbiorów Liczby Stirlinga Drugiego rodzaju:

\(\displaystyle{ S(4,2)=7}\)


c)Wariacje bez powtórzeń:

Tyle ile jest rozwiązań w całkowitych nieujemnych:

\(\displaystyle{ x_{1}+x_{2}=4}\)


d)Partycje liczby:

\(\displaystyle{ P(4,2)= \left[ \frac{4}{2}\right]=2}\)


Można jeszcze rozpatrywać możliwości, gdzie mamy dopuszczone, że niektóre urny mogą być puste...

[adeater]

Ok ok ok, dziękuję

Byłbyś w stanie mnie przeprowadzić przez to zadanie? Nie jestem w stanie ułożyć równania do odpowiedniego podpunktu. Po prostu jeszcze nie umiem tego na tyle. Dopiero zaczynam, a do odpowiedzi chciałbym dojść sam

Skąd powinienem wiedzieć, że do b) bierze się ten podział zbiorów Liczby Stirlinga?

[arek1357]

Już ci napisałem mniej więcej jakie to wzory, a do drugiego punktu czemu są to liczby Stirlinga bo masz coś takiego:

\(\displaystyle{ \left\{ 1\right\} \left\{ 2,3,4\right\}}\)

\(\displaystyle{ \left\{ 2\right\} \left\{ 1,3,4\right\}}\)

\(\displaystyle{ \left\{ 3\right\} \left\{1, 2,4\right\}}\)

\(\displaystyle{ \left\{ 4\right\} \left\{ 1,2,3\right\}}\)

\(\displaystyle{ \left\{ 1,2\right\} \left\{ 3,4\right\}}\)

\(\displaystyle{ \left\{ 1,3\right\} \left\{ 2,4\right\}}\)

\(\displaystyle{ \left\{ 1,4\right\} \left\{ 2,3\right\}}\)

Czyli jest siedem, jak widać nawiasy klamrowe to szuflady nierozróżnialne, a kule rozróżnialne , no i widać, że Musimy wziąć podziały zbiorów a co za tym idzie Liczby Stirlinga Drugiego rodzaju...

Wzór na partycje masz podany wyżej, jest to wzór rekurencyjny, jakbyś zobaczył jawny mógłbyś umrzeć...

[adeater]

W odpowiedziach do b) prowadzący podał nam \(\displaystyle{ \frac{16}{2} = 8}\)
Możliwe, że się pomylił?

[Belf]

Już ci napisałem mniej więcej jakie to wzory, a do drugiego punktu czemu są to liczby Stirlinga bo masz coś takiego:

\(\displaystyle{ \left\{ 1\right\} \left\{ 2,3,4\right\}}\)

\(\displaystyle{ \left\{ 2\right\} \left\{ 1,3,4\right\}}\)

\(\displaystyle{ \left\{ 3\right\} \left\{1, 2,4\right\}}\)

\(\displaystyle{ \left\{ 4\right\} \left\{ 1,2,3\right\}}\)

\(\displaystyle{ \left\{ 1,2\right\} \left\{ 3,4\right\}}\)

\(\displaystyle{ \left\{ 1,3\right\} \left\{ 2,4\right\}}\)

\(\displaystyle{ \left\{ 1,4\right\} \left\{ 2,3\right\}}\)

Czyli jest siedem, jak widać nawiasy klamrowe to szuflady nierozróżnialne, a kule rozróżnialne , no i widać, że Musimy wziąć podziały zbiorów a co za tym idzie Liczby Stirlinga Drugiego rodzaju...

Z treści zadania nie wynika,że w każdej szufladzie musi być co najmniej jedna kula, a więc musimy dołożyć przypadek czterech kul w jednej szufladzie:\(\displaystyle{ \left\{0 \right\} \left\{ 1,2,3,4\right\}}\)

[arek1357]

No oczywiście to dojdzie jeszcze jeden przypaeki a wzór ogólny to będzie sumowanie po liczbach Stirlinga.
Jeżeli zechcesz dołączyć możliwości pustych szuflad...

\(\displaystyle{ S'(n,k)}\) - ilość wszystkich możliwości

\(\displaystyle{ S'(n,k)=S(n,1)+S(n,2)+...+S(n,k)}\)

Możesz zastosować coś takiego, gdzie masz możliwości z pustymi szufladami...

[adeater]

Ok, dziękuję

A jak mam rozumieć to, że i kule i szuflady są nierozróżnialne?

[arek1357]

To będzie:

\(\displaystyle{ P(4,2)=2}\)

Bo może być:

\(\displaystyle{ 3+1,2+2}\)

A jak założymy, że mogą być puste to mamy jeszcze:

\(\displaystyle{ 4+0}\)

A w ogólności:

\(\displaystyle{ P'(n,k)=P(n,1)+P(n,2)+...+P(n,k)}\)

W ostatnim przypadku rozróżnienie daje nam tylko , jak mamy różne ilości kul w szufladach...


Z dziennikarskiego obowiązku przypomnę ci, że brakuje dwóch przypadków do a i b:

Tzn. przypadek gdy wszystkie szuflady są niepuste...