Matematické Fórum

zbynek · 17. 11. 2009 22:12 — Editoval zbynek (29. 11. 2009 20:44)

Omlouvam se, za smazani nasledujiciho tematu, ale toto tema bylo zalozeno bez meho vedomi. Urcita osoba se nabourala do meho loginu a zalozila toto tema a ja si nepreji aby toto tema bylo zverejneno. Děkuji za pochopeni.

jelena · 18. 11. 2009 11:38

↑ zbynek:

Zdravím,

budoucí informatik by měl vědet, že pro to, aby vznikla odpověď, měla by být položena otázka - což v případě úvodního příspěvku v tématu není.

Tak já tedy položím otázku:

- je možné sestavovat i kratší slova, než osmipismenková?

- je možné pro vyloučení (například) nepovoleného slova AUTO použit tento postup _A_U_T_O_, mám tedy pěvně dany pozice pro uspořádání nepovolených pismen a na mezerý umístim ostatní pismena. Jak ošetřím, že na jednu mezeru mohu dat i více písmen?

Já opravdu nevím, proto jsou moje otázky - ale vy jste to možna měli ve cvičení.

Děkuji za doplnění a vysvětlení a doporučuji přečist si místní pravidla, zejména bod 4.

dreek · 19. 11. 2009 20:26

Máme tvořit slova pouze osmipísmenková ;-)

Já bych to zkusil řešit tak, že bych si spočítal počet slov kdy písmeno A bude na 1. - 5. pozici tzn. A _ _ _ A _ _ _ . Písmeno A na 3.pozici by již nevytvořilo podslovo AUTO.

//
A U T O _ _ _ _
A _ U _ _ T O_
_ A U T O _ _ _
_ _ A U T O _ _
_ _ _ A U T O _
_ _ _ _ A U T O
+++ písmena U T O mohou bý jakkoliv seřazeny a na jakékoliv pozici za písmenem A

Poté počet slov kdy písmeno U bude na 2. - 6. pozici. Písmeno U na 1. , 7. a 8. pozici by nevytvořilo podslovo AUTO.
- || - písmeno T na 3. - 7. pozici.
- || - písmeno O na 4. - 8. pozici.

To stejné s podslovy RUKA a HOD.
R na 1. - 5. pozici.
U na 2. - 6. pozici.
K na 3. - 7. pozici.
A na 4. - 8. pozici.

H na 1. - 6. pozici.
O na 2. - 7. pozici.
D na 3. - 8. pozici.

...

jelena · 20. 11. 2009 14:04

↑ dreek:

Zdravím a děkuji za příspěvek k problému (autor dotazu ovšem pořad nic?)

Při takovém "ručním" seřazení bych měla obavy, ať na nějakou pozici nezapomenu.

Ještě jen doplnění, ale to asi víš, že RUKA a AUTO v jednom slově spolu nebudou, ale RUKA a HOD nebo HOD a AUTO mohou se potkat v jednom slově (zejména HOD s AUTO - tak se to dokonce "přesmyčkuje"). Je to tak?

zdenek1 · 20. 11. 2009 14:48

↑ dreek:
Takže za předpokladu, že se tvoří osmipísmenná slova a každé písmeno použiju právě jednou.

Lepší počítání je: Vyberu čtyři pozice, na které umístím písmena AUTO. To můžu dělat ${8\choose4}$ způsoby. Jakmile mám vybranou jednu takovou čtveřici, písmena umístím jednoznačně. Zbylá písmena na zbylých pozicích můžou libovolně permutovat. Takže slov, která obsahují podslovo AUTO je $4!{8\choose4}$

Ostatní podobně.
HOD $5!{8\choose3}$
RUKA $4!{8\choose4}$
AUTO a RUKA $0$
AUTO a RUKA a HOD $0$
HOD a RUKA ${8\choose3}{5\choose4}$ (vyberu 3 pozice pro HOD a pak 4 pozice ze zbytku pro RUKA)
AUTO a HOD. Někam musím umísti sekvenci písmen $\{A,D,H,O,T,U\}$ . Vyberu tedy 6 pozic ${8\choose6}$ způsoby.
Jakmile je vyberu, jsou určeny _ _ _ _ O D. Nyní můžu čtyřmi způsoby umístit H. Jakmile to udělám, pozice písmen AUT je daná. Nakonec mi zbývají K R, ta mohou libovolně permutovat na 2 pozicích.
$4\cdot2!{8\choose6}$

