Matematické Fórum

Makrofág · 16. 12. 2015 22:26

Zdravím vás!

Mám úlohu, se kterou si dost dlouho už lámu hlavu, ale moje pokusy o zdolání byly všechny neúspěšné. Prosím o pomoc.

Na kolotoči sedí $n$ dětí ( $n\ge 2$ ), počáteční rozmístění je na obrázku. Určete, kolika způsoby lze děti rozmístit tak, aby nové rozmístění neobsahovalo tyto uspořádané dvojice: $(1,2), (2,3), (3,4), (4,5), \ldots , (n-1,n), (n,1)$
V počátečním stadiu kolotoč (při prvním rozesazení) vypadá popořadě jako posloupnost čísel (dětí) od jedničky do $n$ , na $n$ pak navazuje do cyklu jednička. Přečetl jsem si jeden postup, kde se ten počet rozesazení počítá jako množina vzniklá průnikem všech možných rozesazení, kde v jednom rozesazení není $(1,2)$ , v dalším není $(2,3)$ atd.

Řešení vypadá takto: $(n-1)!$ (což je počet všech rozesazení jakožto permutací dětí)....tedy:
$(n-1)!-n.nad.jednou*(n-2)!+n.nad.druhou*(n-3)!+\ldots +(-1)^{n-1}*n.nad.(n-1)*0!+(-1)^{n}*n.nad.n$
Vidím v tom inkluzi exkluzi, ale nevidím přesně, co se počítá. Hlavně se nevyznám v těch kombinačních číslech. Prosím nakopněte mě. Dík.

check_drummer · 17. 12. 2015 00:14

↑ Makrofág:
Ahoj, když je to PIE, neměla by se spíš uvažovat ta rozesazení, která naopak (1,2) obsahují? (A podobně další.)

check_drummer · 17. 12. 2015 00:17

Jinak komb. číslo ${n \choose k}$ se t tex píše {n \choose k}. Škoda, že tak důležitý symbol není v nápovědě symbolů vpravo.

Makrofág · 17. 12. 2015 01:11

↑ check_drummer:
Ano, máš pravdu. Přepsal jsem se. Počítá se to jako průnik množin, kde tam ty uspořádané dvojice jsou. Co znamenají ta kombinační čísla v řešení?

check_drummer · 18. 12. 2015 16:49

↑ Makrofág:
Podle mě by to měl být počet způsobů, kterým lze zvolit konkrétní dvojice - např. je-li těchto dvojic k, tak je tam podle toho ${n \choose k}$ . Jenomže podle mého je problém v tom, že některé dvojice mohou mít společné prvky a tak si nejsem jist, zda je ten vzoreček správně...

Matematické Fórum

#1 16. 12. 2015 22:26

Kombinatorika - n dětí na kolotoči

#2 17. 12. 2015 00:14

Re: Kombinatorika - n dětí na kolotoči

#3 17. 12. 2015 00:17

Re: Kombinatorika - n dětí na kolotoči

#4 17. 12. 2015 01:11

Re: Kombinatorika - n dětí na kolotoči

#5 18. 12. 2015 16:49

Re: Kombinatorika - n dětí na kolotoči

Zápatí