szukanie zaawansowane
 [ Posty: 13 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 18 sty 2013, o 14:04 
Użytkownik

Posty: 3
Lokalizacja: Tychy
Moje przemyślenia dotyczące rozmieszczania k przedmiotów w n miejscach. Mamy tu cztery różne przypadki :
A. rozmieszczamy k elementów nierozróżnialnych w 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 k nierozróżnialnych elementów w 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 7 piętrach) ludzie są zamaskowani, więc nie można ich rozróżnić, a pietra są ponumerowane, więc rozróżnialne)
C. rozmieszczamy k rozróżnialnych elementów w n nierozróżnialnych miejscach. np kule, każda w innym kolorze w n jednakowych woreczkach i po umieszczeniu kuli ( lub pusty ) woreczek odkładamy w sposób przypadkowy gdziekolwiek.
D. rozmieszczamy k rozróżnialnych elementów w 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 5 osób na 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 k elementów na dwie części, potem na trzy części ... aż na k części (czyli po jednym elemencie) .
np. ile jest możliwości włożenia 4 jednakowych, nierozróżnialnych kul do pięciu jednakowych, nierozróżnialnych woreczków? wszystkie do jednego ( 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 4 woreczków ( 1 możliwość) czyli w sumie odpowiedź: jest 5 możliwości włożenia czterech jednakowych kul do pięciu jednakowych woreczków.
B Ile jest możliwości umieszczenia 4 jednakowych kul w pięciu rozróżnialnych pudełkach ( szufladach, przegródkach, ponumerowanych urnach itd. ) tu mamy wzór : dwumian Newtona n + k - 1 nad n - 1 gdzie k to ilość elementów , n ilość miejsc; {n+k-1 \choose n-1} . więc stosując wzór mamy 8 nad 4; {8 \choose 4} mamy 70 możliwości
C. Ile jest możliwości rozmieszczenia 4 różnych kul w 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 4 nad 4; {4 \choose 4} , jedna możliwość)
2. Do jednego z woreczków wkładamy trzy kulki do innego jedną kulkę , tu mamy dwumian Newtona 4 nad 1; {4 \choose 1} więc 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 \frac12 \cdot dwumian Newtona 4 nad 2 ; \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 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ź : 4 różne kulki w pięciu jednakowych woreczkach możemy rozmieścić na 1+4+3 +1 czyli na 9 sposobów
D. Na ile sposobów można rozmieścić 4 różne kule w pięciu różnych ( np. ponumerowanych) pudełkach ? Albo na ile możliwości mogą wysiąść z windy 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. :P , 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 :lol: ) na 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 : -1, p , 1 ,2 ,3 ) I tu obliczamy ilość możliwości wzorem na wariację z powtórzeniami więc n do potęgi k; W =   n^{k} czyli 5^{4} = 625 możliwości ( w tym przypadku można narysować drzewko potęgowe: z jednego punktu wyprowadzamy 5 gałęzi potem z każdego z pięciu punktów znowu po 5 gałęzi , następnie z każdego z 25 punktów znowu po 5 gałęzi i na koniec z każdego ze 125 punktów znowu po 5 gałęzi czyli 625 gałęzi)
dla przypomnienia : k= ilość elementów, które rozmieszczamy; n = ilość miejsc do rozmieszczania tych elementów (ilość pudełek, woreczków, urn itd), Podobnie przy rzutach monetą : k = ilość rzutów ( albo ilość monet przy jednokrotnym rzucie) . n = ilość możliwości, czyli wypadnie albo orzeł albo reszka, więc n =2 , innym przykładem rzuty kostką do gry : k- ilość rzutów jedną kostką do gry (albo ilość kostek przy jednokrotnym rzucie tymi kostkami) n = ilość możliwości a więc tu n=6 ( 1 oczko albo 2 oczka albo 3 albo 4 albo 5 albo 6 oczek ) w takich przypadkach również mamy do czynienia z wariacją z powtórzeniami ( ciągi k elementowe ze zbioru n elementowego)
Jolanta Pokrzywińska, Tychy
Góra
Mężczyzna Offline
PostNapisane: 19 sty 2013, o 11:15 
Użytkownik

Posty: 4612
Lokalizacja: Racibórz
Czy masz do tego jakieś pytanie?

W przykładzie C nie uwzględniłaś przypadku dla podziału kulek 2+1+1
Góra
Mężczyzna Offline
PostNapisane: 19 sty 2013, o 21:13 
Użytkownik

Posty: 34
Lokalizacja: dom
Co do przypadku A baw się wzorem:

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

gdzie:

P(n,k)=0,  n<k

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

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!
Góra
Mężczyzna Offline
PostNapisane: 16 maja 2015, o 12:26 
Użytkownik

Posty: 17
Lokalizacja: Rzeszów
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 :D /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 :D /z góry dzięki/
Góra
Mężczyzna Offline
PostNapisane: 15 sty 2018, o 11:29 
Użytkownik

Posty: 8
Lokalizacja: Piła
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?
Góra
Mężczyzna Offline
PostNapisane: 15 sty 2018, o 11:54 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
a) Wariacje z powtórzeniami:

2^4


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

S(4,2)=7


c)Wariacje bez powtórzeń:

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

x_{1}+x_{2}=4


d)Partycje liczby:

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...
Góra
Mężczyzna Offline
PostNapisane: 15 sty 2018, o 11:59 
Użytkownik

Posty: 8
Lokalizacja: Piła
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?
Góra
Mężczyzna Offline
PostNapisane: 15 sty 2018, o 12:05 
Użytkownik
Avatar użytkownika

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

\left\{ 1\right\} \left\{ 2,3,4\right\}

\left\{ 2\right\} \left\{ 1,3,4\right\}

\left\{ 3\right\} \left\{1, 2,4\right\}

\left\{ 4\right\} \left\{ 1,2,3\right\}

\left\{ 1,2\right\} \left\{ 3,4\right\}

\left\{ 1,3\right\} \left\{ 2,4\right\}

\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ć...
Góra
Mężczyzna Offline
PostNapisane: 15 sty 2018, o 12:09 
Użytkownik

Posty: 8
Lokalizacja: Piła
W odpowiedziach do b) prowadzący podał nam \frac{16}{2} = 8
Możliwe, że się pomylił?
Góra
Mężczyzna Offline
PostNapisane: 15 sty 2018, o 12:10 
Użytkownik

Posty: 399
Lokalizacja: Kraków
arek1357 napisał(a):
Już ci napisałem mniej więcej jakie to wzory, a do drugiego punktu czemu są to liczby Stirlinga bo masz coś takiego:

\left\{ 1\right\} \left\{ 2,3,4\right\}

\left\{ 2\right\} \left\{ 1,3,4\right\}

\left\{ 3\right\} \left\{1, 2,4\right\}

\left\{ 4\right\} \left\{ 1,2,3\right\}

\left\{ 1,2\right\} \left\{ 3,4\right\}

\left\{ 1,3\right\} \left\{ 2,4\right\}

\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:\left\{0 \right\} \left\{ 1,2,3,4\right\}
Góra
Mężczyzna Offline
PostNapisane: 15 sty 2018, o 12:20 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
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...

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

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...
Góra
Mężczyzna Offline
PostNapisane: 15 sty 2018, o 12:26 
Użytkownik

Posty: 8
Lokalizacja: Piła
Ok, dziękuję

A jak mam rozumieć to, że i kule i szuflady są nierozróżnialne?
Góra
Mężczyzna Offline
PostNapisane: 15 sty 2018, o 12:30 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
To będzie:

P(4,2)=2

Bo może być:

3+1,2+2

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

4+0

A w ogólności:

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...
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 13 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Na ile sposobów można podzielić 9 różnych przedmiotów...  DVKwodzu  1
 Rozdawanie przedmiotów pomiędzy osoby  spacerunner  4
 k różnych przedmiotów w n szufladach  kogutto  2
 Ile liczb w systemie trójkowym można zapisać na 4 miejscach?  Valiors  7
 rozmieszczanie k różnych kul w n różnych urnach  Z_i_o_M_e_K  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl