Matematické Fórum

3. Permutace je prosté zobrazení konečné množiny X do sebe, pokud je tam jeden cyklus (více zde: http://cs.wikipedia.org/wiki/Cyklus_%28algebra%29, http://en.wikipedia.org/wiki/Cyclic_permutation), tak víš, že se prvek nezobrazí sám na sebe, proto u "prvního" výběru máš n-1 možností, u dalšího n-2, ... 1 Takže výsledek je (n-1)!

Mimochodem pokud jde o ten řád permutace, chápu jej správně tak, že je to nejmenší číslo takové, že bylo-li by jen o 1 větší, začaly by se permutace opakovat?

K příkladu 2: Je správně úvaha, že všech množin A je 2^n, všech množin B také (jedná se o standardní podmnožiny). Tedy celkově 2^(2n) dvojic. Nyní zbývá jen odečíst všechny ty, které mají velikost průniku různou od čísla 1. Jejich počet mi ale nedá spát...

Pravidlo "jedno téma=jeden příklad" má své opodstatnění.
Takže to shrňme:

První sada
-------------
1. Najdu všechny cykly. Začnu z jedničky, kouknu, kam se mi zobrazí, pak zjistím, kam se zobrazí její obraz, kam obraz jejího obrazu...
po nějaké době se dostanu zpět na jedničku. U všech čísel, která jsou v tomto cyklu si zapamatuji, že jsem jimi prošel. Navíc si uložím délku cyklu. Pak najdu první doposud neprocházené číslo a od něj hledám další cyklus, opět si uložím jeho délku... až najdu všechny délky cyklů, spočítám jejich nejmenší společný násobek. Hledání cyklů běhá v čase O(N), kde N je počet prvků, algoritmus pro společný násobek v čase O(NlogN)

2. Souhalas se Saturdayem -- (n-1)!

Druhá sada
--------------

1. Pokud je to míněno jako zápis cyklem, pak má permutace jeden cyklus délky devět a má i řád 9. Pokud je to míněno jako řádkový zápis, pak  přepsáno do cyklů to dává (1 2 3) (4 5) (6 7 8 9), řád tohoto je nejmenší společný násobek čísel 2,3,4, tedy 12.

2. Určitě bych nepoužil symbol "náleží" ale "je podmnožinou". K řešení: n způsoby vybereme, který prvek je společný množinám A,B. Pro každý z n-1 zbylých máme pak 3 možnosti: zařadit do A, zařadit do B, nezařadit nikam. Celkem máme možností.