Involuție (matematică)

De la Wikipedia, enciclopedia liberă
Sari la navigare Sari la căutare
O involuție este o funcție that, when care aplicată de două ori se întoarce la punctul de pornire

În matematică, o involuție, sau o funcție involutivă, este o funcție f care este inversa ei înseși

f(f(x)) = x

pentru orice x din domeniul de definiție al f.[1] Echivalent, rezultatul obținut prin aplicarea funcției f de două ori este valoarea inițială.

Proprietăți generale[modificare | modificare sursă]

Orice involuție este bijectivă.

Funcția identitate () este exemplul banal de involuție. Exemple simple de involuții sunt înmulțirea cu −1 în aritmetică, elementul invers, conjugatul complex, anumite permutări[2] și complementul din teoria mulțimilor. Alte exemple sunt rotația cu o jumătate de tură, transpoziția de tip ROT13, cifrarea simetrică, cifrul Beaufort sau cifrul polialfabetic.

Numărul involuțiilor, inclusiv involuția identică, pe o mulțime cu elementele n = 0, 1, 2, ... este dat de o relație de recurență găsită de Heinrich August Rothe în 1800:

și for

Primii câțiva termeni ai acestui șir sunt 1, 1, 2, 4, 10, 26, 76, 232 (șirul OEIS A000085[3]); aceste numere se numesc numere de telefon⁠(d) și indică și numărul de tablouri Young[2] cu un număr de celule dat.[4] Compunerea gf a două involuții f și g este o involuție dacă și numai dacă operația este comutativă: gf = fg.[5]

Orice involuție pe un număr impar de elemente are cel puțin un punct fix. Mai general, pentru o involuție pe o mulțime finită de elemente, numărul de elemente și numărul de puncte fixe au aceeași paritate.[6]

Note[modificare | modificare sursă]

  1. ^ en Russell, Bertrand (), Principles of mathematics (ed. 2nd), W. W. Norton & Company, Inc, p. 426, ISBN 9781440054167 
  2. ^ a b Knuth, Donald E. (), Tratat de programarea calculatoarelor, vol 3: Sortare și căutare, Ed. Tehnică, p. 47 .
  3. ^ Șirul A000085 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
  4. ^ en Knuth, Donald E. (), The Art of Computer Programming, Volume 3: Sorting and Searching, Reading, Mass.: Addison-Wesley, pp. 48, 65, MR 0445948 .
  5. ^ en Kubrusly, Carlos S. (), The Elements of Operator Theory, Springer Science & Business Media, Problem 1.11(a), p. 27, ISBN 9780817649982 .
  6. ^ en Zagier, D. (), „A one-sentence proof that every prime p≡ 1 (mod 4) is a sum of two squares”, American Mathematical Monthly, 97 (2): 144, doi:10.2307/2323918, JSTOR 2323918, MR 1041893 .

Lectură suplimentară[modificare | modificare sursă]

  • en Ell, Todd A.; Sangwine, Stephen J. (). „Quaternion involutions and anti-involutions”. Computers & Mathematics with Applications. 53 (1): 137–143. arXiv:math/0506034Accesibil gratuit. doi:10.1016/j.camwa.2006.10.029. 
  • en Knus, Max-Albert; Merkurjev, Alexander; Rost, Markus; Tignol, Jean-Pierre (), The book of involutions, Colloquium Publications, 44, With a preface by J. Tits, Providence, RI: American Mathematical Society, ISBN 0-8218-0904-0, Zbl 0955.16001 
  • en Involution, Encyclopedia of Mathematics, EMS Press (Springer Verlag), 2001