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

Partizioni piane (numero di)

Matematica combinatoria 

Una partizione piana di un numero naturale n è una disposizione rettangolare di interi positivi, tali che la loro somma sia n e nessuno sia superiore a quello alla sua sinistra o al di sopra.

Per esempio, una partizione piana di 27 è la seguente.

5

4

2

1

1

3

3

2

1

 

3

1

1

 

 

 

Un’interpretazione fisica si ottiene immaginando pile di scatole identiche, ammassate in un angolo, in modo che ciascuna si appoggi alla pila a sinistra e in a quella alto, tranne quelle estreme, appoggiate ai muri. Una partizione piana rappresenterebbe allora una disposizione stabile, con gli interi che indicano l’altezza di ogni singola pila.

La figura seguente mostra la disposizione corrispondente alla partizione piana mostrata sopra.

 

Raffigurazione di una partizione piana di 27

 

 

Partizioni ottenute riflettendo specularmente la disposizione rispetto alla bisettrice dell’angolo superiore sinistro sono considerate distinte.

Per esempio, le 13 partizioni piane di 4 sono:

4

3

1

3

1

2

2

2

2

2

1

1

2

1

1

2

1

1

 

1

1

1

1

1

1

1

1

1

1

1

1

 

 

1

1

1

 

1

 

1

1

1

1

 

Il numero di partizioni piane si può ottenere dalla ricorrenza a(0) = 1, Ricorrenza per il calcolo del numero di partizioni piane.

 

Il numero di partizioni piane di n tende a Limite cui tende il numero di partizioni piane (E.M. Wright, 1931).

 

La tabella seguente mostra i numeri di partizioni piane per n sino a 20.

n

Numero di partizioni piane

0

1

1

1

2

3

3

6

4

13

5

24

6

48

7

86

8

160

9

282

10

500

11

859

12

1479

13

2485

14

4167

15

6879

16

11297

17

18334

18

29601

19

47330

20

75278

 

La funzione generatrice per il numero di partizioni piane di n è Funzione generatrice del numero di partizioni piane (Mac Mahon).

 

MacMahon dimostrò nel 1960 che il numero di partizioni piane che possono essere rappresentate in un rettangolo a × b (senza necessariamente riempirlo), con interi non superiori a c è Formula per il numero di partizioni piane che possono essere rappresentate in un rettangolo a × b con interi non superiori a c, che nel caso particolare a = b = c = n, ossia quando le partizioni possono essere contenute in un cubo di spigolo n, si riduce a Formula per il numero di partizioni piane che possono essere rappresentate in un rettangolo n × n con interi non superiori a n.

 

La tabella seguente mostra i numeri di partizioni piane con a = b = c = n, per n sino a 30 (Jonas Wallgren, The Online Encyclopedia of Integer Sequences http://oeis.org).

n

Numero di partizioni piane contenute in un cubo di spigolo n

0

1

1

2

2

20

3

980

4

232848

5

267227532

6

1478619421136

7

39405996318420160

8

5055160684040254910720

9

3120344782196754906063540800

10

9265037718181937012241727284450000

11

132307448895406086706107959899799334375000

12

9085552167600874784841331542959517939562500000000

13

2999857765812020084460232816316708564911203617625000000000

14

4762064017638745792086082881004254292914025372882289895393600000000

15

36341729505476900399799665385361772930508838969818479733267909524046796800000

16

1333238967268838729644960699395260091156640392837595395230823030619103588479705246924800

17

235116444976322502829475826364534598822840542738281621552968350050953479641376902283548777986211840

18

199303303578938513961809502550780198457205495201788549642937209410771853197084068107967133483277796725024706560

19

812061577102174649897256643006161014528116972220409359447633569655603949704105564686382037239983539940432060105217072117248

20

15903582500804731054469166508153509542504015776668691671980315420897593303913451678609559537356540537072433389911708414257469432313587968

21

1497003257511731829618095714758691754818522412657295173490755463021981347981334341653789155590248600737096343068622822807378418999952072332139445695336

22

677273209014991763684722160238012272459548041591725717044026670466472754766957344003971387714019541707443992054565305220998913975936867810757036368455748792902018880

23

1472689312552743961773003516937376479183816536804874413638465103589720554014669306091409064899869759945435049629673416647529181200974182138091988906561299052441032408116134797199360

24

15390690529502661189934911114310687265739790211878983873078546973857642349993566515646978891180046784926002868770725078777912725483639881698342723128753597962517146493159874788494534703773119479808

25

773035128749818341441692290901361454234129847092443974991885593081930207358815888017884684680810253634129591298294080429914311081972359667273189535520343256112864738534186275078766042944162627750280969784148754432

26

186607710783090953085091890540568291078433307463174834712420642920012496256042508890033174100966295967230306641462454227795050949996420104073366537261721604289224646698094229840186621912893540628892417927767347806952607241834070016

27

216493472167029164829404176217595295876982124629639164901363905505493687056512048678045247615086058553848868886016694490638686171617795008032758381539219877002903870158100869739949045109753349408380389823051351387943803829283959092110359579278704640

28

1207093751232045965652145196012977782656062171071678944283228401625752002583120625197115503444349910088121042065264786683292112587981869177641070884577572148064270466601343386253229247393542686730893903254315023846194158090248191982409428353579922989917563551943229440

29

32345561312044592958978456758292523061262532603287091595989049111140722640787075286468686333217737237574991780675240189147360564332394614940260534022935264435133722823590840382415752338095045288371277471854040819487437838495061184266431406734802954149661596886497896925368022402739470336

30

4165457904340919485420942168075326611541373543430798671358047428426506925547438251610506720329700499354829616209137772863162211410372528376990867545521482362075056103720140710647411783904290355185482877153598793526763431130749282194115544782656143919020194290255761694152890975799253442233181825888394674176

 

Il concetto può essere esteso a partizioni solide, ma in questo caso non si conoscono funzioni generatrici o ricorrenze per calcolarne facilmente il numero.

Bibliografia

  • Stanley, Richard P.;  Enumerative Combinatorics, Cambridge University Press, vol II, 1999.

Contattami

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