Simple enumeration formulae related to Alternating Sign Matrices, Monotone Triangles and standard Young tableaux

Das Problem, alternierende Vorzeichenmatrizen fixer Größe zu zählen, zeichnet sich einerseits durch die Einfachheit der zugehörigen Abzählformel und andererseits durch die Komplexität ihres Beweises aus. Alternierende Vorzeichenmatrizen mit n Zeilen entsprechen umkehrbar eindeutig monotonen Dreiecken mit unterster Zeile (1,2,...,n). Fischers alternativer Beweis für das „Refined ASM Theorem“ basiert auf der Operatorformel für das Polynom alpha(n;k1,k2,…,kn) in n Variablen, dessen Auswertung an ganzzahligen Werten k1 < k2 < ... < kn gleich der Anzahl an monotonen Dreiecken mit unterster Zeile (k1,k2,...,kn) ist. Wir präsentieren zunächst die aktuellste Version dieses in sich abgeschlossenen Beweises für das „Refined ASM Theorem“. Anschließend betrachten wir Auswertungen von alpha(n;k1,k2,…,kn) an beliebigen, ganzzahligen Stellen und zeigen, dass diese als vorzeichenbehaftete Abzählung einer neuen Familie kombinatorischer Objekte namens „Generalized Monotone Triangles“ interpretiert werden kann. Durch Anwendung der eingeführten Methode beweisen wir eine von zahlreichen, erstaunlichen Identitäten, die Computerexperimente nahegelegt haben, nämlich alpha(2n;n,n,n-1,n-1,…,1,1) = alpha(n;1,2,…,n). Unser Versuch dieselbe Methode anzuwenden, um eine langjährige Vermutung zu einer verfeinerten Abzählung vertikal symmetrischer, alternierender Vorzeichenmatrizen zu beweisen, führt zu einer allgemeineren Vermutung über eine Familie multivariater Laurent-Polynome. Bemerkenswerterweise ist diese neue Vermutung unabhängig von alternierenden Vorzeichenmatrizen oder zugehörigen kombinatorischen Objekten und sollte daher einem großen Publikum zugänglich sein. Der letzte Teil der Dissertation befasst sich thematisch mit der Hakenlängenformel für die Anzahl der „standard Young tableaux“ einer fixen Partition. Wir betrachten eine naheliegende Verallgemeinerung des Sortieralgorithmus „jeu de taquin“ auf dem „double-tailed diamond“ und bestimmen die Verteilung des Outputs. Abschließend leiten wir eine einfache Produktformel für den Erwartungswert des Eintrags in Position (2,1) eines zufälligen „standard Young tableau“ einer fixen Partition her.The problem of enumerating Alternating Sign Matrices (ASMs) of fixed size distinguishes itself by both the simplicity of the corresponding counting formula and the complexity of its proof. The set of ASMs with n rows bijectively corresponds to the set of Monotone Triangles (MTs) with bottom row (1,2,…,n). Fischer’s alternative proof of the Refined ASM Theorem is based on the operator formula for the polynomial alpha(n;k1,k2,…,kn) in n variables which evaluates to the number of MTs with bottom row (k1,k2,…,kn) for all integers k1 < k2 < … < kn. We first present the most current version of this self-contained proof of the Refined ASM Theorem. After that we investigate evaluations of alpha(n;k1,k2,…,kn) at arbitrary integral arguments and show that in this case the evaluation equals a certain signed enumeration of a new family of combinatorial objects we call Generalized Monotone Triangles. By applying the introduced method, we prove one of many astonishing identities computer experiments indicated, namely alpha(2n;n,n,n-1,n-1,…,1,1) = alpha(n;1,2,…,n). Our attempt to apply the same method to prove a long-standing conjecture on a refined enumeration of vertically symmetric ASMs leads to a more general conjectural multivariate Laurent polynomial identity. The startling fact about this new conjecture is its independence from ASMs or related combinatorial objects, thus making it accessible for a broad audience. The final part of the thesis is themed around the hook-length formula for counting standard Young tableaux of fixed shape. We consider a natural generalization of the related sorting algorithm “jeu de taquin” on the double-tailed diamond poset and derive the distribution of its output. Finally, we deduce a simple product formula for the expected value of the entry in position (2,1) of a uniformly random standard Young tableau of fixed shape