Nyní spočítáš podle principu inkluze a exkluze počet "HOD nebo AUTO nebo RUKA" a odečteš od počtu všech možných slov ( $8!$ )

dreek · 24. 11. 2009 21:11

Děkuji za rady..
Prosím ještě o menší kontrolu ;)

výskyt podslov:

AUTO $4!{8\choose4}=1680$
HOD $5!{8\choose3}=6720$
RUKA $4!{8\choose4}=1680$
HOD A RUKA ${8\choose3}{5\choose4}=280$
AUTO A HOD $4\cdot2!{8\choose6}=224$
AUTO a RUKA $0$
AUTO a RUKA a HOD $0$

inkluze a exluze:

AUTO = |A| = 1680,
HOD = |B| = 6720,
RUKA = |C| = 1680,
HOD A RUKA = |B∩C| = 280,
AUTO A HOD = |A∩B| = 224,
AUTO A RUKA = |A∩C| = 0,
AUTO A HOD A RUKA = |A∩B∩C| = 0

|AUBUC| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|
|AUBUC| = 1680 + 6720 + 1680 - 224 - 0 - 280 + 0
|AUBUC| = 9576

8! - 9576 = 30744
Můžeme tedy sestavit 30744 slov.

dreek · 30. 11. 2009 10:29 — Editoval dreek (30. 11. 2009 10:37)

zbynek napsal(a):
Omlouvam se, za smazani nasledujiciho tematu, ale toto tema bylo zalozeno bez meho vedomi. Urcita osoba se nabourala do meho loginu a zalozila toto tema a ja si nepreji aby toto tema bylo zverejneno. Děkuji za pochopeni.

No to nevadí ;-)
Mi to téma dost pomohlo 8)
Pro ty, kdo hledají zadání..

Mějme písmena A,D,H,K,O,R,T,U. Kolik různých slov můžeme sestavit z těchto písmen, pokud tato slova nesmí obsahovat "podslova" AUTO, RUKA a HOD (například hAdUrTkO je nepřípustné slovo).

OT: jinak trošku tragédie Zbynku :D Založil sis účet 17.11.2009 a v ten den už ti ho někdo naboural a založil úplně nedůležité vlákno o kombinatorice :D pobavil jsi ;)
... ale jo, snad to tady všichni z VŠB neobjeví co? ;D

zdenek1 · 30. 11. 2009 10:37

↑ dreek:
Numericky jsem to nekontroloval, ale PIE máš dobře, tak snad jo.

osel · 02. 12. 2009 20:15

Dobrý den, chtěl bych Vás poprosit o odpověď, jestli je tento příklad vypočten správně, respektive výpočet Dreeka. Děkuji. Vážím si Vaší případné odpovědi.

dreek · 03. 12. 2009 13:58

Já bych vzal postup, propočítal to znova a jestli se shodnem na výsledku, třeba to bude dobře ;-)

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

Gabbo · 07. 12. 2009 11:17

Postupoval jsem stejne a dopocital jsem se k stejnym vysledku. Takze potvrzuji.

Matematické Fórum

#1 17. 11. 2009 22:12 — Editoval zbynek (29. 11. 2009 20:44)

Kombinatorika

#2 18. 11. 2009 11:38

Re: Kombinatorika

#3 19. 11. 2009 20:26

Re: Kombinatorika

#4 20. 11. 2009 14:04

Re: Kombinatorika

#5 20. 11. 2009 14:48

Re: Kombinatorika

#6 24. 11. 2009 21:11

Re: Kombinatorika

#7 30. 11. 2009 10:29 — Editoval dreek (30. 11. 2009 10:37)

Re: Kombinatorika

zbynek napsal(a):

#8 30. 11. 2009 10:37

Re: Kombinatorika

#9 02. 12. 2009 20:15

Re: Kombinatorika

#10 03. 12. 2009 13:58

Re: Kombinatorika

#11 07. 12. 2009 11:17

Re: Kombinatorika

Zápatí