Matematické Fórum

Ahoj, prověř si svojí hypotézu na nějakém jednoduchém příkladě, třeba .

Úplně z cesty neuvažuješ, ale všechno sis neohlídal. A nějak jsem doufal, že když si vypíšeš všechny permutace 3 (nebo 4) prvků a poctivě spočítáš pevné body, tak to bude snazší než nějaké vysvětlování. V té své úvaze totiž zafixuješ 1 bod, ale už nehlídáš, aby se další pevný bod neobjevil v té permutaci zbytku.

Vidím, že téma je už vyřešené, ale přihodím svůj výtvor. Jednak pro kompletnost a druhak tím třeba vyprovokuju někoho, kdo mi napíše, že se v tom hrabu hrozně neobratně a přidá nějaké úžasné a jednoduché řešení, které ta úloha třeba má.

Koment k předchozímu vývoji tématu:

K problému. Můj aktuální pocit je, že řešení půjde naindukovat.
Vydělíme si z našich prvků jeden červený, n-tý. Libovolnou permutaci n prvků lze jednoznačně vyjádřit tak, že zpermutujeme n-1 prvků a n-tý buď necháme na místě, nebo ho v závěru prohodíme s některým z prvních n-1 prvků.

Zřejmě {počet permutací n prvků s 1 p.b.} = n*{počet permutací n-1 prvků s 0 p.b.}.
A počet permutací s 0 p.b. si naindukujeme:



Z řešení této jednoduché rekurence už prakticky vypadne výsledek. Je jasné, že nějaká taková rekurence by se vymyslela i pro libovolných k pevných bodů.


Pak mě taky napadá, že pro obecných k p.b. by možná byla snazší cesta přes úvahu, že každá permutace jde (až na nějaké pořadí) jednoznačně rozložit na disjunktní cykly. Pokud by to bylo průchozí, tak by se tam asi lépe postihnul koncept "právě k pevných bodů". Ale nevím. Jen nápad. Já se do toho určitě pouštět nebudu.