Don't take life too seriously: it's just a temporary situation

Involuzioni (numero di)

Matematica combinatoria  Teoria dei grafi 

Il numero di involuzioni In è il numero di permutazioni di n oggetti, tali che applicando due volte la permutazione si ritorna all’ordine iniziale, cioè il numero di permutazioni ottenute scambiando il posto di alcune coppie disgiunte di oggetti (anche nessuna).

Per esempio, le permutazioni del genere di 4 oggetti sono:

  • A, B, C, D;

  • B, A, C, D;

  • C, B, A, D;

  • D, B, C, A;

  • A, C, B, D;

  • A, D, C, B;

  • A, B, D, C;

  • B, A, D, C;

  • C, D, A, B;

  • D, C, B, A.

 

I numeri di involuzioni sono anche detti “numeri di telefonate”, perché rappresentano le differenti combinazioni di telefonate simultanee tra n utenti, ciascuno dei quali comunichi con al massimo un altro.

La figura seguente mostra le combinazioni di telefonate simultanee possibili tra 4 utenti.

 

Le combinazioni di telefonate simultanee possibili tra 4 utenti 

 

La figura mostra anche che In è il numero di “matching” in un grafo completo con n nodi, ossia il numero di sottoinsiemi degli archi che non contengano due archi con un nodo in comune.

 

Il numero di involuzioni In è il numero di tableau di Young standard con n elementi, cioè il numero di modi per inserire i numeri da 1 a n nelle caselle di uno schema rettangolare, uno per casella, lasciando caselle vuote solo all’estremità destra delle righe e all’estremità inferiore delle colonne, in modo che i numeri siano in ordine crescente lungo ogni riga e lungo ogni colonna.

I diagrammi del genere con fino a 4 righe sono i seguenti.

1

2

3

4

 

1

2

3

4

 

 

 

1

2

4

3

 

 

 

1

3

4

2

 

 

 

1

2

3

4

 

1

3

2

4

 

1

4

2

 

3

 

 

1

3

2

 

4

 

 

1

2

3

 

4

 

 

1

2

3

4

 

Il problema di stabilire il numero di involuzioni per n oggetti fu studiato per la prima volta nel 1800 da Heinrich August Rothe (Dresda, Germania, 3/9/1773 – 1842), che dimostrò che In soddisfa la ricorrenza I0 = I1 = 1, In = In – 1 + (n – 1)In – 2.

 

Il numero di involuzioni può essere calcolato anche con la formula Formula per il calcolo del numero di involuzioni.

In è anche la somma dei coefficienti del polinomio di Hermite modificato Hen(x) e Formula per il calcolo del numero di involuzioni.

 

Asintoticamente In tende a Formula asintotica per I(n).

 

La funzione generatrice esponenziale dei numeri di involuzioni è Funzione generatrice esponenziale dei numeri di involuzioni.

 

La tabella seguente mostra i valori di In per n fino a 20.

n

In

0

1

1

1

2

2

3

4

4

10

5

26

6

76

7

232

8

764

9

2620

10

9496

11

35696

12

140152

13

568504

14

2390480

15

10349536

16

46206736

17

211799312

18

997313824

19

4809701440

20

23758664096

 

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.