szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 12 lut 2016, o 17:26 
Użytkownik

Posty: 101
Lokalizacja: Wro
W klasie jest 2n dzieci siedzących w n dwuosobowych ławkach. Jadą na wycieczke autokarem w którym jest 2n ponumerowanych miejsc. Miejsce 2i-1 jest obok miejsca 2i ( i tylko te miejsca sąsiadują). Nauczyciel chce zerwać więzi społeczne i żaden uczeń nie może siedzieć w autobusie obok kolegi z ławki. Na ile sposobów można tak usadzić uczniów w autokarze?
Pozdrawiam i z góry dziekuje za każdą pomoc.
Góra
Mężczyzna Offline
PostNapisane: 12 lut 2016, o 21:15 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
Możliwości podziału na pary 2n osób jest:

\frac{(2n)!}{2^nn!}

jeżeli teraz oznaczymy poprzez a_{n}

ilość możliwości rozsadzenia n par tak, żeby żadne dziecko nie siedziało w autobusie z dzieckiem
z klasy otrzymamy:

a_{1}=0

a_{2}=2

a_{3}=15-3 \cdot a_{2}-1=8

ogólnie:

a_{n}= \frac{(2n)!}{2^nn!} -\left[  {n \choose 1}a_{n-1}+{n \choose 2}a_{n-2}+{n \choose 3}a_{n-3}+...+1 \right]
Góra
Mężczyzna Offline
PostNapisane: 12 lut 2016, o 21:37 
Użytkownik

Posty: 101
Lokalizacja: Wro
kurcze próbuje ale chyba nie potrafie tego zrozumieć bez jakiegoś komentarza na czym polega rozwiązanie? w sensie jaki jest na to pomysł? Chodzi mi głownie o to ze np a _{1} = 0 a przeciez jedną parę mogę rozmiescic w autobusie na wiele sposobow. No chyba ze w tym a chodzi o to że jak mam tylko jedną parę dzieci to w sumie nie mam jak podzielic na inne pary. Wtedy jak mam 2 pary to moge ich przetasować wiec mam parę \left(a,b \right)\left(c,d \right) to mogę zrobic pary
\left(a,c \right) \left( b,d\right) i \left(a,d \right) \left(b,c \right). a dalej? skad sie bierze taki a nie inny wzór?
Góra
Mężczyzna Offline
PostNapisane: 13 lut 2016, o 14:19 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
Tak ale jedna para zakładam że siedzi razem, a rozwiązanie to sposób łączenia w pary tak, żeby żadna nie siedziała z tą osobą co siedzi w ławce w szkole.
Nie uwzględniam permutacji siedzeń.


Jeżeli masz jedną parę tylko to ta para siedzi w szkolnej ławce razem ale już w autobusie zgodnie z założeniem nie może siedzieć razem czyli:

a_{1}=0

a_{2}, a_{3} łatwo obliczyć na piechotę

Jak widzisz dla a_{2}=2 zgadza się z Twoimi obliczeniami,

a_{3}=8 co też łatwo możesz sprawdzić dalej to już rekurencja

W rekurencji tworzę zakazane pary a potem mnożę przez a_{k} czyli dozwolone pary

jak coś nie wiesz pytaj...
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ile jest sposobów utworzenia danej liczby  Matix16  4
 Ilość sposobów rozsadzenia osób  fa1thly  1
 Na ile sposobów może usiąść na ławce 7 osób  Grzesku  1
 Na ile sposobów dwie karty bez zwracania.  Tybias  1
 Na ile sposobów można przydzielić...  MrMarion  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl