Tabella di Young

In matematica, una tabella di Young, detta anche tavola di Young e tableau di Young, è una configurazione combinatorica ampiamente utilizzata nella teoria delle rappresentazioni. Le tavole di Young forniscono codifiche utili per descrivere le rappresentazioni di un gruppo simmetrico e per studiare le loro proprietà.

Le tavole di Young furono introdotte nel 1900 da Alfred Young, allora docente di matematica dell'University of Cambridge. Furono poi applicate allo studio dei gruppi simmetrici da Georg Frobenius nel 1903. La teoria fu in seguito sviluppata da Alfred Young e da molti altri matematici, tra i quali in particolare Percy MacMahon, G. de B. Robinson, Marcel-Paul Schützenberger, Alain Lascoux, Gian-Carlo Rota e Richard P. Stanley. Le tavole di Young in effetti costituiscono un tema centrale anche per gli sviluppi della odierna combinatoria algebrica.

Un diagramma di Ferrers

Un diagramma di Ferrers (chiamato anche diagramma di Young) è un modo di rappresentare la partizione di un numero intero positivo. Sia n un tale numero; una partizione di n riguarda un modo di esprimere tale intero come somma di numeri positivi: n = k₁ + k₂ + ... + k_m, dove k₁ ≥ k₂ ≥ .... Una partizione di n è quindi una sequenza non crescente di interi positivi di peso n. Questa sequenza, se ha m componenti può essere descritta dallo schema visivo formato da m righe di celle quadrate allineate sulla sinistra, con la prima riga che contiene k₁ celle, la seconda riga che contiene k₂ celle, etc. È tale schema che viene chiamato diagramma di Ferrers.

Questa partizione, cioè questa sequenza, si può identificare con la scrittura concisa

${\displaystyle \mathbf {k} =\langle k_{1},k_{2},\dots ,k_{m}\rangle }$ .

Per partizione coniugata della k si intende la partizione di n che consiste nei numeri delle celle delle successive colonne del diagramma. Quindi ad ogni diagramma di Ferrers risulta associato il diagramma coniugato il quale può essere individuato come schema ottenuto riflettendo il diagramma dato rispetto alla diagonale.

La figura sulla destra mostra il diagramma di Young che corrisponde alla partizione 10 = 5 + 4 + 1. La partizione coniugata è 10 = 3 + 2 + 2 + 2 + 1.

Una tabella di Young

Una tabella di Young si ottiene prendendo un diagramma di Ferrers e scrivendo dei numeri positivi 1, 2, ... nelle n celle di questo diagramma, rispettando i seguenti vincoli:

• in ogni riga, i numeri inseriti devono essere non decrescenti da sinistra verso destra;
• in ogni colonna, i numeri inseriti devono essere non decrescenti dall'alto verso il basso.

Il numero associato ad una cella viene detto anche valore della cella. L'insieme dei valori delle celle di una tabella di Young Y si dice codominio della Y

Se nelle celle compaiono gli interi 1, 2, ..., n, ciascuno in una e una sola cella, il tableau è chiamato tabella standard. La figura sulla destra mostra una delle tabelle standard di Young per la partizione 10 = 5 + 4 + 1. Evidentemente per una tabella standard, scorrendo da sinistra a destra le righe e dall'alto in basso le colonne si ottengono sequenze numeriche (strettamente) crescenti.

Le tabelle semi-standard sono generalizzazioni delle standard nelle quali un numero può apparire in più di una cella (si parla allora di valore con molteplicità maggiore di uno). Per le tabelle semi-standard, il primo vincolo descritto sopra è indebolito:

• scorrendo ogni riga da sinistra verso destra si ha una sequenza non decrescente di valori.

In genere si chiede che i valori nelle celle di una tabella semi-standard costituiscano un sottoinsieme di { 1, 2, ..., t }, dove il valore massimo t è generalmente specificato esplicitamente. Non tutti i numeri dell'insieme {1, 2, ..., t} devono apparire in una tabella di Young semi-standard di valore massimo t: alcuni possono apparire più di una volta. Dato che i numeri devono crescere all'interno di ogni colonna, perché la tabella semi-standard di Young esista deve essere ${\displaystyle t\geq m}$ .

I diagrammi di Ferrers sono in corrispondenza biunivoca con le rappresentazioni irriducibili del gruppo simmetrico sul campo dei numeri complessi. Inoltre essi consentono di specificare completamente i simmetrizzatori di Young, operatori che permettono di costruire effettivamente le rappresentazioni irriducibili. Molti aspetti di una rappresentazione possono essere dedotti dal corrispondente diagramma. Sotto, descriviamo due esempi di costruzioni che contribuiscono a determinare le rappresentazioni: determinazione della dimensione di una rappresentazione e rappresentazioni ristrette. In entrambi i casi, vedremo come molte proprietà di una rappresentazione possono essere determinati operando semplicemente sul suo diagramma.

Hook lengths

