Matematické Fórum

Merlí · 14. 11. 2009 11:25

Dobré dopoledne
Zadání úlohy je následující: Máme posloupnost nul a jedniček délky 2*47, přičemž obsahuje právě 47 nul a právě 47 jedniček. Kolika způsoby je lze uspořádat, pokud jsou kombinace lišící se posunutím nerozlišitelné? (Tedy např. u psp délky 4 jsou posloupnosti 0011, 1001, 1100 , 0110 stejné.)
Díky za pomoc

AvMrk · 14. 11. 2009 13:14

Představil bych si to jako když usazuješ jedničky a nuly ke kulatému stolu. První prvek si zafixuješ a od něho potom spočítáš počet všech možností, tzn:

řekněme, že jednu jedničku budeč mít zafixovanou "v čele kulatého stolu", potom můžeš uspořádat vše jako permutaci s opakováním 46 a 47 prvků - tj kombinační číslo, tj (46 + 47)!/(46!*47!)

Olin · 14. 11. 2009 13:23 — Editoval Olin (14. 11. 2009 13:36)

Smí se použít Bursideovo lemma?

Pokud ano, tak je to docela snadné. Možné operace s posloupností (lépe se to představuje jako nějaké kolečko) jsou identita a otočení o 1 až 93. Možností, jak jen tak rozmístit jedničky a nuly bez ohledu na symetrie, je ${{2 \cdot 47} \choose 47}$ . Velikost grupy operací je $|G| = 2\cdot 47$ . Identita nechá nezměněných všech ${{2 \cdot 47} \choose 47}$ možných seřazení. Otočení o sudý počet nechá nezměněna pouze dvě seřazení - jedničky a nuly na střídačku - a lichá (kromě 47) nenechají nezměněné nic (oboje plyne z toho, že 47 je prvočíslo, tudíž jakékoliv liché číslo má NSD s $2\cdot 47$ jedničku a jakékoliv sudé dvojku, takže při lichém otočení by musely být sousední členy stejné, to však nelze). Otočení o 47 je jakoby středová symetrie, tedy ty, které by to zanechávalo nezměněné, bychom vytvořili tak, že bychom volili jen členy v jedné půlce a v druhé by byly stejné. To však nelze, protože jedna půlka má 47 členů a mezi ty nemůžeme rozdělit nuly a jedničky tak, aby jich byl stejný počet (47 je liché), tedy i 47 nenechává nezměněna žádná uspořádání.

Výsledek tedy je
$\frac{1}{2 \cdot 47} ${{2 \cdot 47} \choose 47} + 0 + 2 + 0 + 2 + \dots + 2 + 0 $ = \frac{1}{2 \cdot 47} ${{2 \cdot 47} \choose 47} + 2 \cdot 46 $$ .

Ovšem ať to po mně radši překontroluje nějaký odborník…

↑ AvMrk:
Takto ale nemáš ošetřeno to, že např. pro délku 4 je 1001 to samé jako 1100.

Merlí · 14. 11. 2009 13:42

Bursideovo lemma mi nic neříká, takže to bych radši nepoužíval :-)
Každopádně předchozí řešení chápu. Když jsem se pokoušel to řešit, tak jsem zkoušel nejprv počítat všechny permutace a pak nějakým způsobem od nich odečíst ty totožné posloupnosti. Zafixovat 1 bod mě nenapadlo. Děkuju moc

Olin · 14. 11. 2009 13:52 — Editoval Olin (14. 11. 2009 13:56)

↑ Merlí:
Jenže ono to tak opravdu není. Kdybych se pohyboval jen na délce 6, tak tento postup znamená, že si zafixuji 1xxxxx a za ty x libovolně dosazuji dvě jedničky a tři nuly. Takže mi takto vznikne jak 111000, tak 100011, což jsou ale stejné posloupnosti. Stejný argument je i u těch délky $2 \cdot 47$ , protože

1000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111

je stejné jako

1111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000.

Merlí · 14. 11. 2009 14:18

↑ Olin:
Ufff, no, máš pravdu.
Koukal jsem na tvoje řešení a snad mu i rozumím, každopádně se obávám, že já potřebuju spíš čistě kombinatorický postup. To lemma přesahuje vše, co jsme zatím v algebře dělali, takže jeho použití je dost sporné, protože ho neumím dokázat a stejně tak neznám všechnu tu teorii, která je "pod ním".

Olin · 14. 11. 2009 14:38

Ještě se nad tím zamyslím. Snad by to nemuselo být až tak těžké udělat kombinatoricky. Základní idea je, že jich je jakoby ${{2 \cdot 47} \choose 47}$ , ale každá se tam vyskytuje i se svými posunutími, takže bychom to jako chtěli dělit $2 \cdot 47$ . Jen tam musíme ošetřit ty, jejichž posunutí jsou ony samy - to budou právě ty "na střídačku"…

Merlí · 14. 11. 2009 14:50

↑ Olin:
Jj, tímhle směrem už jsem se právě ubíral dřív, akorát jsem to nedokázal dotáhnout do konce. To, že celkem jich je 93 nad 47 vím, ale nedokázal jsem spočítat, kolik jich bude duplicitních.

Olin · 16. 11. 2009 14:43

Tak snad by to mohlo být takto (vede to na stejnou hodnotu, jako výpočet pomocí BL): když už víme, že jediný problémový případ jsou posloupnosti typu 10101010… (všechny ostatní se při nějakém pootočení změní na jinou posloupnost), spočítáme, kolik je těch "neproblémových". Těch je ${{2 \cdot 47} \choose 47}-2$ (ta dvojka se odečte za dvě problémové - 01010101… a 101010…). Protože mezi těmito připadá ke každé dalších $2\cdot 47 - 1$ takových, které se liší pouze otočením, dostáváme dohromady $\frac{1}{2 \cdot 47} \left ( {{2 \cdot 47} \choose 47}-2 \right )$ posloupností. K těm ovšem ještě musíme připočíst ty problémové - ty byly dvě, jenže ty dvě se od sebe liší pouze otočením, takže nám dají ve výsledku jednu. Celkem tedy $\frac{1}{2 \cdot 47} \left ( {{2 \cdot 47} \choose 47}-2 \right ) + 1$ posloupností.

Merlí · 17. 11. 2009 14:43 — Editoval Merlí (17. 11. 2009 15:30)

Hmm, to zní docela rozumně. Akorát ještě jedné věci nerozumím - neměl by být jmenovatel tedy 2*47 - 1? Nebo kam se poděla ta mínus jednička?
//Edit: už chápu, díky moc

Matematické Fórum

#1 14. 11. 2009 11:25

Kombinatorika - počítání pozic

#2 14. 11. 2009 13:14

Re: Kombinatorika - počítání pozic

#3 14. 11. 2009 13:23 — Editoval Olin (14. 11. 2009 13:36)

Re: Kombinatorika - počítání pozic

#4 14. 11. 2009 13:42

Re: Kombinatorika - počítání pozic

#5 14. 11. 2009 13:52 — Editoval Olin (14. 11. 2009 13:56)

Re: Kombinatorika - počítání pozic

#6 14. 11. 2009 14:18

Re: Kombinatorika - počítání pozic

#7 14. 11. 2009 14:38

Re: Kombinatorika - počítání pozic

#8 14. 11. 2009 14:50

Re: Kombinatorika - počítání pozic

#9 16. 11. 2009 14:43

Re: Kombinatorika - počítání pozic

#10 17. 11. 2009 14:43 — Editoval Merlí (17. 11. 2009 15:30)

Re: Kombinatorika - počítání pozic

Zápatí