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

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

 

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

  • Se n = Fk, { n, n – 1, n – 2, n – 3, …, 2, 1, 0 } è una permutazione di Fibonacci di n; per esempio, una permutazione di Fibonacci di 5 è { 5, 4, 3, 2, 1, 0 }. In particolare esistono permutazioni di Fibonacci degli interi da 0 a 3.

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

  • Se esistono permutazioni di Fibonacci degli interi da 0 a r, dato che esiste un numero di Fibonacci Fk tale che r < Fk < 2r, esistono permutazioni di Fibonacci per tutti gli interi n da r + 1 a Fk – 1. Infatti, prendendo m = Fk – 1 – n, abbiamo che 0 ≤ m < Fk – 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 di Fibonacci.

 

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

 

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

n

Numero di permutazioni di Fibonacci

0

1

1

2

2

4

3

7

4

10

5

15

6

7

7

28

8

39

9

32

10

17

11

56

12

136

13

173

14

36

15

142

16

89

17

114

18

304

19

512

20

1456

 

Propongo il termine “permutazioni di Fibonacci positive”, per analogia con le permutazioni quadrate positive, per le permutazioni degli interi da 1 a n, nelle quali k + P(k) è un numero di Fibonacci 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 4 è { 4, 3, 2, 1 }.

 

Si può dimostrare che con questa definizione esistono permutazioni di Fibonacci positive degli interi da 1 a n per qualsiasi valore di n. La dimostrazione è analoga a quella per le permutazioni di Fibonacci e si basa sull’osservazione che se n = Fk – 1, { n, n – 1, n – 2, n – 3, …, 2, 1 } è una permutazione di Fibonacci di n; per esempio, una permutazione di Fibonacci positiva di 7 è { 7, 6, 5, 4, 3, 2, 1 }.

 

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

 

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

n

Numero di permutazioni di Fibonacci positive

1

1

2

1

3

1

4

2

5

1

6

2

7

4

8

2

9

1

10

4

11

4

12

20

13

4

14

5

15

1

16

20

17

24

18

8

19

96

20

200

 

Bibliografia

  • 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.