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

Grattacieli (numeri di)

Matematica combinatoria 

Nel “problema dei grattacieli” si chiede di riempire una matrice n × n in modo tale che ogni riga e colonna contenga esattamente una volta gli interi da 1 a n, che rappresentano i numeri di piani di edifici, in modo tale che i numeri di edifici visibili dalle estremità di ogni riga e colonna siano valori assegnati. L’idea è che ogni edificio nasconde quelli seguenti di altezza inferiore; per cui, per esempio, nella disposizione (2, 1, 3, 6, 4, 5) sono visibili 3 edifici da sinistra (2, 3 e 6) e 2 da destra (5 e 6). Più formalmente, si tratta di disporre gli interi da 1 a n lungo ogni riga e colonna di un quadrato latino, in modo tale che in ogni riga e colonna i valori maggiori di ogni numero precedente e i valori maggiori di ogni numero seguente siano in numero assegnato.

 

Il numero di grattacieli fn(a, b) è il numero di permutazioni degli interi da 1 a n, tali che vi siano a grattacieli visibili da sinistra e b da destra.

 

Se si considera la visibilità da una sola parte, il numero di permutazioni tali che a edifici su n siano visibili da una parte, ossia il numero di permutazioni di n interi, tali che ve ne siano a maggiori di tutti i precedenti è Numero di Stirling di prima specie s(n, k) (v. numeri di Stirling di prima specie);

 

I numeri di grattacieli possono essere calcolati con la formula Formula per il calcolo dei numeri di grattacieli (Tanya Khovanova e Joel Brewster Lewis, 2013) e in particolare:

  • fn(1, 2) = fn(2, 1) = (n – 2)!, per n > 1;

  • Formula per il calcolo dei numeri di grattacieli, per n > 1;

  • fn(1, n) = fn(n, 1) = 1;

  • Formula per il calcolo dei numeri di grattacieli;

  • fn(2, n – 1) = fn(n – 1, 2) = n – 1;

  • Formula per il calcolo dei numeri di grattacieli.

 

Alcune proprietà:

fn(a, b) = fn(b, a);

fn(a, b) > 0 solo se 3 ≤ a + bn + 1, per n > 1;

Formula per il calcolo dei numeri di grattacieli (Tanya Khovanova e Joel Brewster Lewis, 2013);

se il massimo di fn(a, b) si raggiunge per a = r e b = s, |rs| ≤ 1, vale a dire che il massimo di raggiunge per valori di a e b uguali o che differiscono al massimo di 1 (Tanya Khovanova e Joel Brewster Lewis, 2013);

Formula che coinvolge i numeri di grattacieli (Tanya Khovanova e Joel Brewster Lewis, 2013);

 

Le tabelle seguenti mostrano i numeri di grattacieli fn(a, b) per n fino a 20.

 

La tabella seguente mostra i numeri di grattacieli f1(a, b).

a \ b

1

1

1

 

La tabella seguente mostra i numeri di grattacieli f2(a, b).

a \ b

1

2

1

0

1

2

1

0

 

La tabella seguente mostra i numeri di grattacieli f3(a, b).

a \ b

1

2

3

1

0

1

1

2

1

2

0

3

1

0

0

 

La tabella seguente mostra i numeri di grattacieli f4(a, b).

a \ b

1

2

3

4

1

0

2

3

1

2

2

6

3

0

3

3

3

0

0

4

1

0

0

0

 

La tabella seguente mostra i numeri di grattacieli f5(a, b).

a \ b

1

2

3

4

5

1

0

6

11

6

1

2

6

22

18

4

0

3

11

18

6

0

0

4

6

4

0

0

0

5

1

0

0

0

0

 

La tabella seguente mostra i numeri di grattacieli f6(a, b).

a \ b

1

2

3

4

5

6

1

0

24

50

35

10

1

2

24

100

105

40

5

0

3

50

105

60

10

0

0

4

35

40

10

0

0

0

5

10

5

0

0

0

0

6

1

0

0

0

0

0

 

La tabella seguente mostra i numeri di grattacieli f7(a, b).

a \ b

1

2

3

4

5

6

7

1

0

120

274

225

85

15

1

2

120

548

675

340

75

6

0

3

274

675

510

150

15

0

0

4

225

340

150

20

0

0

0

5

85

75

15

0

0

0

0

6

15

6

0

0

0

0

0

7

1

0

0

0

0

0

0

 

La tabella seguente mostra i numeri di grattacieli f8(a, b).

a \ b

1

2

3

4

5

6

7

8

1

0

720

1764

1624

735

175

21

1

2

720

3528

4872

2940

875

126

7

0

3

1764

4872

4410

1750

315

21

0

0

4

1624

2940

1750

420

35

0

0

0

5

735

875

315

35

0

0

0

0

6

175

126

21

0

0

0

0

0

7

21

7

0

0

0

0

0

0

8

1

0

0

0

0

0

0

0

 

La tabella seguente mostra i numeri di grattacieli f9(a, b).

a \ b

1

2

3

4

5

6

7

8

9

1

0

5040

13068

13132

6769

1960

322

28

1

2

5040

26136

39396

27076

9800

1932

196

8

0

3

13068

39396

40614

19600

4830

588

28

0

0

4

13132

27076

19600

6440

980

56

0

0

0

5

6769

9800

4830

980

70

0

0

0

0

6

1960

1932

588

56

0

0

0

0

0

7

322

196

28

0

0

0

0

0

0

8

28

8

0

0

0

0

0

0

0

9

1

0

0

0

0

0

0

0

0

 

La tabella seguente mostra i numeri di grattacieli f10(a, b).

a \ b

1

2

3

4

5

6

7

8

9

10

1

0

40320

109584

118124

67284

22449

4536

546

36

1

2

40320

219168

354372

269136

112245

27216

3822

288

9

0

3

109584

354372

403704

224490

68040

11466

1008

36

0

0

4

118124

269136

224490

90720

19110

2016

84

0

0

0

5

67284

112245

68040

19110

2520

126

0

0

0

0

6

22449

27216

11466

2016

126

0

0

0

0

0

7

4536

3822

1008

84

0

0

0

0

0

0

8

546

288

36

0

0

0

0

0

0

0

9

36

9

0

0

0

0

0

0

0

0

10

1

0

0

0

0

0

0

0

0

0

 

 

La tabella seguente mostra i massimi di fn(a, b) per n fino a 20.

n

Massimo di fn(a, b)

1

f1(1, 1) = 1

2

f2(1, 2) = f2(2, 1) = 1

3

f3(2, 2) = 2

4

f4(1, 1) = 6

5

f5(1, 1) = 22

6

f6(2, 3) = f6(3, 2) = 105

7

f7(2, 3) = f7(3, 2) = 675

8

f8(2, 3) = f8(3, 2) = 4872

9

f9(3, 3) = 40614

10

f10(3, 3) = 403704

11

f11(3, 3) = 4342080

12

f12(3, 3) = 50457000

13

f13(3, 3) = 631548456

14

f14(3, 3) = 8484089328

15

f15(3, 3) = 121882518576

16

f16(3, 3) = 1865935562400

17

f17(3, 3) = 30341974222944

18

f18(3, 3) = 522466493255424

19

f19(3, 3) = 9499883854364928

20

f20(3, 3) = 181927524046316544

 

Contattami

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