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

Permutazioni quadrate (numero di)

Matematica combinatoria 

Data una permutazione P degli interi da 0 a n, Indichiamo con P(k) la posizione nella sequenza occupata da k; per esempio, nella permutazione { 0, 3, 1, 2 } degli interi fino a 3, P(1) = 2, perché 1 va in posizione 2, iniziando a contare da zero.

Si chiamano “permutazioni quadrate” di n le permutazioni di n nelle quali k + P(k) è un quadrato per tutti i valori di k da 0 a n.

 

Le permutazioni quadrate furono suggerite da David Silverman ed esaminate da Benjamin L. Schwartz, che dimostrò nel 1978 che con questa definizione esistono permutazioni quadrate degli interi da 0 a n per qualsiasi valore di n. La dimostrazione è costruttiva e si basa su quattro semplici passi.

  • Se n = r2 o n = r2 – 1, esiste una permutazione quadrata di n: nel primo caso la permutazione è { n, n – 1, n – 2, n – 3, …, 2, 1, 0 } e nel secondo { 0, n, n – 1, n – 2, n – 3, …, 2, 1 }. Per esempio, una permutazione quadrata di 9 è { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 } e una permutazione quadrata di 8 è { 0, 8, 7, 6, 5, 4, 3, 2, 1 }.

  • Una permutazione quadrata di 2 è { 0, 1, 2 }, quindi, considerando anche il passo precedente, esistono permutazioni quadrate degli interi positivi fino a 4.

  • Se esiste una permutazione quadrata di m, n > m e n + m = r2 – 1, allora esiste una permutazione quadrata di n: basta concatenare alla permutazione di m gli elementi { n, n – 1, n – 2, … m + 2, m + 1 }. Per esempio, una permutazione quadrata di 4 è { 4, 3, 2, 1, 0 } e prendendo n = 11 abbiamo la permutazione { 4, 3, 2, 1, 0, 11, 10, 9, 8, 7, 6, 5 }.

  • Se esistono permutazioni quadrate degli interi da 0 a (r – 1)2, allora esistono per tutti gli interi n superiori fino a r2 – 1. Infatti, prendendo m = r2 – 1 – n, abbiamo che 0 ≤ m < r2 – 1 – (r – 1)2 = 2r – 2 ≤ (r – 1)2 < n, per r > 2, quindi m < n e sono soddisfatte le condizioni del punto precedente; procedendo per induzione otteniamo che esistono permutazioni quadrate di ogni intero non negativo.

 

Le permutazioni quadrate costruite come indicato sopra non sono le uniche possibili; non si conosce alcun modo per determinare il numero di permutazioni quadrate di un intero, se non esaminando le varie possibilità.

 

La tabella seguente mostra il numero di permutazioni quadrate di n, per n sino a 42 (M. Fiorentini, 2014).

n

Numero di permutazioni quadrate

0

1

1

1

2

1

3

1

4

1

5

1

6

1

7

1

8

2

9

3

10

2

11

1

12

2

13

6

14

11

15

21

16

22

17

16

18

30

19

87

20

195

21

241

22

247

23

237

24

619

25

2426

26

5189

27

10904

28

16152

29

19449

30

19825

31

32193

32

117696

33

410616

34

1309671

35

3731273

36

9188803

37

12217363

38

15793351

39

22361903

40

41002326

41

143287534

42

499020393

Il termine successivo è maggiore di 109.

 

Schwartz propose di chiamare “permutazioni quadrate positive” le permutazioni degli interi da 1 a n, nelle quali k + P(k) è un quadrato per tutti i valori di k da 1 a n, contando le posizioni a partire da 1. Per esempio, una permutazione quadrata positiva degli interi da 1 a 17 è { 15, 7, 1, 5, 4, 3, 2, 17, 16, 6, 14, 13, 12, 11, 10, 9, 8 }.

 

Schwartz dimostrò che esistono permutazioni quadrate positive degli interi da 1 a n per qualsiasi valore di n, tranne 1, 2, 4, 6, 7 e 11.

Anche in questo caso non si conosce alcuna formula per determinare il numero di permutazioni quadrate positive di un intero dato.

 

