W klasie jest \(\displaystyle{ 2n}\) dzieci siedzących w \(\displaystyle{ n}\) dwuosobowych ławkach. Jadą na wycieczke autokarem w którym jest \(\displaystyle{ 2n}\) ponumerowanych miejsc. Miejsce \(\displaystyle{ 2i-1}\) jest obok miejsca \(\displaystyle{ 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.
Na ile sposobów można rozsadzić dzieci
-
TrzyRazyCztery
- Użytkownik
- Posty: 101
- Rejestracja: 24 maja 2014, o 17:53
- Płeć: Mężczyzna
- Lokalizacja: Wro
- Podziękował: 27 razy
- Pomógł: 1 raz
-
arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Na ile sposobów można rozsadzić dzieci
Możliwości podziału na pary \(\displaystyle{ 2n}\) osób jest:
\(\displaystyle{ \frac{(2n)!}{2^nn!}}\)
jeżeli teraz oznaczymy poprzez \(\displaystyle{ a_{n}}\)
ilość możliwości rozsadzenia n par tak, żeby żadne dziecko nie siedziało w autobusie z dzieckiem
z klasy otrzymamy:
\(\displaystyle{ a_{1}=0}\)
\(\displaystyle{ a_{2}=2}\)
\(\displaystyle{ a_{3}=15-3 \cdot a_{2}-1=8}\)
ogólnie:
\(\displaystyle{ 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]}\)
\(\displaystyle{ \frac{(2n)!}{2^nn!}}\)
jeżeli teraz oznaczymy poprzez \(\displaystyle{ a_{n}}\)
ilość możliwości rozsadzenia n par tak, żeby żadne dziecko nie siedziało w autobusie z dzieckiem
z klasy otrzymamy:
\(\displaystyle{ a_{1}=0}\)
\(\displaystyle{ a_{2}=2}\)
\(\displaystyle{ a_{3}=15-3 \cdot a_{2}-1=8}\)
ogólnie:
\(\displaystyle{ 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]}\)
-
TrzyRazyCztery
- Użytkownik
- Posty: 101
- Rejestracja: 24 maja 2014, o 17:53
- Płeć: Mężczyzna
- Lokalizacja: Wro
- Podziękował: 27 razy
- Pomógł: 1 raz
Na ile sposobów można rozsadzić dzieci
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 \(\displaystyle{ 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ę \(\displaystyle{ \left(a,b \right)\left(c,d \right)}\) to mogę zrobic pary
\(\displaystyle{ \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?
\(\displaystyle{ \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?
-
arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Na ile sposobów można rozsadzić dzieci
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:
\(\displaystyle{ a_{1}=0}\)
\(\displaystyle{ a_{2}, a_{3}}\) łatwo obliczyć na piechotę
Jak widzisz dla \(\displaystyle{ a_{2}=2}\) zgadza się z Twoimi obliczeniami,
\(\displaystyle{ a_{3}=8}\) co też łatwo możesz sprawdzić dalej to już rekurencja
W rekurencji tworzę zakazane pary a potem mnożę przez \(\displaystyle{ a_{k}}\) czyli dozwolone pary
jak coś nie wiesz pytaj...
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:
\(\displaystyle{ a_{1}=0}\)
\(\displaystyle{ a_{2}, a_{3}}\) łatwo obliczyć na piechotę
Jak widzisz dla \(\displaystyle{ a_{2}=2}\) zgadza się z Twoimi obliczeniami,
\(\displaystyle{ a_{3}=8}\) co też łatwo możesz sprawdzić dalej to już rekurencja
W rekurencji tworzę zakazane pary a potem mnożę przez \(\displaystyle{ a_{k}}\) czyli dozwolone pary
jak coś nie wiesz pytaj...