pasazerowie opuszczajacy autobus

[Hellbike]

Oblicz, na ile sposob 20 pasazerow moze oposcic autobus zatrzymujacy sie na 7 przystankach, z warunkiem, ze na kazdym ktos wysiadzie.

a wiec: wybieramy 7 pasazerow z 20-tu ktorzy beda po jednej sztuce na kazdym z przystankow i mnozymy przez 7!, bo kolejnosc ma znaczenie, czyli:

\(\displaystyle{ {20 \choose 7} \cdot 7!}\)

do tego dodajemy rozlozenie pozostalych pasazerow, ktore wynosi \(\displaystyle{ 7^{13}}\),

czyli razem:
\(\displaystyle{ {20 \choose 7} \cdot 7! + 7^{13}}\)

[Inkwizytor]

Tok myślenia OK ale trzeba wszystko wymnożyć a nie dodać

[mat_61]

Niestety nie jest to dobre rozwiązanie. Ani co do sposobu liczenia ani toku myślenia.
Ten sposób liczenia powoduje, że takie same przypadki liczone są wielokrotnie. Np. na początku możemy wybrać i rozmieścić 7 pasażerów tak (kolejne wiersze to kolejne przystanki)

1
3
5
6
7
15
17

Teraz dokładamy pozostałych 13 pasażerów np. tak:

1+2
3+4
5
6
7
15
17+pozostali

W drugim wariancie możemy wybrać i rozmieścić 7 pasażerów np. tak:

2
4
5
6
7
15
17

oraz dołożyć 13 pasażerów tak:

2+1
4+3
5
6
7
15
17+pozostali

Jak widzisz te warianty są identyczne choć w Twoim sposobie liczenia są uwzględnione wielokrotnie (tutaj pokazane są tylko dwa warianty, ale przecież np. zamiana na ostatnim przystanku każdej z 12 wysiadających osób - wpisanej jako pierwszej, pochodzącej z tej wybranej siódemki daje kolejne warianty, podobnie jak inny wariant wyboru pierwszej osoby na dwóch pierwszych przystankach).

[Hellbike]

a wiec... jak to zrobic?

[mat_61]

Obliczenia można zrobić wg schematu:

Dla ułatwienia zapisu wprowadzę oznaczenia:

\(\displaystyle{ P^{k}_{n}}\) - nie wysiadł nikt na k przystankach z n
\(\displaystyle{ W^{k}_{n}}\) - dowolny sposób wysiadania n osób na k przystankach (czyli także warianty, że na dowolnych z k przystanków może nikt nie wysiąść)

1) Od wszystkich możliwych wariantów wysiadania odjąć te w których na co najmniej jednym przystanku nikt nie wysiadł, czyli:

\(\displaystyle{ W^{7}_{20}- \left( P^{1}_{7}+P^{2}_{7}+P^{3}_{7}+...+P^{6}_{7}\right)}\)

2) Oczywiście żeby obliczyć ilość wariantów \(\displaystyle{ P^{1}_{7}}\) należy wybrać 6 przystanków z 7 na których wysiadła co najmniej jedna osoba i obliczyć ile jest takich możliwości wysiadania, czyli:

\(\displaystyle{ P^{1}_{7}= {7 \choose 6} \cdot \left( W^{6}_{20}-\left( P^{1}_{6}+P^{2}_{6}+P^{3}_{6}+...+P^{5}_{6}\right)\right\)}\)

3) Analogicznie żeby obliczyć ilość wariantów \(\displaystyle{ P^{2}_{7}}\) należy wybrać 5 przystanków z 7 na których wysiadła co najmniej jedna osoba i obliczyć ile jest takich możliwości wysiadania, czyli:

\(\displaystyle{ P^{2}_{7}= {7 \choose 5} \cdot \left( W^{5}_{20}-\left( P^{1}_{5}+P^{2}_{5}+P^{3}_{5}+P^{4}_{5}\right)\right)}\)

itd.

W ten sam sposób obliczymy ostatni składnik sumy, czyli \(\displaystyle{ P^{6}_{7}}\) jako:

\(\displaystyle{ P^{6}_{7}= {7 \choose 1} \cdot W^{1}_{20}}\)

Oczywiście w analogiczny sposób obliczymy składniki \(\displaystyle{ P^{k}_{n}}\) pozostałych sum dla poszczególnych punktów.

Może ten sposób wydaje się lekko przydługi, ale nie znam innego który byłby krótszy, co oczywiście nie znaczy, że takiego nie ma (może ma ktoś jakiś inny pomysł ?).

Może po rozpisaniu całości (albo kilku pierwszych wariantów) da się zapisać jakiś uproszczony, ogólny wzór na tego typu zadanie.

W dotychczas spotkanych przeze mnie zadaniach tego typu liczba k nie przekraczała wartości 3 lub 4, co znacznie upraszczało zapis.

[Hellbike]

eeeeeeee............. to zadanie powinno miec jakies proste rozwiazanie.
Bardzo proste. Tak proste jak to moje, bledne.

