Young-tableau

In de representatietheorie is een young-tableau een grafische voorstelling die bij de representatie van een symmetrische groep wordt gebruikt. Ze worden ook in de combinatoriek en algebraïsche meetkunde toegepast. Young-tableaus zijn naar de wiskundige Alfred Young uit Engeland genoemd, die ze in 1900 introduceerde,

Definities

Young-diagram

Young-diagram met vorm [5,4,1]

Een young-diagram of ferrersdiagram is een eindige verzameling van vakjes of cellen, gerangschikt in rijen die links zijn uitgelijnd, op een zodanige wijze dat het aantal vakjes in een rij nooit kleiner is dat het aantal vakjes in de rij eronder. Het aantal vakjes in de rijen is met andere woorden een niet-stijgende rij.

De opsomming van het aantal vakjes in iedere rij bepaalt de vorm van het diagram en vormt een partitie van de verzameling $\{1,\ldots ,n\},$ met $n$ het totale aantal vakjes in het diagram. Elke rij in het diagram is een deelverzameling van de partitie.

Een young-diagram wordt traditioneel met een Griekse letter $\lambda$ aangeduid, de partitie met $[\lambda _{1},\lambda _{2},\ldots ]$, het young-diagram hiernaast dus met $\lambda [5,4,1]$.

Een young-diagram kan om de diagonaal worden gespiegeld, waarbij rijen en kolommen worden omgewisseld. Men krijgt dan een nieuw young-diagram, het geconjugeerde diagram. Bijvoorbeeld een diagram met vorm [4,3,3,2] wordt omgezet in het geconjugeerde diagram met vorm [4,4,3,1]. Het geconjugeerde diagram van het hiernaast afgebeelde diagram heeft als vorm [3,2,2,2,1].

Young-diagrammen kunnen worden opgevuld. Een opvulling van een diagram is een diagram waarin elk vakje gevuld is met een positief geheel getal, of meer algemeen met een element uit een verzameling waarop een totale orde is gedefinieerd. Voor de eenvoud gebruikt men doorgaans de positieve gehele getallen 1, 2, 3, ...

De hier gebruikte voorstelling van young-diagrammen noemt men de 'Engelse notatie'. Er bestaat ook een 'Franse notatie', waarin het diagram ondersteboven wordt getekend, met de langste rij onderaan.

Young-tableau

Een standaard young-tableau met n=10 vakjes

Een young-tableau is een opvulling van een young-diagram die aan bepaalde voorwaarden voldoet. Men maakt een onderscheid tussen een semistandaard young-tableau en een standaard young-tableau.

Een semistandaard young-tableau voldoet aan de volgende voorwaarden:

• in elke rij vormen de getallen een niet-dalende rij, ieder getal is kleiner dan of gelijk aan het getal rechts ervan en
• in elke kolom vormen de getallen een strikt stijgende rij, elk getal is kleiner dan het getal eronder, als dat er is.

Een standaard young-tableau voldoet aan de voorwaarden:

• in elke rij en in elke kolom vormen de getallen een strikt stijgende rij
• alle getallen in het tableau zijn verschillend.

In een standaard young-tableau met $n$ vakjes staan dus de eerste $n$ positieve gehele getallen. In een semistandaard young-tableau kunnen er minder dan $n$ verschillende getallen staan, maar minstens het aantal rijen in het diagram. Het geconjugeerde tableau van een standaard young-tableau is ook standaard.

Scheef young-diagram en young-tableau

Scheef young-tableau ontstaan door $\mu [2,1]$ te verwijderen uit $\lambda [5,4,2,2]$

Een scheef young-diagram ontstaat als uit een young-diagram $\lambda$ een ander, kleiner young-diagram $\mu$ in de linkerbovenhoek wordt weggenomen. Het resterende scheve diagram, $\lambda /\mu$ is de verschilverzameling van de vakjes die behoren tot $\lambda$ maar niet tot $\mu$.

Scheve young-tableaus definieert men dan op dezelfde wijze als hierboven: semistandaard als de opeenvolgende getallen in een rij niet-dalend zijn en in een kolom strikt stijgend; standaard als ze zowel in rijen als kolommen strikt stijgend zijn en alle getallen van 1 tot het aantal vakjes in het tableau eenmaal erin voorkomen.

