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

Permutazioni (numero di)

Matematica combinatoria 

Il numero di permutazioni di n è il numero di modi di ordinare n oggetti distinti, uguale a n!.

Il concetto e il modo per calcolare il numero di permutazioni risalgono (almeno) a Bhāskara II (Bijapur, India, 1114 – 1185), che trattò le permutazioni nel Lilāvati (nome della figlia, alla quale il libro è dedicato), una delle quattro parti del Siddhānta Shiromani (Corona di trattati), scritto nel 1150.

Bhāskara II fu il più importante matematico nell’arco di alcuni secoli; oltre a numerose ricerche in astronomia, i suoi lavori contengono tra l’altro varie scoperte comunemente attribuite a matematici posteriori di secoli, quali:

  • metodi per affrontare equazioni diofantee fino al quarto grado,

  • la ricerca di soluzioni intere di equazioni della forma ax2 + bx + c = y (comunemente attribuita a William Brouncker, 1657);

  • la ricerca di soluzioni intere di equazioni della forma x2ny2 = 1 (detta “equazione di Fermat – Pell”); l’equazione 61x2 + 1 = y2 fu proposta da Fermat come problema, ma la soluzione arrivò solo con Eulero, nel XVIII secolo;

  • la soluzione di equazioni di secondo grado in più incognite, con un corretto trattamento dello zero e dei numeri negativi e irrazionali, quale in Europa si ebbe solo nel Rinascimento;

  • alcuni concetti preliminari di analisi e calcolo infinitesimale, incluso il calcolo di derivate e nozioni di integrali;

  • il teorema di Rolle (1691, ma dimostrato nella forma generale solo da Cauchy nel 1823);

  • la soluzione di problemi di trigonometria sferica.

Eppure nessuno dei suoi importanti risultati è oggi ricordato col suo nome!

 

Una permutazione si può rappresentare come un prodotto di cicli di permutazioni, dove ogni ciclo contiene numeri scambiati ciclicamente di posto tra loro; in questo caso un ciclo composto da un solo numero rappresenta un elemento che resta al suo posto. Per esempio, la permutazione { 4, 2, 1, 3 } dei primi 4 interi maggiori di zero si può rappresentare come il prodotto (2)(1, 4, 3), perché il numero 2 è al suo posto e gli altri tre ruotano ciclicamente; la notazione indica che il primo elemento è rimpiazzato dal quarto, questo dal terzo e il terzo dal primo.

Con questa notazione la rappresentazione è unica, a meno dell’ordinamento (arbitrario) dei cicli tra loro: (2)(1, 4, 3) e (1, 4, 3)(2) indicano la stessa permutazione. La rappresentazione canonica prevede che i cicli siano ordinati prima per lunghezza crescente, poi in ordine crescente del primo numero che compare in essi; con queste condizioni aggiuntive la rappresentazione di una permutazione come prodotto di cicli diventa unica.

Il numero di permutazioni di n oggetti con esattamente k cicli è il numero di Stirling di prima specie Numero di Stirling di prima specie S(n, k).

 

Ogni permutazione si può ottenere dalla disposizione iniziale scambiando ripetutamente tra loro coppie di elementi; si può anche fare in modo che in ogni scambio sia coinvolto esattamente uno di due elementi prefissati.

Il numero di permutazioni distinte ottenibili con k scambi è il coefficiente di xk nello sviluppo di Funzione generatrice del numero di permutazioni ottenibili con k scambi.

 

Una permutazione si dice “pari” se ottenibile con un numero pari di scambi di posizione tra elementi e “dispari” altrimenti. Per esempio delle 6 permutazioni di { 1, 2, 3 }:

  • { 1, 2, 3 } è pari (nessuno scambio);

  • { 1, 3, 2 } è dispari (ottenibile scambiando 2 e 3);

  • { 2, 1, 3 } è dispari (ottenibile scambiando 1 e 2);

  • { 2, 3, 1 } è pari (ottenibile scambiando 1 e 2 e poi 1 e 3);

  • { 3, 1, 2 } è pari (ottenibile scambiando 1 e 2 e poi 2 e 3);

  • { 3, 2, 1 } è dispari (ottenibile scambiando 1 e 3).

Vi sono Numero di permutazioni pari di n oggetti permutazioni pari di n oggetti e altrettante dispari.

 

Il numero di inversioni di una permutazione è il numero minimo di inversioni tra elementi adiacenti necessari per ripristinare l’ordine originale. Per esempio, { 1, 3, 5, 2, 4 } è una permutazione degli interi da 1 a 5 con 3 inversioni: per ripristinare l’ordine iniziale bisogna scambiare due volte 2 con l’elemento alla sua sinistra e una volta 4 con l’elemento alla sua sinistra.

Se I(σ) è il numero di inversioni della permutazione σ e Sn è l’insieme delle permutazioni di n oggetti, Formula che coinvolge il numero di inversioni delle permutazioni di n oggetti.

 

Il numero di permutazioni di n oggetti nelle quali ogni oggetto si trova al massimo a un posto di distanza dalla sua posizione originale è il numero di Fibonacci Fn + 1.

 

Il numero di permutazioni cicliche di n oggetti (ossia considerando consecutivi il primo e l’n-esimo) è (n – 1)!; il numero di quelle nelle quali ogni oggetto si trova al massimo a un posto di distanza dalla sua posizione originale è il numero di Lucas Ln.

 

Se pn(k) è il numero di permutazioni di n oggetti, nelle quali esattamente k restano al loro posto, Somma che coinvolge i numeri di permutazioni. La dimostrazione fu proposta come problema alle Olimpiadi internazionali di Matematica, nel 1987.

Inoltre Somma che coinvolge i numeri di permutazioni e Somma che coinvolge i numeri di permutazioni.

 