[Qń]

Zauważmy, że pytamy po prostu o ilość funkcji "na" ze zbioru dwudziestoelementowego w siedmioelementowy. Takich funkcji jest:
\(\displaystyle{ \left\{ \begin{matrix}20 \\ 7 \end{matrix}\right\} \cdot 7!}\)
gdzie \(\displaystyle{ \left\{ \begin{matrix}n \\ k \end{matrix}\right\}}\) to liczba Stirlinga drugiego rodzaju.

Zastanów się dlaczego tak jest.

Q.

[mat_61]

Bardzo proste. Tak proste jak to moje, błędne.

Nie jest to wykluczone, ale widziałem już trochę zadań tego typu i żadnego "bardzo prostego" - w sensie rachunków - rozwiązania.
Przykładowo tutaj jest tego typu zadanie: https://www.matematyka.pl/216628.htm#p803819. Wprawdzie są to kolejki (czyli liczy się także kolejność) ale co do sposobu rozwiązania jest ono takie jak powyżej. Oczywiście przy 3 kolejkach (a nie 7) rozwiązanie wydaje się rachunkowo proste. Trzeba więc szukać

--------------------------------------

Widzę wskazówkę napisaną przez Qń-a. Z bardzo dużym p-stwem (dla mnie równym 1) jest ona dobra, z tym, że sposób rozwiązania z pewnością wybiega poza zakres szkoły średniej.

[Qń]

sposób rozwiązania z pewnością wybiega poza zakres szkoły średniej.

Jeśli zadanie wykracza ponad poziom szkoły średniej, to rozwiązanie chyba też ma prawo .

Natomiast gdybyśmy przyjęli, że pasażerowie są nierozróżnialni (szara masa ), to już byłby poziom szkoły średniej (kombinacje z powtórzeniami).

Q.

[mat_61]

Poczytałem sobie o liczbach Stirlinga i faktycznie z ich zastosowaniem sprawa jest prościutka.

Skoro liczby Stirlinga II rodzaju opisują liczbę sposobów podziału zbioru n elementowego na k niepustych podzbiorów to wszystko jest jasne.

Zastanawiam się tylko czy do przedstawienia tej ilości w postaci liczby naturalnej (czyli jej wyliczenia) jest inny sposób niż skorzystanie ze wzoru rekurencyjnego?

-- 23 sty 2011, o 16:17 --

Natomiast gdybyśmy przyjęli, że pasażerowie są nierozróżnialni (szara masa ), to już byłby poziom szkoły średniej (kombinacje z powtórzeniami).

Q.

Czy dobrze rozumiem, że w takim przypadku należałoby obliczyć 13-elementową kombinację z powtórzeniami ze zbioru 7-elementowego ?

W 20 elementowym multizbiorze mamy elementy wybrane spośród \(\displaystyle{ \left\{ 1,2,3,4,5,6,7\right\}}\)oznaczające przystanki. Ilość powtórzeń każdego z elementów oznacza ile osób wysiada na danym przystanku. Skoro każdy z elementów musi się znaleźć co najmniej 1 raz, to w tym 20-elementowym multizbiorze mamy \(\displaystyle{ \left\{ 1,2,3,4,5,6,7,...\right\}}\) i dla tych brakujących 13 miejsc dobieramy w sposób dowolny pozostałe elementy. Myślę, że takie rozumowanie jest poprawne?

[Hellbike]

ja moze pokaze wam liste zadan, zeby bylo jasne, na jakim poziomie jest to zadanie.




wiec... moze chodzi o pasazerow nierozroznialnych?

[mat_61]

Może .
Ale na 100% wie to tylko autor zadania (ewentualnie Ci którym przekazał tą wiedzę)

1. Sądząc po nagłówku do zadań z pewnością nie ma tutaj ograniczenia do szkoły średniej.

2. Ja osobiście przyjmuję założenie, że jeżeli w zadaniach jest mowa o osobach i nie ma nic skonkretyzowanego w samej treści zadania, to mówimy o bytach rozróżnialnych.

[Hellbike]

mam w skrypcie taki przyklad:

rozmieszczamy k rozroznialnych kul w n ponumerowanych komorkach tak, aby w pierwszej znalazlo sie dokladnie m( m<= k) kul. Ustal liczbe mozliwosci.

Jako wynik podano
\(\displaystyle{ {k \choose m} \cdot (n-1)^{k-m}}\)



czy to nie jest zle z tego samego powodu, co moje rozwiazanie poprzedniego problemu?

[mat_61]

Nie.

To jest dobre rozwiązanie i można powiedzieć standardowe (nie ma żadnych ograniczeń co do rozmieszczania kul w (n-1) komórkach - czyli mogą także pozostać puste komórki).

Pierwszy czynnik to wybór m kul do umieszczenia w pierwszej komórce (kombinacje bez powtórzeń).
Pozostaje (k-m) kul oraz (n-1) komórek i to są wariacje z powtórzeniami (każdej z kul przyporządkowujemy dowolną z komórek).