Teaserowa gra Schützenberger

W matematyce , aw szczególności w kombinatoryce , gra teaserowa jest konstrukcją Marcela-Paula Schützenbergera wprowadzoną w Schützenberger (1977), która definiuje relację równoważności na wszystkich tablicach Younga . Poślizg jest transformacja gdzie liczby w tablicy są przemieszczane w sposób podobny do tego z tradycyjnej grze zwiastuna . Dwie tabele są równoważne w grze teaserowej, jeśli można je przekształcić w siebie za pomocą serii slajdów.

Wślizgiwanie się w grę złośliwą

Biorąc pod uwagę lewą tablicę Younga w lewej postaci , wybieramy pustą komórkę sąsiadującą z tablicą, którą można dodać do tablicy. Oznacza to, że ma stronę wspólną z komórką i nadal jest to lewy kształt. Istnieją dwa rodzaje ślizgaczy, w zależności od tego, czy znajdują się w lewej górnej, czy w prawej dolnej części . $T$ $\ lambda \ setminus \ mu$ $vs$ $vs$ $T$ ${\ displaystyle \ {c \} \ cup \ lambda \ setminus \ mu}$ $vs$ $T$

Załóżmy, że na początek znajduje się w lewym górnym rogu. Mamy przeciągnij liczbę celi obok w ; jeśli ma dwie sąsiednie komórki, bierzemy mniejszą z liczb, a jeśli liczby są równe, dolną komórkę: ta reguła zapewnia, że właściwość tabeli, która ma nie zmniejszające się wiersze i rosnące kolumny, jest zachowana. Jeśli właśnie opróżniona komórka nie ma sąsiada po prawej lub niżej, przeciąganie jest zakończone. W przeciwnym razie przeciągamy numer sąsiedniej komórki według tej samej reguły co poprzednio i kontynuujemy do końca. Na końcu wynikowa tablica jest zawsze tablicą Younga (niekoniecznie po lewej stronie). $vs$ $vs$ $vs$ $vs$

Drugi rodzaj poślizgu, gdy znajduje się w prawym dolnym rogu , działa w ten sam sposób, ale w przeciwnym kierunku. W tym przypadku przeciągamy liczbę do pustej komórki od sąsiada po lewej lub powyżej, biorąc większą liczbę liczb, jeśli istnieje wybór. Te dwa rodzaje poślizgu są wzajemnie odwrotne: poślizg jednego z dwóch typów może zostać odwrócony przez poślizg drugiego rodzaju. $vs$ $T$

Inwolucja Schützenbergera

Gra teaserowa pozwala na zdefiniowanie operacji na tablicach Younga o określonej postaci; operacja ta jest w rzeczywistości inwolucją, chociaż nie wynika to z definicji. Operacja jest następująca: zaczynamy od opróżnienia lewej górnej komórki, co przekształca tabelę w lewą tabelę. Następnie wykonujemy przesuwanie zajawek, aby przekształcić lewy stół w prawy. Zwalnia to komórkę na krawędzi stołu. Ta komórka jest wypełniona wartością odwrotną do liczby usuniętej w lewym górnym rogu. Ta ujemna wartość jest uważana za część nowej tabeli i jej pozycja nie zmieni się w następujących przypadkach. Dopóki w pierwotnej tabeli nadal istnieją wpisy, powtarzamy operację usuwania wartości w lewym górnym rogu, przesuwania drażniących i wstawiania wartości do zwolnionej komórki. Pod koniec tego procesu wartości ujemne są zmieniane, tak że wiersze i kolumny rosną. Na koniec odpowiednia stała jest dodawana do wszystkich danych wejściowych, aby uzyskać tablicę Younga z dodatnimi danymi wejściowymi. $x$ $-x$

Aplikacje

Dowolna lewa tablica Younga może zostać przekształcona w pojedynczą tablicę Younga przez sekwencję przesunięć, więc każda lewa tablica Younga jest równoważna tablicy Younga. Równoważność zdefiniowana przez zrazy jest w rzeczywistości taka sama, jak równoważność Knutha, która definiuje monoid plaxiczny .

Ta gra jest ściśle związana z korespondencją Robinsona-Schensteda-Knutha i regułą Littlewooda-Richardsona .

Bibliografia

(fr) Ten artykuł jest częściowo lub w całości zaczerpnięty z artykułu Wikipedii w języku angielskim zatytułowanego „ teaser game ” ( zobacz listę autorów ) .
(en) Jacques Désarménien , »Jeu de taquin« , w Michiel Hazewinkel , Encyclopædia of Mathematics , Springer ,2002( ISBN 978-1556080104 , czytaj online )
(en) Bruce E. Sagan , The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions , New York / Berlin / Heidelberg etc., Springer, coll. "Graduate Teksty matematyki" ( N O 203)2001, 2 II wyd. , 238 str. ( ISBN 0-387-95067-2 , czytaj online )
.
Marcel-Paul Schützenberger , „Korespondencja Robinsona” , w: Dominique Foata (redaktor), Kombinatoryka i reprezentacja grupy symetrycznej: Actes Round Table CNRS, Univ. Louis-Pasteur Strasbourg, Strasburg, 1976 , Springer, zb. „Notatki do wykładów z matematyki. „( N O 579)1977( ISBN 978-3-540-08143-2 , DOI 10.1007 / BFb0090012 ) , str. 59–113
(en) Richard P. Stanley , Enumerative Combinatorics , vol. 2 [ szczegóły wydań ] ( prezentacja online )