Voor een scheef young-diagram volstaat het niet het aantal vakjes in elke rij op te sommen om de vorm van het diagram te kennen; men moet ook de vorm van het weggelaten diagram kennen. Het diagram hiernaast wordt daarom genoteerd als [5,4,2,2]/[2,1].

Aantallen young-tableaus

Een semistandaard young-tableau kan men aanduiden met $(\lambda ,n,k),$ waarin $\lambda$ de partitie is, bijvoorbeeld [5,4,2,2], $n$ het totaal aantal vakjes en $k$ het maximaal aantal getallen in het tableau. $k$ is ten minste gelijk aan het aantal rijen in het tableau en ten hoogste gelijk aan $n.$ Het aantal verschillende manieren om zo een semistandaard young-tableau maken met de getallen $1,\ldots ,k$ bepaalt men als volgt:

1. Bepaal voor elk vakje in het tableau de 'hoeklengte', dit is het aantal vakjes rechts van het vakje in dezelfde rij, plus het aantal vakjes onder het vakje in dezelfde kolom, plus 1. Vermenigvuldig de hoeklengtes van alle vakjes.
2. Schrijf in elk vakje in het tableau het getal $k+j-i,$ waarin $i$ het volgnummer van de rij is en $j$ het volgnummer van de kolom. De nummering begint linksboven bij nul. Vermenigvuldig al deze getallen.
3. Deel het product uit stap 2 door het product uit stap 1. Dit is het aantal mogelijke semistandaard young-tableaus.

Voorbeeld: bepaal het aantal semistandaard young-tableaus ([2,1], 3, 3), dus van de vorm

[ ][ ]
[ ]

1. de hoeklengten zijn:

[3][1]
[1]

2. de getallen $k+j-i$ zijn:

[3][4]
[2]

3. het aantal is dus: (3.4.2)/(3.1.1) = 8. Er zijn inderdaad acht verschillende geldige opvullingen mogelijk:

[1][1]  [1][1]  [1][2]  [1][2]  [1][3]  [1][3]  [2][2]  [2][3]  
[2]     [3]     [2]     [3]     [2]     [3]     [3]     [3]     

Dit is de verzameling SSYT([2,1], 3, 2). De standaard young-tableaus van de vorm [2,1] vormen daar een deelverzameling van, namelijk:

[1][2]  [1][3]  
[3]     [2]     

Behalve deze twee zijn er nog twee andere standaard young-tableaus met drie vakjes:

[1]  en  [1][2][3]
[2]
[3]

Het aantal standaard young-tableaus met $n=0,1,2,3,\ldots$ vakjes wordt gegeven door de rij:

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ...

Tralie van Young

De tralie van Young is een partieel geordende verzameling en een tralie die bestaat uit alle gehele partities. Ze bevat alle young-diagrammen met 0,1, 2, 3, ... vakjes en kan met een hasse-diagram worden weergegeven:

De rijen in dit diagram geven alle mogelijke partities aan van verzamelingen met $n=0,1,2,3,\ldots$ elementen. Het aantal diagrammen (partities) op elke rij is de waarde van de partitiefunctie $p(n):p(1)=2,p(2)=2,p(3)=3,p(4)=5,\ldots$

De verbindingen geven aan welke young-diagrammen kunnen ontstaan door één vakje aan een young-diagram toe te voegen of er één vakje uit weg te nemen. Een young-diagram met $n$ vakjes kan op de volgende manieren naar een diagram met $n+1$ vakjes worden uitgebreid:

• voeg een vakje toe aan de bovenste lijn
• voeg een vakje toe aan een lijn die korter is dan de lijn erboven
• voeg onderaan een nieuwe lijn toe met één vakje.

Een young-diagram met $n$ vakjes kan op de volgende manieren worden verkleind naar een diagram met $n-1$ vakjes:

• verwijder het meest rechtse vakje in de onderste lijn, als er maar één vakje in die lijn staat verdwijnt het uit het diagram
• verwijder het meest rechtse vakje in een lijn die langer is dan de lijn eronder.

Jeu de taquin

Een jeu de taquin-verschuiving verschuift de getallen in een young-tableau op dezelfde manier als in een schuifpuzzel en bepaalt een equivalentierelatie op de verzameling getallen in het tableau .

Voetnoten