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

Entropia del quadrato rigido (costante della)

Matematica combinatoria  Teoria dei grafi 

Data una matrice quadrata di ordine n, si possono attribuire valori 0 e 1 a ogni cella, in modo che non vi siano due 1 adiacenti, in G(n) modi.

Si può anche definire G(n) come il numero di modi per disporre principi (che muovono di una casella ortogonalmente, ma non in diagonale) su una scacchiera di n × n caselle in modo che due principi non si attacchino; in questo caso le caselle contenenti i principi corrispondono al valore 1 e quelle vuote a 0.

Di seguito sono mostrati i 6 modi per attribuire 0 e 1 a una scacchiera di ordine 2.

0

0

0

0

 

1

0

0

0

 

0

1

0

0

 

0

0

1

0

 

0

0

0

1

 

1

0

0

1

 

0

1

1

0

 

La tabella seguente mostra i primi valori di G(n) (Robert Gerbicz, The Online Encyclopedia of Integer Sequences http://oeis.org).

n

G(n)

1

2

2

7

3

63

4

1234

5

55447

6

5598861

7

1280128950

8

660647962955

9

770548397261707

10

2030049051145980050

11

12083401651433651945979

12

162481813349792588536582997

13

4935961285224791538367780371090

14

338752110195939290445247645371206783

15

52521741712869136440040654451875316861275

16

18396766424410124752958806046933947217821482942

17

14557601701834111295974187104248827765798599152358303

18

26024585612650837861658126921792857026992497268285945167621

19

105105055066577962012604229608317915229737651637019975757755051314

20

958979036662929619406859624886958746851620546557485230898539651354907499

21

19766982580727525559447459703066410506378295841376040664015562851325369819076327

22

920486427724231647653646535134255190048558085587696509535085179014710020739303637413062

23

96836737362332577228126233146266027907220602904916569863928397932638147313462817836132159477643

24

23014876830102973080295375510481185265791418130718634637816237986620978856344595418898906840911239867869

25

12357280628458621610261003683798282889567362022871449310490079744330288088293888381458751196205785114467063479978

26

14989353830657887045253535577369170604561059504403111230207533142521161755543754839412836401335298693619461437872472165615

27

41076048814756904170038431958637474710328322517168428037124975797939221729929250098889601666346169376778430801983574787538529309191

28

254296368874677123746928211898730495474495246876690760159507126754738599026016292991448162576157292681301528315863006160203433527765235617478

29

3556619491488838337298644336171591528960687731348622394588805214244031766315339709627465589460212852431000227410783701037177097019793172369009198594591

30

112377766778527126203646648402050958984330252199994469198044986979798657215652532005142877926040203499014641860333039219325350361465468647055420204598509312491705

31

8021750282073225155937277559442085596569252222562065072079408283677366741501457757872727476533342530106995176743171878672055949896401364288786903505428040587483067121789402

32

1293610782537380062750834541787067327216099960402483810534636303148904354725352922280461789260135159483731789518847103985667992830570856310313642194651494698031350657047234754882428439

33

471285266887777154296095881476654192824817584357899764624988774903040794894502001053808670120270336794101503284106850667860054973490983066198243111721856759031824855064664844124351924909694482063

 

Si può dimostrare che al crescere di n, G(n) tende a Formula per la crescita asintotica di G(n), dove K è detta “costante dell’entropia del quadrato rigido” e vale circa 1.5030480824753322643220663294755536893857810. Compare in alcuni problemi di fisica statistica.

Non si conosce alcuna espressione della costante in forma chiusa, né si sa se sia algebrica.

Contattami

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