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

Lengyel (costante di)

Matematica combinatoria 

Possiamo definire una relazione d’ordine parziale sulle partizioni di un insieme S come segue: date due partizioni distinte P1 e P2, scriviamo P1P2 se tutti gli elementi di P2 sono contenuti in elementi di P!, vale a dire se P2 è un raffinamento di P1.

Dato un insieme di n elementi (che indicheremo con interi positivi consecutivi a partire da 1), indichiamo con Zn il numero totale di catene di partizioni { { 1, 2, 3, ... n } } = P0 ≺ P1P2... ≺ Pk = { { 1 }, { 2 }, { 3 }, ... { n } }.

Per esempio, Z3 = 4, perché le catene sono:

  • { { 1, 2, 3 } } ≺ { { 1 }, { 2 }, { 3 } },

  • { { 1, 2, 3 } } ≺ { { 1, 2 }, { 3 } } ≺ { { 1 }, { 2 }, { 3 } },

  • { { 1, 2, 3 } } ≺ { { 1, 3 }, { 2 } } ≺ { { 1 }, { 2 }, { 3 } },

  • { { 1, 2, 3 } } ≺ { { 2, 3 }, { 1 } } ≺ { { 1 }, { 2 }, { 3 } }.

 

I numeri di catene possono essere calcolati tramite la ricorrenza Z0 = 1, Formula per il calcolo di Z(n), dove Numero di Stirling di seconda specie S(n, k) indica un numero di Stirling di seconda specie.

 

 

T. Lengyel dimostrò nel 1984 che il valore di Formula che tende alla costante di Lengyel è limitato da due costanti e nel 1992, in collaborazione con L. Babai, dimostrò che al crescere di n tende a una costante, chiamata appunto “costante di Lengyel”, che vale circa 1.098685805525187.

 

La tabella seguente mostra i valori di Zn per n sino a 20 e l’accordo con la stima asintotica.

n

Zn

Formula che tende alla costante di Lengyel

1

1

1.3862943611

2

1

1.1278039604

3

4

1.1446785189

4

32

1.1306149095

5

436

1.1242623000

6

9012

1.1200342308

7

262760

1.1169751859

8

10270696

1.1146809046

9

518277560

1.1128965460

10

32795928016

1.1114693372

11

2542945605432

1.1103020576

12

237106822506952

1.1093297540

13

26173354092593696

1.1085074138

14

3375693096567983232

1.1078028715

15

502995942483693043200

1.1071925358

16

85750135569136650473360

1.1066587141

17

16583651916595710735271248

1.1061878794

18

3611157196483089769387182064

1.1057695131

19

879518067472225603327860638128

1.1053953137

20

238173627622886617865046545942960

1.1050586421

 

Il numero di catene di lunghezza massima (cioè di n elementi) è invece Numero di catene di lunghezza massima.

Contattami

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