Matematické Fórum

Cermix · 19. 04. 2010 19:57

Zdravím,
chtěl bych se zeptat. mám několik uspořádaných dvojic čisel. (např (1,1)(1,2)(1,3)(3,2)(2,3)(3,3)(3,1)(2,1))
No a mě by zajímalo jak vypočtu počet uspořádání těchto uspořádaných dvojic tak aby druhé číslo uspořádané dvojice bylo stejné jako první číslo další uspořádané dvojice (prostě počet variací které budou vypadat asi takhle:" (1,1)(1,2)(2,3)(3,2) atd.." A taky by měla být spolněna podmínka aby druhé číslo v celé té řadě odpovídalo prvnímu číslu první uspořádané dvojice.
Děkuji za řešení. Samotného mě bohužel nic nenapadlo, zhola nic :(

Doxxik · 19. 04. 2010 20:28

Zdravím,

(jestli jsem to dobře pochopil,) představil bych si to jako domino. Zkusil jsem se tedy zeptatstrýce na matematiku v dominu a našel mi třeba tohle (nečetl jsem, pouze dávám odkaz; nejlepší nejspíš bude zeptatse ho sám).

Cermix · 19. 04. 2010 20:45

↑ Doxxik:
No teda, dík. zdá se, že mi to dost pomohlo.

Doxxik · 19. 04. 2010 22:26

↑ Cermix:
To jsem moc rád :)

Cermix · 20. 04. 2010 10:56

↑ Doxxik:
Tak jsem to pročítal.. No a zjistil jsem, že je mi to.. na houby :D Asi jsem špatně řekl zadání. Když vezmeme asociaci s dominem, tak bych chtěl najít počet všech řešení domina kde první a poslední dílek mají stejnou hodnotu. taky jsem hledal na netu, ale nic jsem nenašel.. a tento problém mi připadne až moc.. komplexní :D takže kdyby někdo aspoň naznačil postup, tak bych byl vděčen :) Ale jinak dík Dominiku za snahu :D

Pavel Brožek

Řekl bych, že hledáš počet Eulerovských tahů v orientovaném grafu. (Čísla jsou vrcholy, uspořádané dvojice hrany.)

http://cs.wikipedia.org/wiki/Eulerovsk%C3%BD_tah

Já ti v tomhle moc neporadím, protože o tom moc nevím.

Cermix · 20. 04. 2010 15:38

↑ BrozekP:
hm, hned jsem chytřejší :D:D

Cermix · 20. 04. 2010 18:09

Nějaké další nápady?

petrkovar · 20. 04. 2010 21:43

↑ BrozekP:To je správný postřeh a dal by se dotáhnout do konce. Jedná se o oritentovaný digraf se smyčkami.
Také si všimneme, že každým vrcholem musíme projít právě třikrát a vždy se vrátíme do výchozího vrcholu - jinak o nejde, pokud máme použít všechny uspořádané dvojice.
To putování můžeme Co kdyby se spořítaly všechny permutace s opakováním tří prvků (1,2,3), každý se třemi kopiemi a odečetly by se ty možnosti, které nemohou nastat, jako:
1) tři stejné prvky bezprostředně za sebou 1,1,1
2) Dvě stejné dvojice *někdy* za sebou
3) ...?
Mám ale pocit, že vhodným sformulováním úlohy to půjde vypočítat snadno bez rozebírání mnoha případů.

petrkovar · 20. 04. 2010 21:48

Nebo bysme mohli nejprve ignorovat smyčky a rozmyslet si, že zvývajích 6 hran můžeme projít v pořadí
a) 1,2,3,1,3,2,1
b) 1,2,1,3,2,3,1
c) 1,2,3,2,1,3,1
d) nezapoměl jsem na nic?
Pro každou možnost rozlišíme několik permutací symbolů 1,2,3 a potom si stačí zdůvodnit, že existuje 2*2*3 (je to dobře?) možností jak přidat ty smyčky (i,i).

Cermix · 21. 04. 2010 10:35

Nejsem si úplně jistý jestli vidím analogii mezi těma smyčkama (nebo těmi smičkami?...) a dominem.. jediné co jsem z těch elerových tahů pochopil je to město královec, že nelze přejít přes všechny mosty aniž bychom přes některý přešli dvakrát :D

petrkovar

↑ Cermix:Analogie je vybudována takto:
máme tři vrcholy (někdo říká uzky) a mezi každými dvěma existuje orientovaná hrana (někdo říký šíp nebo šipka). naví u každého vrcholu je orientovaná smyčka.
Těch šipek a smyček je dohromady 6+3=9, stějně jako uspořádaných dvojic $(x,y)$ , kde $x,y\in\{1,2,3\}$ . No a seřazení kostek domina odpovídá orientovanému tahu v tomto grafu. Kolik je seřazení kostek? Tolik, kolik existuje těch otevřených tahů. Odvození počtu jsem naznačil výš.
(ony ty tahy jsou sice uzavřené, ale podle smyslu úlohy s dominem je i uzavřený tak považován za otevřený)

Cermix · 22. 04. 2010 10:18

↑ petrkovar:
A co když máme domino o šedesáti kostkách ve kterém jsou čísla od jedničky do pětí (na každé straně kostky samozřejmě) a některé kostky se opakují?

Matematické Fórum

#1 19. 04. 2010 19:57

kombinatorika

#2 19. 04. 2010 20:28

Re: kombinatorika

#3 19. 04. 2010 20:45

Re: kombinatorika

#4 19. 04. 2010 22:26

Re: kombinatorika

#5 20. 04. 2010 10:56

Re: kombinatorika

#6 20. 04. 2010 13:51 — Editoval BrozekP (20. 04. 2010 13:53)

Re: kombinatorika

#7 20. 04. 2010 15:38

Re: kombinatorika

#8 20. 04. 2010 18:09

Re: kombinatorika

#9 20. 04. 2010 21:43

Re: kombinatorika

#10 20. 04. 2010 21:48

Re: kombinatorika

#11 21. 04. 2010 10:35

Re: kombinatorika

#12 21. 04. 2010 21:41 — Editoval petrkovar (21. 04. 2010 21:42)

Re: kombinatorika

#13 22. 04. 2010 10:18

Re: kombinatorika

Zápatí