La tabella seguente mostra il numero di permutazioni quadrate positive di n, per n sino a 45 (Franklin T. Adams-Watters, The Online Encyclopedia of Integer Sequences http://oeis.org).

n

Numero di permutazioni quadrate positive

Permutazioni quadrate positive

1

0

-

2

0

-

3

1

{ 3, 2, 1 }

4

0

-

5

1

{ 3, 2, 1, 5, 4 }

6

0

-

7

0

-

8

1

{ 8, 7, 6, 5, 4, 3, 2, 1 }

9

1

{ 8, 2, 6, 5, 4, 3, 9, 1, 7 }

10

1

{ 3, 2, 1, 5, 4, 10, 9, 8, 7, 6 }

11

0

-

12

1

{ 3, 2, 1, 12, 11, 10, 9, 8, 7, 6, 5, 4 }

13

1

{ 8, 2, 13, 12, 11, 10, 9, 1, 7, 6, 5, 4, 3 }

14

2

{ 3, 2, 1, 5, 4, 10, 9, 8, 7, 6, 14, 13, 12, 11 },

{ 8, 14, 13, 12, 11, 10, 9, 1, 7, 6, 5, 4, 3, 2 }

15

4

{ 3, 2, 6, 5, 4, 10, 9, 8, 7, 15, 14, 13, 12, 11, 1 },

{ 8, 2, 6, 5, 4, 3, 9, 1, 7, 15, 14, 13, 12, 11, 10 },

{ 15, 2, 1, 5, 4, 3, 9, 8, 7, 6, 14, 13, 12, 11, 10 },

{ 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }

16

3

{ 3, 7, 6, 5, 4, 10, 2, 8, 16, 15, 14, 13, 12, 11, 1, 9 },

{ 8, 7, 6, 5, 4, 3, 2, 1, 16, 15, 14, 13, 12, 11, 10, 9 },

{ 15, 7, 1, 5, 4, 3, 2, 8, 16, 6, 14, 13, 12, 11, 10, 9 }

17

2

{ 3, 7, 6, 5, 4, 10, 2, 17, 16, 15, 14, 13, 12, 11, 1, 9, 8 },

{ 15, 7, 1, 5, 4, 3, 2, 17, 16, 6, 14, 13, 12, 11, 10, 9, 8 }

18

5

{ 3, 2, 6, 5, 4, 10, 18, 17, 16, 15, 14, 13, 12, 11, 1, 9, 8, 7 },

{ 3, 7, 6, 5, 4, 10, 2, 17, 16, 15, 14, 13, 12, 11, 1, 9, 8, 18 },

{ 15, 2, 1, 5, 4, 3, 18, 17, 16, 6, 14, 13, 12, 11, 10, 9, 8, 7 },

{ 15, 7, 1, 5, 4, 3, 2, 17, 16, 6, 14, 13, 12, 11, 10, 9, 8, 18 },

{ 15, 14, 13, 12, 11, 10, 18, 17, 16, 6, 5, 4, 3, 2, 1, 9, 8, 7 }

19

15

{ 3, 2, 1, 5, 4, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6 },

{ 3, 2, 6, 5, 4, 10, 18, 8, 16, 15, 14, 13, 12, 11, 1, 9, 19, 7, 17 },

{ 3, 2, 6, 5, 4, 19, 18, 1, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 17 },

{ 3, 7, 1, 5, 4, 19, 2, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 18, 6 },

{ 3, 7, 6, 5, 4, 10, 2, 8, 16, 15, 14, 13, 12, 11, 1, 9, 19, 18, 17 },

{ 3, 7, 6, 5, 4, 19, 2, 1, 16, 15, 14, 13, 12, 11, 10, 9, 8, 18, 17 },

{ 8, 2, 1, 5, 4, 3, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 19, 7, 6 },

{ 8, 2, 6, 5, 4, 3, 18, 1, 16, 15, 14, 13, 12, 11, 10, 9, 19, 7, 17 },

{ 8, 7, 1, 5, 4, 3, 2, 17, 16, 15, 14, 13, 12, 11, 10, 9, 19, 18, 6 },

{ 8, 7, 6, 5, 4, 3, 2, 1, 16, 15, 14, 13, 12, 11, 10, 9, 19, 18, 17 },

{ 8, 14, 13, 12, 11, 10, 18, 17, 16, 15, 5, 4, 3, 2, 1, 9, 19, 7, 6 },

{ 15, 2, 1, 5, 4, 3, 18, 8, 16, 6, 14, 13, 12, 11, 10, 9, 19, 7, 17 },

{ 15, 7, 1, 5, 4, 3, 2, 8, 16, 6, 14, 13, 12, 11, 10, 9, 19, 18, 17 },

{ 15, 14, 13, 12, 11, 10, 18, 8, 16, 6, 5, 4, 3, 2, 1, 9, 19, 7, 17 },

{ 15, 14, 13, 12, 11, 19, 18, 1, 16, 6, 5, 4, 3, 2, 10, 9, 8, 7, 17 }

20

21

{ 3, 2, 1, 5, 4, 19, 9, 17, 7, 15, 14, 13, 12, 11, 10, 20, 8, 18, 6, 16 },

{ 3, 2, 6, 5, 4, 10, 9, 8, 7, 15, 14, 13, 12, 11, 1, 20, 19, 18, 17, 16 },

{ 3, 2, 6, 5, 4, 19, 9, 1, 7, 15, 14, 13, 12, 11, 10, 20, 8, 18, 17, 16 },

{ 8, 2, 1, 5, 4, 3, 9, 17, 7, 15, 14, 13, 12, 11, 10, 20, 19, 18, 6, 16 },

{ 8, 2, 6, 5, 4, 3, 9, 1, 7, 15, 14, 13, 12, 11, 10, 20, 19, 18, 17, 16 },

{ 8, 2, 13, 12, 20, 10, 18, 17, 16, 15, 14, 4, 3, 11, 1, 9, 19, 7, 6, 5 },

{ 8, 7, 13, 12, 11, 10, 9, 17, 16, 15, 14, 4, 3, 2, 1, 20, 19, 18, 6, 5 },

{ 8, 7, 13, 12, 20, 10, 2, 17, 16, 15, 14, 4, 3, 11, 1, 9, 19, 18, 6, 5 },

{ 8, 14, 13, 12, 11, 10, 9, 17, 7, 15, 5, 4, 3, 2, 1, 20, 19, 18, 6, 16 },

{ 8, 14, 13, 12, 20, 10, 2, 17, 7, 15, 5, 4, 3, 11, 1, 9, 19, 18, 6, 16 },

{ 15, 2, 1, 5, 4, 3, 9, 8, 7, 6, 14, 13, 12, 11, 10, 20, 19, 18, 17, 16 },

{ 15, 2, 13, 12, 20, 10, 18, 8, 16, 6, 14, 4, 3, 11, 1, 9, 19, 7, 17, 5 },

{ 15, 2, 13, 12, 20, 19, 18, 1, 16, 6, 14, 4, 3, 11, 10, 9, 8, 7, 17, 5 },

{ 15, 7, 13, 12, 11, 10, 9, 8, 16, 6, 14, 4, 3, 2, 1, 20, 19, 18, 17, 5 },

{ 15, 7, 13, 12, 11, 19, 9, 1, 16, 6, 14, 4, 3, 2, 10, 20, 8, 18, 17, 5 },

{ 15, 7, 13, 12, 20, 10, 2, 8, 16, 6, 14, 4, 3, 11, 1, 9, 19, 18, 17, 5 },

{ 15, 7, 13, 12, 20, 19, 2, 1, 16, 6, 14, 4, 3, 11, 10, 9, 8, 18, 17, 5 },

{ 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 20, 19, 18, 17, 16 },

{ 15, 14, 13, 12, 11, 19, 9, 1, 7, 6, 5, 4, 3, 2, 10, 20, 8, 18, 17, 16 },

{ 15, 14, 13, 12, 20, 10, 2, 8, 7, 6, 5, 4, 3, 11, 1, 9, 19, 18, 17, 16 },

{ 15, 14, 13, 12, 20, 19, 2, 1, 7, 6, 5, 4, 3, 11, 10, 9, 8, 18, 17, 16 }

21

66

 

22

37

 

23

51

 

24

144

 

25

263

 

26

601

 

27

1333

 

28

2119

 

29

2154

 

30

2189

 

31

3280

 

32

12405

 

33

55329

 

34

160895

 

35

588081

 

36

849906

 

37

1258119

 

38

1233262

 

39

2478647

 

40

4305500

 

41

17278636

 

42

47424179

 

43

153686631

 

44

396952852

 

45

1043844982

 

 

Bibliografia

  • Roberts, Joe;  The Lure of the Integers, The Mathematical Association of America, 1992 -

    Una miniera di informazioni sugli interi.

  • Schwartz, Benjamin L.;  "Square Permutations" in Mathematics Magazine, The Mathematical Association of America, vol. 51, n. 1, gennaio 1978, pag. 64 – 66.

Contattami

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