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

Permutazioni triangolari (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 triangolari” di n le permutazioni di n nelle quali k + P(k) è un numero triangolare per tutti i valori di k da 0 a n.

 

Si può dimostrare che con questa definizione esistono permutazioni triangolari degli interi da 0 a n per qualsiasi valore di n. La dimostrazione è costruttiva e si basa su quattro semplici passi.

  • Se n = 2, { 0, 2, 1 } è una permutazione triangolare di n.

  • Se n = Tk, { n, n – 1, n – 2, n – 3, …, 2, 1, 0 } è una permutazione triangolare di n; per esempio, una permutazione triangolare di 6 è { 6, 5, 4, 3, 2, 1, 0 }. Esistono quindi permutazioni triangolari degli interi da 0 a 3.

  • Se esiste una permutazione triangolare di m, n > m e n + m = Tk – 1, esiste una permutazione triangolare di n: basta concatenare alla permutazione di m gli elementi { n, n – 1, n – 2, … m + 2, m + 1 }. Per esempio, una permutazione triangolare di 10 è { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 } e prendendo n = 17 abbiamo la permutazione { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 17, 16, 15, 14, 13, 12, 11, 10 }.

  • Se esistono permutazioni triangolari degli interi da 0 a r, con r > 1, dato che esiste un numero triangolare Tk tale che r < Tk < 2r, esistono permutazioni triangolari per tutti gli interi n da r + 1 a Tk – 1. Infatti, prendendo m = Tk – 1 – n, abbiamo che 0 ≤ m < Tk – 1 – r < r < n, quindi m < n e sono soddisfatte le condizioni del punto precedente.

La dimostrazione procede quindi per induzione, aggiungendo nuovi interi all’insieme di quelli per i quali esiste una permutazione triangolare.

 

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

 

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

n

Numero di permutazioni triangolari

0

1

1

1

2

1

3

2

4

1

5

3

6

5

7

4

8

11

9

15

10

23

11

55

12

79

13

86

14

305

15

969

16

1502

17

2084

18

5617

19

18061

20

45276

21

97849

22

138242

23

526647

24

1359778

25

2892308

26

5515021

27

13468104

28

59373473

29

181620242

30

399527296

31

817618115

Il termine successivo è maggiore di 109.

 

Propongo il termine “permutazioni triangolari positive”, per analogia con le permutazioni quadrate positive, per le permutazioni degli interi da 1 a n, nelle quali k + P(k) è un numero triangolare per tutti i valori di k da 1 a n, contando le posizioni a partire da 1. Per esempio, una permutazione del genere degli interi da 1 a 5 è { 5, 4, 3, 2, 1 }.

 

Si può dimostrare che con questa definizione esistono permutazioni triangolari positive degli interi da 1 a n per qualsiasi valore di n, tranne 1 e 4. La dimostrazione è costruttiva, analoga a quella per le permutazioni triangolari e si basa su cinque semplici passi.

  • Se n = 3, { 2, 1, 3 } è una permutazione triangolare positiva di n.

  • Se n = 10, { 9, 1, 3, 2, 10, 4, 8, 7, 6, 5 } è una permutazione triangolare positiva di n.

  • Se n = Tk – 1, { n, n – 1, n – 2, n – 3, …, 2, 1 } è una permutazione triangolare positiva positiva di n; per esempio, una permutazione triangolare positiva di 9 è { 9, 8, 7, 6, 5, 4, 3, 2, 1 }. Esistono quindi permutazioni triangolari positive di 1, 2, 5 e 9.

  • Se esiste una permutazione triangolare positiva di m, n > m e n + m = Tk – 1, esiste una permutazione triangolare di n: basta concatenare alla permutazione di m gli elementi { n, n – 1, n – 2, … m + 2, m + 1 }. Per esempio, una permutazione triangolare positiva di 9 è { 9, 8, 7, 6, 5, 4, 3, 2, 1 } e prendendo n = 18 abbiamo la permutazione { 9, 8, 7, 6, 5, 4, 3, 2, 1, 18, 17, 16, 15, 14, 13, 12, 11, 10}. Grazie ai due punti precedenti possiamo quindi stabilire che esistono permutazioni triangolari positive degli interi da 5 a 10.

  • Se esistono permutazioni triangolari positive degli interi da 5 a r, con r ≥ 10, dato che esiste un numero triangolare Tk tale che r + 6 < Tk < 2r, esiste una permutazioni triangolare positiva per tutti gli interi da r + 1 a Tk – 1. Infatti, prendendo m = Tkr – 2, abbiamo che m < Tk – 1 – r < r < n = r + 1 e m > 4, quindi 4 < m < n e sono soddisfatte le condizioni del punto precedente.

La dimostrazione procede quindi per induzione, aggiungendo nuovi interi all’insieme di quelli per i quali esiste una permutazione triangolare.

 

Non si conosce alcun modo per determinare il numero di permutazioni triangolari positive di un intero, se non esaminando le varie possibilità.

 

La tabella seguente mostra il numero di permutazioni triangolari positive di n, per n sino a 33 (M. Fiorentini, 2014).

n

Numero di permutazioni triangolari positive

1

0

2

1

3

1

4

0

5

1

6

1

7

1

8

2

9

4

10

3

11

9

12

14

13

13

14

52

15

124

16

161

17

181

18

715

19

2338

20

7073

21

8624

22

15466

23

52858

24

150365

25

316543

26

691771

27

1681604

28

5324919

29

15407311

30

37417775

31

69725286

32

155786456

33

579599171

Il termine successivo è maggiore di 109.

Contattami

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