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

Indice

  1. 1. Pagina principale
  2. 2. Formule
  3. 3. Valori
  4. 4. Permutazioni k-discordanti

L’n-esimo subfattoriale, indicato con d(n), ma anche con !n o n¡, è il numero di permutazioni di n oggetti che non ne lasciano nessuno al posto di partenza.

Per esempio, con 4 oggetti inizialmente nell’ordine ABCD, vi sono d(4) = 9 permutazioni del genere:

B, A, D, C;

B; C, D, A;

B, D, A, C;

C, A, D, B;

C, D, A, B;

C, D, B, A;

D, A, B, C;

D, C, A, B;

D, C, B, A.

 

Nel XIX secolo il reverendo W. Allen Withworth propose per i subfattoriali la notazione Notazione per i subfattoriali per il subfattoriale di n, per analogia con una notazione allora in uso per i fattoriali, ma l’idea non ebbe successo.

 

I subfattoriali sono anche chiamati “fattoriali sinistri”, a causa della notazione !n, “numeri di permutazioni discordanti” o “numeri di de Montmort”, perché Pierre de Montmort (Parigi, 27/10/1678 – Parigi, 7/10/1719) pose nel 1708 il problema di calcolare il numero di permutazioni di n oggetti che non ne lasciano nessuno al posto di partenza e lo risolse nel 1713, quasi contemporaneamente a Nicholas Bernoulli (Basilea, 21/10/1687 – Basilea, 29/11/1759).

 

Il numero di permutazioni degli interi da 1 a n, tali che non ve ne siano due consecutivi minori di tutti i precedenti e non terminino con 1 è d(n). Per esempio, vi sono d(4) = 9 permutazioni del genere degli interi da 1 a 4:

1, 2, 3, 4;

1, 2, 4, 3;

1, 3, 2, 4;

1, 3, 4, 2;

1, 4, 2, 3;

1, 4, 3, 2;

2, 3, 1, 4;

2, 4, 1, 3;

3, 4, 1, 2.

Non vanno contate le permutazione 2, 1, 3, 4 e 3, 2, 1, 4 perché 2 e 1 sono minori di tutti i precedenti e consecutivi.

 

Il numero di permutazioni degli interi da 1 a n, tali che vi sia esattamente un caso in cui un numero è uguale al precedente più uno è d(n). Per esempio, vi sono d(4) = 9 permutazioni del genere degli interi da 1 a 4:

1, 2, 4, 3;

1, 3, 4, 2;

1, 4, 2, 3;

2, 1, 3, 4;

2, 3, 1, 4;

3, 1, 2, 4;

3, 4, 2, 1;

4, 2, 3, 1;

4, 3, 1, 2.

 

Il numero di permutazioni degli interi da 1 a n, che iniziano con 1 e nelle quali non vi siano numeri uguali al precedente più uno è d(n – 1). Per esempio, vi sono d(3) = 2 permutazioni del genere degli interi da 1 a 4:

1, 3, 2, 4;

1, 4, 3, 2.

 

Il numero di permutazioni degli interi da 1 a n, che non iniziano con 1 e nelle quali non vi siano numeri uguali al precedente più uno è d(n). Per esempio, vi sono d(4) = 9 permutazioni del genere degli interi da 1 a 4:

2, 1, 4, 3;

2, 4, 1, 3;

2, 4, 3, 1;

3, 1, 4, 2;

3, 2, 1, 4;

3, 2, 4, 1;

4, 1, 3, 2;

4, 2, 1, 3;

4, 3, 2, 1.

 

Di conseguenza il numero di permutazioni degli interi da 1 a n, nelle quali non vi siano numeri uguali al precedente più uno è d(n) + d(n – 1).

 

Se si mettono i biglietti da visita di n persone in un cappello, si rimescola e si fa pescare a ciascuno un biglietto, esistono d(n) modi per pescare tutti i biglietti senza che nessuno peschi il proprio. Dato che i biglietti possono essere pescati in n! ordini differenti, la probabilità che nessuno peschi il proprio è d(n) / n!, che tende rapidamente a 1 / e al crescere di n. Più precisamente, d(n) – n! / e tende a Limite asintotico cui tende d(n) – n! / e, dove bn è l’n-esimo numero di Bell (Ramanujan).

 

Si indica con d(n, k) il numero di permutazioni di n oggetti che ne lasciano esattamente k al loro posto, ovvero il numero di modi in cui può succedere che esattamente k persone su n peschino il proprio biglietto.

La probabilità che esattamente k persone peschino il proprio biglietto è Probabilità che esattamente k persone peschino il proprio biglietto, per k < n, e tende rapidamente a 1 / (e * k!) al crescere di n.

Le probabilità sono le stesse che k carte restino nella loro posizione originale dopo aver mescolato un mazzo di n; indipendentemente dal numero di carte, il valore più probabile è sempre zero.

Il valor medio del numero di carte al loro posto è invece 1, per qualsiasi valore di n.

 

Il numero Sn, k di permutazioni di n + k oggetti, nelle quali nessuno dei primi k resta nella posizione originale si può calcolare con la formula Formula per il calcolo di S(n + k, k). Chiaramente Sn, 0 = n! e Sn, n = d(n).

 

Il numero di permutazioni pari, ossia ottenibili con un numero pari di scambi di coppie di elementi, di n oggetti che non ne lasciano nessuno al posto di partenza è dato dalla ricorrenza a(0) = 1, a(1) = 0, a(n) = (n – 1)(a(n – 1) + a(n – 2)) + (–1)n – 1(n – 1), oppure Ricorrenza per a(n). Una formula equivalente è Formula per il calcolo di a(n), per n > 1.

 

Un gruppo di permutazioni è un insieme di permutazioni dotato della struttura di gruppo, ossia contenente l’inversa di ogni permutazione, la permutazione identica e che sia associativo e chiuso rispetto alla composizione di permutazioni. Stabilire se una permutazione mantenga o meno almeno un elemento al suo posto è un’operazione semplice, tuttavia, dato un gruppo di permutazioni stabilire se contenga o meno una permutazione nella quale tutti gli elementi abbiano cambiato posto è un problema NP-completo, ovvero un problema per il quale non si conoscono algoritmi il cui tempo di calcolo non cresca esponenzialmente con le dimensioni del problema nel caso peggiore. La difficoltà deriva dal fatto che un gruppo di permutazioni può essere definito da un numero relativamente piccolo di permutazioni (n – 1 scambi bastano per costruire tutte le n! permutazioni di un insieme di n elementi), ma contiene un numero di elementi che può essere molto elevato (è un divisore di n! per un insieme di n elementi).

Bibliografia

  • Gardner, Martin;  Enigmi e giochi matematici volume 4Âș, Firenze, Sansoni, 1975 -

    Traduzione di The Unexpected Hanging and Other Mathematical Diversions, New York, Simon and Schuster, 1966.

  • Yaglom, A.M.;  Yaglom, I.M.;  Challenging Mathematical Problems with Elementary Solutions, New York, Dover, 1987 -

    Traduzione dal russo di Neelementarnye Zadachi v Elementarnom Izlozhenii (Problemi non elementari e soluzioni elementari), Mosca, Ist. Governativo di stampa per la letteratura tecnico-teorica, 1954. Una splendida raccolta di problemi, generalmente non facili, comparsa per la prima volta in occidente nel 1964 (S. Francisco, Holden-Day Inc., 1964).

Contattami

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