La dimensione di una rappresentazione irriducibile ${\displaystyle {\pi _{\lambda }}}$ che corrisponde ad una partizione ${\displaystyle \lambda }$ è uguale al numero di tabelle di Young diverse che si può ottenere dal diagramma della rappresentazione. Questo numero può essere calcolato dalla formula della hook length, o formula delle lunghezze dei ganci.

La hook length di una cella ${\displaystyle x}$ in un diagramma ${\displaystyle \lambda }$, che denotiamo con ${\displaystyle \operatorname {hook} _{\lambda }(x)}$, si definisce come il numero di celle che si trovano nella stessa riga alla sua destra e nella stessa colonna al di sotto di essa aumentato di uno per tener conto della stessa cella x. La formula di hook-length dice che la dimensione di una rappresentazione irriducibile è data da n! diviso il prodotto delle hook lengths di tutte le celle nel diagramma della rappresentazione:

${\displaystyle {\rm {dim}}\,\pi _{\lambda }={\frac {n!}{\prod _{x\in \lambda }{\rm {hook}}_{\lambda }(x)}}.}$

La figura sulla destra mostra le hook-lengths per tutte le celle nel diagramma della partizione 10 = 5 + 4 + 1. Quindi per la dimensione della rappresentazione del gruppo simmetrico di n oggetti S_n individuata da ${\displaystyle \lambda }$ = [5 + 4 + 1] si ha

${\displaystyle {\rm {dim}}\,\pi _{\lambda }={\frac {10!}{1\cdot 1\cdot 1\cdot 2\cdot 3\cdot 3\cdot 4\cdot 5\cdot 5\cdot 7}}=288}$.

Una rappresentazione del gruppo simmetrico di n oggetti, è rappresentazione anche del gruppo simmetrico di n − 1 elementi, S_n−1. Tuttavia, una rappresentazione irriducibile di S_n potrebbe non essere irriducibile per S_n−1: infatti potrebbe essere somma diretta di più rappresentazioni che sono irriducibili per S_n−1. Queste rappresentazioni sono chiamate rappresentazioni indotte. Data una rappresentazione di S_n attraverso un diagramma di Young, si pone il problema di determinare le corrispondenti rappresentazioni indotte.

La risposta è che le rappresentazioni indotte sono esattamente le rappresentazioni caratterizzate da diagrammi di Young che si possono ottenere cancellando un quadrato dal diagramma di Young della rappresentazione di S_n. Si osserva che i diagrammi validi di n - 1 celle ottenibili cancellando una cella da un diagramma di n celle si possono ottenere solo cancellando le celle che non hanno celle né alla loro destra ne al di sotto, ovvero le celle con lunghezza di gancio uguale a 1.

Una tabella di Young può essere usata per costruire le rappresentazioni del gruppo simmetrico su un campo arbitrario e per studiare la loro struttura. In generale le rappresentazioni ottenute da tabelle non standard non sono irriducibili.

• Algoritmo di Robinson-Schensted
• Partizione di un intero
• Polinomio
• Rappresentazione dei gruppi

• Wikimedia Commons contiene immagini o altri file su tabella di Young

• (EN) Eric W. Weisstein, Tabella di Young, su MathWorld, Wolfram Research.
• William Fulton. Young Tableaux, with Applications to Representation Theory and Geometry. Cambridge University Press, 1997.
• William Fulton and Joe Harris, Representation Theory, A First Course (1991) Springer Verlag New York, ISBN 0-387-97495-4 See Chapter 4
• Bruce E. Sagan. The Symmetric Group. Springer, 2001
• Eric W. Weisstein. "Ferrers Diagram". From MathWorld--A Wolfram Web Resource.
• Jean-Christophe Novelli, Igor Pak, Alexander V. Stoyanovkii, "A direct bijective proof of the Hook-length formula", Discrete Mathematics and Theoretical Computer Science 1 (1997), pp.53–67.

V · D · M Combinatoria
Orientamento generale	Combinatoria · Storia della combinatoria · Matematica discreta · Sezione 05-XX di MSC
Nozioni introduttive	Permutazioni · Disposizioni · Combinazioni · Coefficienti binomiali · Partizioni di interi · Partizioni di insiemi finiti - Identità combinatorie e biiezioni · Principio dei cassetti
Configurazioni	Quadrati latini · Quadrati magici · Disegni a blocchi · Geometrie finite · Matroidi - Tassellazioni · Polimini
Teoria dei grafi	Alberi · Cammini sui grafi (euleriani, hamiltoniani) · Connessione nei grafi - Grafi planari · Colorazione dei grafi e teorema dei quattro colori) · Ipergrafi · Grafi e gruppi · Digrafo · Flussi su grafi · Passeggiate aleatorie su grafi · Omomorfismo fra grafi · Algoritmi sui grafi
Combinatoria algebrica	Tavola di Young · Funzioni simmetriche - Serie formale di potenze · Funzioni generatrici · Polinomi ortogonali · Azioni di un gruppo su strutture combinatorie - Aspetti combinatorici dell'algebra commutativa
Altre aree	Calcolo umbrale (sequenze polinomiali di tipo binomiale · sequenze di Sheffer) - Combinatoria estremale

Portale Matematica: accedi alle voci di Teknopedia che trattano di matematica