Matematické Fórum

bojga · 25. 10. 2012 21:47

Prosím o radu s příkladem: Kolika způsoby lze usadit n manželských párů do jedné řady v níž je 2n míst, aby žádný manželský pár neseděl vedle sebe.
Lze určitě řešit pomocí principu inkluze a exkluze,ale jak? Děkuji

Andrejka3

↑ bojga:
Ahoj,
takto:
$N=\{\text{uspořádání};\;\text{ ani jeden par nestoji vedle sebe}\}$
$M=\{\text{uspořádání};\; \text{aspon jeden par stoji vedle sebe}\}$
$|N|=(2n)! - |M|$
Očíslujme páry - tj. pojmenujme je $1,2,\dots ,n$ .
$M_i:=\{\text{uspořádání};\;\text{par 'i' stoji vedle sebe}\}$
$M=\bigcup_{i=1}^nM_i$ . Pro PIE je nutno znat:
$c_k=\left| \bigcap_{j=1}^kM_j \right|$ pro $k=1,\dots ,n$ . Toto cislo nezavisi na konkretnich parech, pouze na poctu pruniku.
Spocitas-li $c_k$ , mas vyhrano.

Počítání $c_k$

Autor skryl část textu. Zobrazit/skrýt!

edit: oprava kombinac. cisla

Andrejka3

↑ Andrejka3:
Takže to po aplikaci PIE vychází

Autor skryl část textu. Zobrazit/skrýt!

Teď, jestli bych mohla se zeptat, když je to podobný příklad:
Jak se změnit postup, pokud je zadání:
Spočtěte kolika způsoby lze rozsadit n manželských párů ke kulatému stolu tak, aby (žádný - čeština) (každý - matika) pár neseděl vedle sebe.
Prosím, poraďte.

JohnPeca18

↑ Andrejka3:
Myslim, ze to mas dobre, len by som zjednodusil uvahu o tom, kolkymi sposobmi usadis k paru vedle sebe. Staci si predstavit, ze ten par, ktery sedi vedle sebe, tak se zluci do jedneho prvku. A pak permutujem posloupnost i se sloucenymi prvky. Tobe to nakonec i vychazi protoze
$k!(2n-2k)!{2n-k \choose k} = (2n-k)!$

Pri okrouhlem stolu nam vsak vadi to, ze nektere permutace nam daj stejne usporadani az na otoceni stolem.
takovych otoceni je 2n-1. Takze celkove mnozstvi usporadani bude $\frac{(2n)!}{2n-1}$ . Dal pri pocitani v PIE nebudeme mit (2n-k)! usporadani pri k parech ale $\frac{(2n-k)!}{2n-k}$ . Takhle se nam ale nezapocitaji posloupnosti, kde jeden z paru sedi na 1.miste a druhy z paru na (2n).tom miste. Takovych moznosti je k pro kazde usporadani.

Takze v tvem znaceni bych upravil $c_k=2^k\frac{(2n-k)!}{2n-k-1}+k2^k\frac{(2n-k)!}{2n-k-1}$

Ale este se na to podivej, jestli to je spravne.

Edit: Upravil sem este v zlomkoch -1.

Andrejka3

↑ JohnPeca18:
Aha. To je tedy rozhodně jednodušší. Jen bych neříkala, že je náhoda, že mi to vyšlo :)

Pri okrouhlem stolu nam vsak vadi to, ze nektere permutace nam daj stejne usporadani az na otoceni stolem.

To asi záleží na zadání - buď to můžu chápat jako problém v středově symetrické místnosti, nebo ne. Jakože budu počítat i ta uspořádání, která dostanu z jiných pouze otočením.
Moc děkuji za odpověď! V průběhu dne to zkontroluju.

Edit: Myslím, že to je v pořádku. Díky za vysvětlení.

bojga · 30. 10. 2012 15:10

↑ Andrejka3:

moc děkuji za pomoc :-)

Matematické Fórum

#1 25. 10. 2012 21:47

princip inkluze a exkluze

#2 26. 10. 2012 11:42 — Editoval Andrejka3 (26. 10. 2012 20:36)

Re: princip inkluze a exkluze

#3 26. 10. 2012 20:41 — Editoval Andrejka3 (26. 10. 2012 21:14)

Re: princip inkluze a exkluze

#4 27. 10. 2012 11:53 — Editoval JohnPeca18 (28. 10. 2012 02:12)

Re: princip inkluze a exkluze

#5 27. 10. 2012 12:00 — Editoval Andrejka3 (27. 10. 2012 19:13)

Re: princip inkluze a exkluze

#6 30. 10. 2012 15:10

Re: princip inkluze a exkluze

Zápatí