Solid partition

I matematik är solida partitioner naturliga generaliseringar av partitioner och plana partitioner definierade av Percy Alexander MacMahon . En solid partition av $n$ är en tredimensionell matris av icke-negativa heltal $n_{i,j,k}$ (med index ${ \displaystyle i,j,k\geq 1} )$ så att

\sum _{i,j,k}n_{i,j,k}=n

och

n_{i+1,j,k}\leq n_{i,j,k},\quad n_{i,j+1,k}\leq n_{i,j,k}\quad {\text{and }}\quad n_{i,j,k+1}\leq n_{i,j,k}

för alla

i,j{\text{ och }}k.

Låt $p_{3}(n)$ beteckna antalet solida partitioner av $n$ . Eftersom definitionen av solida partitioner involverar tredimensionella uppsättningar av tal, kallas de även tredimensionella partitioner i notation där plana partitioner är tvådimensionella partitioner och partitioner är endimensionella partitioner. Solida partitioner och deras högre dimensionella generaliseringar diskuteras i boken av Andrews .

Ferrers diagram för solida partitioner

En annan representation för solida partitioner är i form av Ferrers- diagram. Ferrers-diagrammet för en solid partition av $n$ är en samling av $n$ punkter eller noder , ${\displaystyle \lambda =(\ mathbf {y} _{1},\mathbf {y} _{2},\ldots ,\mathbf {y} _{n})} , med y i$ ∈ $\mathbf {y} _ {i}\in \mathbb {Z} _{\geq 0}^{4}}$ som uppfyller villkoret:

Villkor FD: Om noden

\mathbf {a} =(a_{1},a_{2},a_{3},a_{ 4})\in \lambda

, då gör alla noder

\mathbf {y} =(y_{1},y_{2}, y_{3},y_{4})

med

0\leq y_{i}\leq a_{i}

för alla

i =1,2,3,4

.

Till exempel Ferrers-diagrammet

\left({\begin{smallmatrix}0\\0\\0\\0\end{smallmatrix}}{\begin{smallmatrix}0\\0\\1\ \0\end{smallmatrix}}{\begin{smallmatrix}0\\1\\0\\0\end{smallmatrix}}{\begin{smallmatrix}1\\0\\0\\0\end{smallmatrix} }}{\begin{smallmatrix}1\\1\\0\\0\end{smallmatrix}}\right)\ ,

där varje kolumn är en nod, representerar en solid partition på $5$ . Det finns en naturlig verkan av permutationsgruppen $S_{4}$ på ett Ferrers-diagram – detta motsvarar att permutera de fyra koordinaterna för alla noder. Detta generaliserar operationen som betecknas med konjugering på vanliga partitioner.

Likvärdighet mellan de två representationerna

Givet ett Ferrers-diagram, konstruerar man den solida partitionen (som i huvuddefinitionen) enligt följande.

Låt

n_{i,j,k}

vara antalet noder i Ferrers-diagrammet med koordinater av formen

{\ displaystyle (i-1,j-1,k-1,*)}

där

*

anger ett godtyckligt värde. Samlingen

n_{i,j,k}

bildar en solid partition. Man kan verifiera att villkor FD innebär att villkoren för en solid skiljevägg är uppfyllda.

Givet en uppsättning av $n_{i,j,k}$ som bildar en solid partition, erhåller man motsvarande Ferrers-diagram enligt följande.

Börja med Ferrers-diagrammet utan noder. För varje

{\displaystyle n_{i,j,k}} som inte är noll

, lägg till

n_{i,j,k}

noder

(i-1,j-1,k-1,y_{4})

för

0\leq y_ {4}<n_{i,j,k}

till Ferrers-diagrammet. Genom konstruktion är det lätt att se att villkor FD är uppfyllt.

Till exempel, Ferrers-diagrammet med $5$ -noder som anges ovan motsvarar den solida partitionen med

n_{1,1,1}=n_{ 2,1,1}=n_{1,2,1}=n_{1,1,2}=n_{2,2,1}=1

med alla andra $n_{i,j,k}$ försvinner.

Genererande funktion

Låt $p_{3}(0)\equiv 1$ . Definiera genereringsfunktionen för solida partitioner, $P_{3}(q)$ , med

P_{3}(q):=\sum _{n=0}^{\infty }p_{3}(n)q^{n}=1+q+4q^{2}+10q^ {3}+26q^{4}+59q^{5}+140q^{6}+\cdots .

Genereringsfunktionerna för heltalspartitioner och plana partitioner har enkla produktformler, på grund av Euler respektive MacMahon . Men en gissning om MacMahon misslyckas med att korrekt reproducera de solida partitionerna för 6. Det verkar som om det inte finns någon enkel formel för genereringsfunktionen för solida partitioner; i synnerhet kan det inte finnas någon formel som är analog med produktformlerna för Euler och MacMahon.

Exakt uppräkning med hjälp av datorer

Med tanke på avsaknaden av en explicit känd genereringsfunktion, har uppräkningarna av antalet solida partitioner för större heltal utförts numeriskt. Det finns två algoritmer som används för att räkna upp solida partitioner och deras högre dimensionella generaliseringar. Atkins verk. et al. använde en algoritm på grund av Bratley och McKay. År 1970 föreslog Knuth en annan algoritm för att räkna upp topologiska sekvenser som han använde för att utvärdera antalet solida partitioner av alla heltal $n\leq 28$ . Mustonen och Rajesh utökade uppräkningen för alla heltal $n\leq 50$ . 2010 föreslog S. Balakrishnan en parallell version av Knuths algoritm som har använts för att utöka uppräkningen till alla heltal $n\leq 72$ . Man hittar