Dismutácia (matematika)

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

Dismutácia je matematický pojem, ktorý modeluje intuitívnu predstavu takého preusporiadania súboru vecí, po ktorom neostane ani jedna vec na svojom pôvodnom mieste. Formálne je dismutácia množiny A definovaná ako taká jej permutácia, ktorá nemá pevný bod.

Napríklad, existuje 6 rôznych permutácií trojprvkovej množiny {A,B,C}. Sú to

\textstyle\left( {A\atop A} {B\atop B} {C\atop C} \right), \left( {A\atop A} {B\atop C} {C\atop B} \right), \left( {A\atop B} {B\atop A} {C\atop C} \right), \left( {A\atop B} {B\atop C} {C\atop A} \right), \left( {A\atop C} {B\atop A} {C\atop B} \right), \left( {A\atop C} {B\atop B} {C\atop A} \right).

Ale iba 2 z nich sú dismutácie. Konkrétne

\textstyle\left( {A\atop B} {B\atop C} {C\atop A} \right), \left( {A\atop C} {B\atop A} {C\atop B} \right).

Počet dismutácií[upraviť | upraviť zdroj]

Podobne ako v prípade permutácii, aj počet rôznych dismutácií danej množiny zavisí iba od počtu jej prvkov. Napríklad:

  • Prázdna, čiže 0-prvková množina, má práve jednu dismutáciu. Je to prázdne zobrazenie, ktoré ničomu nič nepriradí a teda nemôže mať ani pevný bod.
  • Jednoprvková množina nemá žiadnu dismutáciu. Jediná jej permutácia je totiž identita a jej pevným bodom je každý prvok, na ktorom je definovaná.
  • Horeuvedený príklad ukazuje, že existujú dve dismutácie trojprvkovej množiny.

Vo všeobecnosti možno počet dismutácií !n ľubobolnej n-prvkovej množiny vypočítať pomocou rekurentného vzťahu

!\,n=\textstyle(n-1)\left(!\,(n-1)+!\,(n-2)\right)

s počiatočnou podmienkou !0=1 a !1=0. Číslo !n sa nazýva subfaktoriál čísla n. Subfaktoriály celých čísel od 0 po 13 tvoria postupnosť

1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, ...

Pozri aj[upraviť | upraviť zdroj]