Il numero di permutazioni degli interi da 1 a 2n, tali che nessun numero pari sia seguito da uno inferiore è n!2. Per esempio, 2!2 = 4 e le permutazioni del genere degli interi da 1 a 4 sono: { 1, 2, 3, 4 }, { 1, 3, 2, 4 }, { 2, 3, 1, 4 } e { 3, 1, 2, 4 }.

Il numero di permutazioni degli interi da 1 a 2n, tali che ogni numero pari sia seguito da uno inferiore è n!2. Per esempio, 2!2 = 4 e le permutazioni del genere degli interi da 1 a 4 sono: { 2, 1, 4, 3 }, { 3, 4, 2, 1 }, { 4, 2, 1, 3 } e { 4, 3, 2, 1 }.

Il numero di permutazioni degli interi da 1 a 2n – 1, tali che nessun numero pari sia seguito da uno inferiore è n!2. Per esempio, 2!2 = 4 e le permutazioni del genere degli interi da 1 a 3 sono: { 1, 2, 3 }, { 1, 3, 2 }, { 2, 3, 1 } e { 3, 1, 2 }.

Il numero di permutazioni degli interi da 1 a 2n – 1, tali che n – 1 numeri dispari siano seguiti da uno inferiore è n!2. Per esempio, 2!2 = 4 e le permutazioni del genere degli interi da 1 a 3 sono: { 1, 3, 2 }, { 2, 3, 1 }, { 3, 1, 2 } e { 3, 2, 1 }.

 

Avendo un insieme contenente nk volte ogni numero k da 1 a n, per un totale quindi di Formula per il numero totale di elementi elementi, tra le Formula per il numero totale di permutazioni permutazioni distinte ve ne sono Formula per il numero di permutazioni con esattamente m elementi seguiti da uno minore con esattamente m seguiti da uno minore.

Il problema di determinare questa formula è noto come “problema di Newcomb”, perché suggerito a Simon Newcomb (1835 – 1909) dall’analisi di un solitario, e fu risolto da MacMahon nel 1907.

La formula si può applicare, per esempio, per trovare quante permutazioni esistano di un mazzo di carte con m seguite da una minore (non distinguendo tra loro carte di ugual valore, ma diverso seme). In questo caso i vari nk sono tutti 4, n = 13 e t = 52. La formula diviene allora Formula per il numero di permutazioni con esattamente m elementi seguiti da uno minore.

La tabella seguente riporta i numeri di permutazioni per m da 0 a 52.

m

Numero di permutazioni

0

1

1

1220703072

2

1946130371095128

3

118169571125488257824

4

962624331855762939745950

5

1966328218272794506172178816

6

1439127765510353092008927027552

7

471290654822091236131899199410048

8

80029528286823033581035280235294534

9

7809293779983274822623535153608582400

10

471762301604915916041949990598824207936

11

18654336397201567770100728803808487060992

12

503889648704412874721333911884119515746758

13

9613969033397252407631428647542828678636064

14

133048205100685883825495567684755566981336600

15

1364318456196520255200188920212913617632210016

16

10546812030894381137947079321870444480470272927

17

62333247894001270743501413257072250147120086848

18

284880680711858047534653813824918033094981058384

19

1016136251788781102429880214938283344136061476800

20

2849571385456082606267939710075351583153983595676

21

6318824818889898577943340766185999924189290367872

22

11127251518100353624522450439162012227211697056928

23

15607392285813146100694590567092487112942549482624

24

17467353221593073329258089394532643301221130216500

25

15607392285813146100694590567092487112942549482624

26

11127251518100353624522450439162012227211697056928

27

6318824818889898577943340766185999924189290367872

28

2849571385456082606267939710075351583153983595676

29

1016136251788781102429880214938283344136061476800

30

284880680711858047534653813824918033094981058384

31

62333247894001270743501413257072250147120086848

32

10546812030894381137947079321870444480470272927

33

1364318456196520255200188920212913617632210016

34

133048205100685883825495567684755566981336600

35

9613969033397252407631428647542828678636064

36

503889648704412874721333911884119515746758

37

18654336397201567770100728803808487060992

38

471762301604915916041949990598824207936

39

7809293779983274822623535153608582400

40

80029528286823033581035280235294534

41

471290654822091236131899199410048

42

1439127765510353092008927027552

43

1966328218272794506172178816

44

962624331855762939745950

45

118169571125488257824

46

1946130371095128

47

1220703072

48

1

49

0

50

0

51

0

52

0

 

Se si considerano distinte le 4 carte dello stesso valore, ogni numero della tabella va moltiplicato per 4!13 = 876488338465357824.

 

Se i vari nk sono tutti 1, t = n e la soluzione è data dal numero euleriano Numero euleriano E(n, k).

 

Il numero di permutazioni di n elementi contenenti esattamente m sequenze crescenti, ciascuna delle quali non può essere estesa alle estremità, è Numero di permutazioni di n elementi contenenti esattamente m sequenze crescenti; si noti che in questa definizione un numero inferiore ai due adiacenti è considerato una sottosequenza ascendente di lunghezza 1.

 

Se si scelgono k oggetti tra n, il numero di permutazioni è Numero di permutazioni di k elementi scelti tra n.

Bibliografia

  • Andrews, G.E.;  The Theory of Partitions, Cambridge University Press, 1984.
  • Bressoud, David M.;  Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture, Cambridge, Cambridge University Press, 1999.
  • Koshy, Thomas;  Fibonacci and Lucas Numbers with Applications, New York, John Wiley & Sons, 2001.
  • Kuczma, E. Marcin;  International Mathematical Olympiads 1986 – 1999, Mathematical Association of America, 2003.

Contattami

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