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

I subfattoriali sono un caso particolare di permutazioni discordanti; una permutazione degli interi da 1 a n si dice “k-discordante” se la distanza (ciclica) tra la posizione iniziale e quella finale di ogni intero è almeno k.

I subfattoriali sono il numero di permutazioni 1-discordanti.

Le permutazioni k-discordanti possono essere viste come il numero di modi di permutare la posizione di n persone intorno a un tavolo, in modo che ciascuno non disti meno di k posti dalla posizione precedente.

Per esempio, vi sono 2 permutazioni 2-discordanti degli interi da 1 a 5: (3, 4, 5, 1, 2) e (4, 5, 1, 2, 3).

 

Non si conosce una formula generale per le permutazioni k-discordanti e solo i primi casi sono stati risolti.

Le permutazioni 2-discordanti furono studiate da I. Kaplansky e John Riordan nel 1946 e da Touchard nel 1953.

John Riordan nel 1954 e Leo Moser nel 1964 studiarono le permutazioni 3-discordanti.

Nel 1978 Earl Glen Whitehead Jr. affrontò il problema di quelle 4-discordanti.

Per k > 2 però le soluzioni sono sotto forma di funzioni generatrici e non di formule chiuse o ricorrenze.

 

Il numero An – 1 di permutazioni di n oggetti nelle quali ognuno non si trova al suo posto né al successivo è legato alla soluzione, dovuta a Charles Ange Laisant, Charles Paul Narcisse Moreau e H.M. Taylor, del problema delle coppie (o problema del ménage): in quanti modi n coppie possono sedersi intorno a un tavolo, in modo che uomini e donne siano alternati e che nessuno sieda accanto al proprio coniuge?

Le signore possono accomodarsi in 2n! modi diversi e per ciascuno di essi vi sono An modi di assegnare posti ai mariti rispettando i vincoli del problema, quindi, contando separatamente rotazioni e riflessioni, il numero di modi è 2n!An.

Per esempio, indicando con due lettere uguali, una maiuscola e una minuscola, gli appartenenti alla stessa coppia, fatte accomodare le signore, vi è un solo modo con 3 coppie, (A, c, B, a, C, b), e due con 4 coppie: (A, c, B, d, C, a, D, b) e (A, d, B, a, C, b, D, c).

 

I valori di An si possono si possono calcolare con una delle tre ricorrenze:

A2 = 0 e A3 = 1, Ricorrenza per A(n);

A2 = 0 e A3 = 1, Ricorrenza per A(n) (W. Schöbe, 1943);

A2 = 0, A3 = 1, A4 = 2, A5 = 13, An = nAn – 1 + 2An – 2 – (n – 4)An – 3An – 4, per n > 5.

 

I valori possono anche essere calcolati tramite le formule:

Formula per il calcolo di A(n), per n > 1 (I. Kaplansky, 1945);

Formula per il calcolo di A(n), per n > 1 (J. Touchard 1953).

 

Al crescere di n, An tende a n! / e^2 (S.M. Kerawala, 1947), quindi il numero di soluzioni del problema delle coppie tende a 2 * n!^2 / e^2, ovvero a 2d(n)2.

 

I valori di An e il numero totale di soluzioni del problema delle coppie sono mostrati nella tabella seguente per n fino a 20.

n

An

Numero totale di soluzioni del problema delle coppie

0

0

0

1

0

0

2

0

0

3

1

12

4

2

96

5

13

3120

6

80

115200

7

579

5836320

8

4738

382072320

9

43387

31488549120

10

439792

3191834419200

11

4890741

390445460697600

12

59216642

56729732529254400

13

775596313

9659308746908620800

14

10927434464

1905270127543015833600

15

164806435783

431026303509734220288000

16

2649391469058

110865322076320374571008000

17

45226435601207

32172949121885378686623744000

18

817056406224416

10462200902615632782225309696000

19

15574618910994665

3789152162514479444022541762560000

20

312400218671253762

1520078238720229488146888721039360000

 

Se si considerano non coppie, ma singoli individui, il numero Bn di modi nei quali si possono disporre n persone intorno a un tavolo, in modo che nessuno sia nella posizione originaria o in una adiacente, ovvero il numero di permutazioni 2-discordanti di n è dato dalla spaventosa ricorrenza B3 = 0, B4 = 1, B5 = 2, B6 = 20, Ricorrenza per B(n), dove f(n) = Fn – 1 + Fn + 1 + 2 (K. Yamamoto).

 

La tabella seguente mostra il numero di permutazioni 2-discordanti di n, per n fino a 20.

n

Permutazioni 2-discordanti

0

0

1

0

2

0

3

0

4

1

5

2

6

20

7

144

8

1265

9

12072

10

126565

11

1445100

12

17875140

13

238282730

14

3407118041

15

52034548064

16

845569542593

17

14570246018686

18

265397214435860

19

5095853023109484

20

102877234050493609

 

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.