DMTCS Proceedings vol. AN, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010)

---

1. Crossings and nestings in set partitions of classical types

Martin Rubey ; Christian Stump.

In this extended abstract, we investigate bijections on various classes of set partitions of classical types that preserve openers and closers. On the one hand we present bijections for types $B$ and $C$ that interchange crossings and nestings, which generalize a construction by Kasraoui and Zeng for type $A$. On the other hand we generalize a bijection to type $B$ and $C$ that interchanges the cardinality of a maximal crossing with the cardinality of a maximal nesting, as given by Chen, Deng, Du, Stanley and Yan for type $A$. For type $D$, we were only able to construct a bijection between non-crossing and non-nesting set partitions. For all classical types we show that the set of openers and the set of closers determine a non-crossing or non-nesting set partition essentially uniquely.

---

2. A Pieri rule for skew shapes

Sami H. Assaf ; Peter R. W. McNamara.

The Pieri rule expresses the product of a Schur function and a single row Schur function in terms of Schur functions. We extend the classical Pieri rule by expressing the product of a skew Schur function and a single row Schur function in terms of skew Schur functions. Like the classical rule, our rule involves simple additions of boxes to the original skew shape. Our proof is purely combinatorial and extends the combinatorial proof of the classical case.

---

3. Compositions and samples of geometric random variables with constrained multiplicities

Margaret Archibald ; Arnold Knopfmacher ; Toufik Mansour.

We investigate the probability that a random composition (ordered partition) of the positive integer $n$ has no parts occurring exactly $j$ times, where $j$ belongs to a specified finite $\textit{`forbidden set'}$ $A$ of multiplicities. This probability is also studied in the related case of samples $\Gamma =(\Gamma_1,\Gamma_2,\ldots, \Gamma_n)$ of independent, identically distributed random variables with a geometric distribution.

---

4. The spectrum of an asymmetric annihilation process

Arvind Ayyer ; Volker Strehl.

In recent work on nonequilibrium statistical physics, a certain Markovian exclusion model called an asymmetric annihilation process was studied by Ayyer and Mallick. In it they gave a precise conjecture for the eigenvalues (along with the multiplicities) of the transition matrix. They further conjectured that to each eigenvalue, there corresponds only one eigenvector. We prove the first of these conjectures by generalizing the original Markov matrix by introducing extra parameters, explicitly calculating its eigenvalues, and showing that the new matrix reduces to the original one by a suitable specialization. In addition, we outline a derivation of the partition function in the generalized model, which also reduces to the one obtained by Ayyer and Mallick in the original model.

---

5. Weakly directed self-avoiding walks

Axel Bacher ; Mireille Bousquet-Mélou.

We define a new family of self-avoiding walks (SAW) on the square lattice, called $\textit{weakly directed walks}$. These walks have a simple characterization in terms of the irreducible bridges that compose them. We determine their generating function. This series has a complex singularity structure and in particular, is not D-finite. The growth constant is approximately 2.54 and is thus larger than that of all natural families of SAW enumerated so far (but smaller than that of general SAW, which is about 2.64). We also prove that the end-to-end distance of weakly directed walks grows linearly. Finally, we study a diagonal variant of this model.

---

6. The Homology of the Real Complement of a $k$-parabolic Subspace Arrangement

Christopher Severs ; Jacob A. White.

The $k$-parabolic subspace arrangement, introduced by Barcelo, Severs and White, is a generalization of the well known $k$-equal arrangements of type-$A$ and type-$B$. In this paper we use the discrete Morse theory of Forman to study the homology of the complements of $k$-parabolic subspace arrangements. In doing so, we recover some known results of Björner et al. and provide a combinatorial interpretation of the Betti numbers for any $k$-parabolic subspace arrangement. The paper provides results for any $k$-parabolic subspace arrangement, however we also include an extended example of our methods applied to the $k$-equal arrangements of type-$A$ and type-$B$. In these cases, we obtain new formulas for the Betti numbers.

---

7. Fully Packed Loop configurations in a triangle and Littlewood Richardson coefficients

Philippe Nadeau.

We are interested in Fully Packed Loops in a triangle (TFPLs), as introduced by Caselli at al. and studied by Thapper. We show that for Fully Packed Loops with a fixed link pattern (refined FPL), there exist linear recurrence relations with coefficients computed from TFPL configurations. We then give constraints and enumeration results for certain classes of TFPL configurations. For special boundary conditions, we show that TFPLs are counted by the famous Littlewood Richardson coefficients.

---

8. Pattern avoidance in alternating permutations and tableaux (extended abstract)

Joel Brewster Lewis.

We give bijective proofs of pattern-avoidance results for a class of permutations generalizing alternating permutations. The bijections employed include a modified form of the RSK insertion algorithm and recursive bijections based on generating trees. As special cases, we show that the sets $A_{2n}(1234)$ and $A_{2n}(2143)$ are in bijection with standard Young tableaux of shape $\langle 3^n \rangle$. Alternating permutations may be viewed as the reading words of standard Young tableaux of a certain skew shape. In the last section of the paper, we study pattern avoidance in the reading words of standard Young tableaux of any skew shape. We show bijectively that the number of standard Young tableaux of shape $\lambda / \mu$ whose reading words avoid $213$ is a natural $\mu$-analogue of the Catalan numbers. Similar results for the patterns $132$, $231$ and $312$.

---

9. Unitary Matrix Integrals, Primitive Factorizations, and Jucys-Murphy Elements

Sho Matsumoto ; Jonathan Novak.

A factorization of a permutation into transpositions is called "primitive'' if its factors are weakly ordered.We discuss the problem of enumerating primitive factorizations of permutations, and its place in the hierarchy of previously studied factorization problems. Several formulas enumerating minimal primitive and possibly non-minimal primitive factorizations are presented, and interesting connections with Jucys-Murphy elements, symmetric group characters, and matrix models are described.

---

10. Zonotopes, toric arrangements, and generalized Tutte polynomials

Luca Moci.

We introduce a multiplicity Tutte polynomial $M(x,y)$, which generalizes the ordinary one and has applications to zonotopes and toric arrangements. We prove that $M(x,y)$ satisfies a deletion-restriction recurrence and has positive coefficients. The characteristic polynomial and the Poincaré polynomial of a toric arrangement are shown to be specializations of the associated polynomial $M(x,y)$, likewise the corresponding polynomials for a hyperplane arrangement are specializations of the ordinary Tutte polynomial. Furthermore, $M(1,y)$ is the Hilbert series of the related discrete Dahmen-Micchelli space, while $M(x,1)$ computes the volume and the number of integral points of the associated zonotope.

---

11. Involutions of the Symmetric Group and Congruence B-Orbits (Extended Abstract)

Eli Bagno ; Yonah Cherniavsky.

We study the poset of Borel congruence classes of symmetric matrices ordered by containment of closures. We give a combinatorial description of this poset and calculate its rank function. We discuss the relation between this poset and the Bruhat poset of involutions of the symmetric group. Also we present the poset of Borel congruence classes of anti-symmetric matrices ordered by containment of closures. We show that there exists a bijection between the set of these classes and the set of involutions of the symmetric group. We give two formulas for the rank function of this poset.

---

12. Harmonics for deformed Steenrod operators (Extended Abstract)

François Bergeron ; Adriano Garsia ; Nolan Wallach.

We explore in this paper the spaces of common zeros of several deformations of Steenrod operators. Proofs are omitted in view of pages limitation for the extended abstract. \par

---

13. The Geometry of Lecture Hall Partitions and Quadratic Permutation Statistics

Katie L. Bright ; Carla D. Savage.

We take a geometric view of lecture hall partitions and anti-lecture hall compositions in order to settle some open questions about their enumeration. In the process, we discover an intrinsic connection between these families of partitions and certain quadratic permutation statistics. We define some unusual quadratic permutation statistics and derive results about their joint distributions with linear statistics. We show that certain specializations are equivalent to the lecture hall and anti-lecture hall theorems and another leads back to a special case of a Weyl group generating function that "ought to be better known.''

---

14. A preorder-free construction of the Kazhdan-Lusztig representations of Hecke algebras $H_n(q)$ of symmetric groups

Charles Buehrle ; Mark Skandera.

We use a quantum analog of the polynomial ring $\mathbb{Z}[x_{1,1},\ldots, x_{n,n}]$ to modify the Kazhdan-Lusztig construction of irreducible $H_n(q)$-modules. This modified construction produces exactly the same matrices as the original construction in [$\textit{Invent. Math.}$ $\textbf{53}$ (1979)], but does not employ the Kazhdan-Lusztig preorders. Our main result is dependent on new vanishing results for immanants in the quantum polynomial ring.

---

15. On $k$-crossings and $k$-nestings of permutations

Sophie Burrill ; Marni Mishna ; Jacob Post.

We introduce $k$-crossings and $k$-nestings of permutations. We show that the crossing number and the nesting number of permutations have a symmetric joint distribution. As a corollary, the number of $k$-noncrossing permutations is equal to the number of $k$-nonnesting permutations. We also provide some enumerative results for $k$-noncrossing permutations for some values of $k$.

---

16. The stability of the Kronecker product of Schur functions

Emmanuel Briand ; Rosa Orellana ; Mercedes Rosas.

In the late 1930's Murnaghan discovered the existence of a stabilization phenomenon for the Kronecker product of Schur functions. For $n$ large enough, the values of the Kronecker coefficients appearing in the product of two Schur functions of degree $n$ do not depend on the first part of the indexing partitions, but only on the values of their remaining parts. We compute the exact value of n when this stable expansion is reached. We also compute two new bounds for the stabilization of a particular coefficient of such a product. Given partitions $\alpha$ and $\beta$, we give bounds for all the parts of any partition $\gamma$ such that the corresponding Kronecker coefficient is nonzero. Finally, we also show that the reduced Kronecker coefficients are structure coefficients for the Heisenberg product introduced by Aguiar, Ferrer and Moreira.

---

17. Viewing counting polynomials as Hilbert functions via Ehrhart theory

Felix Breuer ; Aaron Dall.

Steingrímsson (2001) showed that the chromatic polynomial of a graph is the Hilbert function of a relative Stanley-Reisner ideal. We approach this result from the point of view of Ehrhart theory and give a sufficient criterion for when the Ehrhart polynomial of a given relative polytopal complex is a Hilbert function in Steingrímsson's sense. We use this result to establish that the modular and integral flow and tension polynomials of a graph are Hilbert functions.

---

18. Words and Noncommutative Invariants of the Hyperoctahedral Group

Anouk Bergeron-Brlek.

Let $\mathcal{B}_n$ be the hyperoctahedral group acting on a complex vector space $\mathcal{V}$. We present a combinatorial method to decompose the tensor algebra $T(\mathcal{V})$ on $\mathcal{V}$ into simple modules via certain words in a particular Cayley graph of $\mathcal{B}_n$. We then give combinatorial interpretations for the graded dimension and the number of free generators of the subalgebra $T(\mathcal{V})^{\mathcal{B}_n}$ of invariants of $\mathcal{B}_n$, in terms of these words, and make explicit the case of the signed permutation module. To this end, we require a morphism from the Mantaci-Reutenauer algebra onto the algebra of characters due to Bonnafé and Hohlweg.

---

19. A unified bijective method for maps: application to two classes with boundaries

Olivier Bernardi ; Eric Fusy.

Based on a construction of the first author, we present a general bijection between certain decorated plane trees and certain orientations of planar maps with no counterclockwise circuit. Many natural classes of maps (e.g. Eulerian maps, simple triangulations,...) are in bijection with a subset of these orientations, and our construction restricts in a simple way on the subset. This gives a general bijective strategy for classes of maps. As a non-trivial application of our method we give the first bijective proofs for counting (rooted) simple triangulations and quadrangulations with a boundary of arbitrary size, recovering enumeration results found by Brown using Tutte's recursive method.

---

20. Combinatorial aspects of Escher tilings

Alexandre Blondin Massé ; Srecko Brlek ; Sébastien Labbé.

In the late 30's, Maurits Cornelis Escher astonished the artistic world by producing some puzzling drawings. In particular, the tesselations of the plane obtained by using a single tile appear to be a major concern in his work, drawing attention from the mathematical community. Since a tile in the continuous world can be approximated by a path on a sufficiently small square grid - a widely used method in applications using computer displays - the natural combinatorial object that models the tiles is the polyomino. As polyominoes are encoded by paths on a four letter alphabet coding their contours, the use of combinatorics on words for the study of tiling properties becomes relevant. In this paper we present several results, ranging from recognition of these tiles to their generation, leading also to some surprising links with the well-known sequences of Fibonacci and Pell.

---

21. An Algebraic Analogue of a Formula of Knuth

Lionel Levine.

We generalize a theorem of Knuth relating the oriented spanning trees of a directed graph $G$ and its directed line graph $\mathcal{L} G$. The sandpile group is an abelian group associated to a directed graph, whose order is the number of oriented spanning trees rooted at a fixed vertex. In the case when $G$ is regular of degree $k$, we show that the sandpile group of $G$ is isomorphic to the quotient of the sandpile group of $\mathcal{L} G$ by its $k$-torsion subgroup. As a corollary we compute the sandpile groups of two families of graphs widely studied in computer science, the de Bruijn graphs and Kautz graphs.

---

22. QSym over Sym has a stable basis

Aaron Lauve ; Sarah K Mason.

We prove that the subset of quasisymmetric polynomials conjectured by Bergeron and Reutenauer to be a basis for the coinvariant space of quasisymmetric polynomials is indeed a basis. This provides the first constructive proof of the Garsia―Wallach result stating that quasisymmetric polynomials form a free module over symmetric polynomials and that the dimension of this module is $n!$.

---

23. Three notions of tropical rank for symmetric matrices

Dustin Cartwright ; Melody Chan.

We introduce and study three different notions of tropical rank for symmetric matrices and dissimilarity matrices in terms of minimal decompositions into rank 1 symmetric matrices, star tree matrices, and tree matrices. Our results provide a close study of the tropical secant sets of certain nice tropical varieties, including the tropical Grassmannian. In particular, we determine the dimension of each secant set, the convex hull of the variety, and in most cases, the smallest secant set which is equal to the convex hull.

---

24. Models and refined models for involutory reflection groups and classical Weyl groups

Fabrizio Caselli ; Roberta Fulci.

A finite subgroup $G$ of $GL(n,\mathbb{C})$ is involutory if the sum of the dimensions of its irreducible complex representations is given by the number of absolute involutions in the group, i.e. elements $g \in G$ such that $g \bar{g}=1$, where the bar denotes complex conjugation. A uniform combinatorial model is constructed for all non-exceptional irreducible complex reflection groups which are involutory including, in particular, all infinite families of finite irreducible Coxeter groups. If $G$ is a classical Weyl group this result is much refined in a way which is compatible with the Robinson-Schensted correspondence on involutions.

---

25. Chamber Structure For Double Hurwitz Numbers

Renzo Cavalieri ; Paul JOHNSON ; Hannah Markwig.

Double Hurwitz numbers count covers of the sphere by genus $g$ curves with assigned ramification profiles over $0$ and $\infty$, and simple ramification over a fixed branch divisor. Goulden, Jackson and Vakil (2005) have shown double Hurwitz numbers are piecewise polynomial in the orders of ramification, and Shadrin, Shapiro and Vainshtein (2008) have determined the chamber structure and wall crossing formulas for $g=0$. We provide new proofs of these results, and extend them in several directions. Most importantly we prove wall crossing formulas for all genera. The main tool is the authors' previous work expressing double Hurwitz number as a sum over labelled graphs. We identify the labels of the graphs with lattice points in the chambers of certain hyperplane arrangements, which give rise to piecewise polynomial functions. Our understanding of the wall crossing for these functions builds on the work of Varchenko (1987). This approach to wall crossing appears novel, and may be of broader interest. This extended abstract is based on a new preprint by the authors.

---

26. Random Walks in the Plane

Jonathan M. Borwein ; Dirk Nuyens ; Armin Straub ; James Wan.

We study the expected distance of a two-dimensional walk in the plane with unit steps in random directions. A series evaluation and recursions are obtained making it possible to explicitly formulate this distance for small number of steps. Formulae for all the moments of a 2-step and a 3-step walk are given, and an expression is conjectured for the 4-step walk. The paper makes use of the combinatorical features exhibited by the even moments which, for instance, lead to analytic continuations of the underlying integral.

---

27. Computing Node Polynomials for Plane Curves

Florian Block.

According to the Göttsche conjecture (now a theorem), the degree $N^{d, \delta}$ of the Severi variety of plane curves of degree $d$ with $\delta$ nodes is given by a polynomial in $d$, provided $d$ is large enough. These "node polynomials'' $N_{\delta} (d)$ were determined by Vainsencher and Kleiman―Piene for $\delta \leq 6$ and $\delta \leq 8$, respectively. Building on ideas of Fomin and Mikhalkin, we develop an explicit algorithm for computing all node polynomials, and use it to compute $N_{\delta} (d)$ for $\delta \leq 14$. Furthermore, we improve the threshold of polynomiality and verify Göttsche's conjecture on the optimal threshold up to $\delta \leq 14$. We also determine the first 9 coefficients of $N_{\delta} (d)$, for general $\delta$, settling and extending a 1994 conjecture of Di Francesco and Itzykson.

---

28. The expansion of Hall-Littlewood functions in the dual Grothendieck polynomial basis

Jason Bandlow ; Jennifer Morse.

A combinatorial expansion of the Hall-Littlewood functions into the Schur basis of symmetric functions was first given by Lascoux and Schützenberger, with their discovery of the charge statistic. A combinatorial expansion of stable Grassmannian Grothendieck polynomials into monomials was first given by Buch, using set-valued tableaux. The dual basis of the stable Grothendieck polynomials was given a combinatorial expansion into monomials by Lam and Pylyavskyy using reverse plane partitions. We generalize charge to set-valued tableaux and use all of these combinatorial ideas to give a nice expansion of Hall-Littlewood polynomials into the dual Grothendieck basis. \par

---

29. Counting unicellular maps on non-orientable surfaces

Olivier Bernardi ; Guillaume Chapuy.

A unicellular map is the embedding of a connected graph in a surface in such a way that the complement of the graph is a topological disk. In this paper we give a bijective operation that relates unicellular maps on a non-orientable surface to unicellular maps of a lower topological type, with distinguished vertices. From that we obtain a recurrence equation that leads to (new) explicit counting formulas for non-orientable precubic (all vertices of degree 1 or 3) unicellular maps of fixed topology. We also determine asymptotic formulas for the number of all unicellular maps of fixed topology, when the number of edges goes to infinity. Our strategy is inspired by recent results obtained for the orientable case [Chapuy, PTRF 2010], but significant novelties are introduced: in particular we construct an involution which, in some sense, ``averages'' the effects of non-orientability. \par

---

30. A canonical basis for Garsia-Procesi modules

Jonah Blasiak.

We identify a subalgebra $\widehat{\mathscr{H}}^+_n$ of the extended affine Hecke algebra $\widehat{\mathscr{H}}_n$ of type $A$. The subalgebra $\widehat{\mathscr{H}}^+_n$ is a u-analogue of the monoid algebra of $\mathcal{S}_n ⋉ℤ_≥0^n$ and inherits a canonical basis from that of $\widehat{\mathscr{H}}_n$. We show that its left cells are naturally labeled by tableaux filled with positive integer entries having distinct residues mod $n$, which we term positive affine tableaux (PAT). We then exhibit a cellular subquotient $\mathscr{R}_1^n$ of $\widehat{\mathscr{H}}^+_n$ that is a $u$-analogue of the ring of coinvariants $ℂ[y_1,\ldots,y_n]/(e_1, \ldots,e_n)$ with left cells labeled by PAT that are essentially standard Young tableaux with cocharge labels. Multiplying canonical basis elements by a certain element $*π ∈ \widehat{\mathscr{H}}^+_n$ corresponds to rotations of words, and on cells corresponds to cocyclage. We further show that $\mathscr{R}_1^n$ has cellular quotients $\mathscr{R}_λ$ that are $u$-analogues of the Garsia-Procesi modules $R_λ$ with left cells labeled by (a PAT version of) the $λ$ -catabolizable tableaux.

---

31. Generalized Ehrhart polynomials

Sheng Chen ; Nan Li ; Steven V Sam.

Let $P$ be a polytope with rational vertices. A classical theorem of Ehrhart states that the number of lattice points in the dilations $P(n) = nP$ is a quasi-polynomial in $n$. We generalize this theorem by allowing the vertices of $P(n)$ to be arbitrary rational functions in $n$. In this case we prove that the number of lattice points in $P(n)$ is a quasi-polynomial for $n$ sufficiently large. Our work was motivated by a conjecture of Ehrhart on the number of solutions to parametrized linear Diophantine equations whose coefficients are polynomials in $n$, and we explain how these two problems are related.

---

32. Descent polynomials for permutations with bounded drop size

Fan Chung ; Anders Claesson ; Mark Dukes ; Ronald Graham.

Motivated by juggling sequences and bubble sort, we examine permutations on the set${1, 2, \ldots, n}$ with $d$ descents and maximum drop size $k$. We give explicit formulas for enumerating such permutations for given integers $k$ and $d$. We also derive the related generating functions and prove unimodality and symmetry of the coefficients.

---

33. Combinatorics of the PASEP partition function

Matthieu Josuat-Vergès.

We consider a three-parameter PASEP model on $N$ sites. A closed formula for the partition function was obtained analytically by Blythe et al. We give a new formula which generalizes the one of Blythe et al, and is proved in two combinatorial ways. Moreover the first proof can be adapted to give the moments of Al-Salam-Chihara polynomials.

---

34. Generalized Energy Statistics and Kostka―Macdonald Polynomials

Anatol N. Kirillov ; Reiho Sakamoto.

We give an interpretation of the $t=1$ specialization of the modified Macdonald polynomial as a generating function of the energy statistics defined on the set of paths arising in the context of Box-Ball Systems (BBS-paths for short). We also introduce one parameter generalizations of the energy statistics on the set of BBS-paths which all, conjecturally, have the same distribution.

---

35. Skew Littlewood―Richardson rules from Hopf algebras

Thomas Lam ; Aaron Lauve ; Frank Sottile.

We use Hopf algebras to prove a version of the Littlewood―Richardson rule for skew Schur functions, which implies a conjecture of Assaf and McNamara. We also establish skew Littlewood―Richardson rules for Schur $P-$ and $Q-$functions and noncommutative ribbon Schur functions, as well as skew Pieri rules for k-Schur functions, dual k-Schur functions, and for the homology of the affine Grassmannian of the symplectic group.

---

36. Criteria for rational smoothness of some symmetric orbit closures

Axel Hultman.

Let $G$ be a connected reductive linear algebraic group over $ℂ$ with an involution $θ$ . Denote by $K$ the subgroup of fixed points. In certain cases, the $K-orbits$ in the flag variety $G/B$ are indexed by the twisted identities $ι (θ ) = {θ (w^{-1})w | w∈W}$ in the Weyl group $W$. Under this assumption, we establish a criterion for rational smoothness of orbit closures which generalises classical results of Carrell and Peterson for Schubert varieties. That is, whether an orbit closure is rationally smooth at a given point can be determined by examining the degrees in a "Bruhat graph'' whose vertices form a subset of $ι (θ )$. Moreover, an orbit closure is rationally smooth everywhere if and only if its corresponding interval in the Bruhat order on $ι (θ )$ is rank symmetric. In the special case $K=\mathrm{Sp}_{2n}(ℂ), G=\mathrm{SL}_{2n}(ℂ)$, we strengthen our criterion by showing that only the degree of a single vertex, the "bottom one'', needs to be examined. This generalises a result of Deodhar for type A Schubert varieties.

---

37. The biHecke monoid of a finite Coxeter group

Florent Hivert ; Anne Schilling ; Nicolas M. Thiéry.

For any finite Coxeter group $W$, we introduce two new objects: its cutting poset and its biHecke monoid. The cutting poset, constructed using a generalization of the notion of blocks in permutation matrices, almost forms a lattice on $W$. The construction of the biHecke monoid relies on the usual combinatorial model for the $0-Hecke$ algebra $H_0(W)$, that is, for the symmetric group, the algebra (or monoid) generated by the elementary bubble sort operators. The authors previously introduced the Hecke group algebra, constructed as the algebra generated simultaneously by the bubble sort and antisort operators, and described its representation theory. In this paper, we consider instead the monoid generated by these operators. We prove that it admits |W| simple and projective modules. In order to construct the simple modules, we introduce for each $w∈W$ a combinatorial module $T_w$ whose support is the interval $[1,w]_R$ in right weak order. This module yields an algebra, whose representation theory generalizes that of the Hecke group algebra, with the combinatorics of descents replaced by that of blocks and of the cutting poset.

---

38. Weighted branching formulas for the hook lengths

Ionuţ Ciocan-Fontanine ; Matjaž Konvalinka ; Igor Pak.

The famous hook-length formula is a simple consequence of the branching rule for the hook lengths. While the Greene-Nijenhuis-Wilf probabilistic proof is the most famous proof of the rule, it is not completely combinatorial, and a simple bijection was an open problem for a long time. In this extended abstract, we show an elegant bijective argument that proves a stronger, weighted analogue of the branching rule. Variants of the bijection prove seven other interesting formulas. Another important approach to the formulas is via weighted hook walks; we discuss some results in this area. We present another motivation for our work: $J$-functions of the Hilbert scheme of points.

---

39. Valuative invariants for polymatroids

Harm Derksen ; Alex Fink.

Many important invariants for matroids and polymatroids, such as the Tutte polynomial, the Billera-Jia-Reiner quasi-symmetric function, and the invariant $\mathcal{G}$ introduced by the first author, are valuative. In this paper we construct the $\mathbb{Z}$-modules of all $\mathbb{Z}$-valued valuative functions for labelled matroids and polymatroids on a fixed ground set, and their unlabelled counterparts, the $\mathbb{Z}$-modules of valuative invariants. We give explicit bases for these modules and for their dual modules generated by indicator functions of polytopes, and explicit formulas for their ranks. Our results confirm a conjecture of the first author that $\mathcal{G}$ is universal for valuative invariants.

---

40. A bijection between (bounded) dominant Shi regions and core partitions

Susanna Fishel ; Monica Vazirani.

It is well-known that Catalan numbers $C_n = \frac{1}{ n+1} \binom{2n}{n}$ count the number of dominant regions in the Shi arrangement of type $A$, and that they also count partitions which are both n-cores as well as $(n+1)$-cores. These concepts have natural extensions, which we call here the $m$-Catalan numbers and $m$-Shi arrangement. In this paper, we construct a bijection between dominant regions of the $m$-Shi arrangement and partitions which are both $n$-cores as well as $(mn+1)$-cores. We also modify our construction to produce a bijection between bounded dominant regions of the $m$-Shi arrangement and partitions which are both $n$-cores as well as $(mn-1)$-cores. The bijections are natural in the sense that they commute with the action of the affine symmetric group.

---

41. Linear Systems on Tropical Curves

Christian Haase ; Gregg Musiker ; Josephine Yu.

A tropical curve $\Gamma$ is a metric graph with possibly unbounded edges, and tropical rational functions are continuous piecewise linear functions with integer slopes. We define the complete linear system $|D|$ of a divisor $D$ on a tropical curve $\Gamma$ analogously to the classical counterpart. We investigate the structure of $|D|$ as a cell complex and show that linear systems are quotients of tropical modules, finitely generated by vertices of the cell complex. Using a finite set of generators, $|D|$ defines a map from $\Gamma$ to a tropical projective space, and the image can be modified to a tropical curve of degree equal to $\mathrm{deg}(D)$. The tropical convex hull of the image realizes the linear system $|D|$ as a polyhedral complex.

---

42. On joint distribution of adjacencies, descents and some Mahonian statistics

Alexander Burstein.

We prove several conjectures of Eriksen regarding the joint distribution on permutations of the number of adjacencies (descents with consecutive values in consecutive positions), descents and some Mahonian statistics. We also prove Eriksen's conjecture that a certain bistatistic on Viennot's alternative tableaux is Euler-Mahonian.

---

43. Mixed Statistics on $01$-Fillings of Moon Polyominoes

William Y. C. Chen ; Andrew Y. Z. Wang ; Catherine H. Yan ; Alina F. Y. Zhao.

We establish a stronger symmetry between the numbers of northeast and southeast chains in the context of $01$-fillings of moon polyominoes. Let $\mathcal{M}$ be a moon polyomino. Consider all the $01$-fillings of $\mathcal{M}$ in which every row has at most one $1$. We introduce four mixed statistics with respect to a bipartition of rows or columns of $\mathcal{M}$. More precisely, let $S$ be a subset of rows of $\mathcal{M}$. For any filling $M$, the top-mixed (resp. bottom-mixed) statistic $\alpha (S; M)$ (resp. $\beta (S; M)$) is the sum of the number of northeast chains whose top (resp. bottom) cell is in $S$, together with the number of southeast chains whose top (resp. bottom) cell is in the complement of $S$. Similarly, we define the left-mixed and right-mixed statistics $\gamma (T; M)$ and $\delta (T; M)$, where $T$ is a subset of the columns. Let $\lambda (A; M)$ be any of these four statistics $\alpha (S; M)$, $\beta (S; M)$, $\gamma (T; M)$ and $\delta (T; M)$. We show that the joint distribution of the pair $(\lambda (A; M), \lambda (M/A; M))$ is symmetric and independent of the subsets $S, T$. In particular, the pair of statistics $(\lambda (A;M), \lambda (M/A; M))$ is equidistributed with $(\mathrm{se}(M), \mathrm{ne}(M))$, where $\mathrm{se}(M)$ and $\mathrm{ne}(M)$ are the numbers of southeast chains and northeast chains of $M$, respectively.

---

44. Products of Geck-Rouquier conjugacy classes and the Hecke algebra of composed permutations

Pierre-Loïc Méliot.

We show the $q$-analog of a well-known result of Farahat and Higman: in the center of the Iwahori-Hecke algebra $\mathscr{H}_{n,q}$, if $(a_{\lambda \mu}^ν (n,q))_ν$ is the set of structure constants involved in the product of two Geck-Rouquier conjugacy classes $\Gamma_{\lambda, n}$ and $\Gamma_{\mu,n}$, then each coefficient $a_{\lambda \mu}^ν (n,q)$ depend on $n$ and $q$ in a polynomial way. Our proof relies on the construction of a projective limit of the Hecke algebras; this projective limit is inspired by the Ivanov-Kerov algebra of partial permutations.

---

45. An algorithm which generates linear extensions for a generalized Young diagram with uniform probability

Kento Nakada ; Shuji Okamura.

The purpose of this paper is to present an algorithm which generates linear extensions for a generalized Young diagram, in the sense of D. Peterson and R. A. Proctor, with uniform probability. This gives a proof of a D. Peterson's hook formula for the number of reduced decompositions of a given minuscule elements. \par

---

46. On $\gamma$-vectors satisfying the Kruskal-Katona inequalities

E. Nevo ; T. K. Petersen.

We present examples of flag homology spheres whose $\gamma$-vectors satisfy the Kruskal-Katona inequalities. This includes several families of well-studied simplicial complexes, including Coxeter complexes and the simplicial complexes dual to the associahedron and to the cyclohedron. In these cases, we construct explicit flag simplicial complexes whose $f$-vectors are the $\gamma$-vectors in question, and so a result of Frohmader shows that the $\gamma$-vectors satisfy not only the Kruskal-Katona inequalities but also the stronger Frankl-Füredi-Kalai inequalities. In another direction, we show that if a flag $(d-1)$-sphere has at most $2d+3$ vertices its $\gamma$-vector satisfies the Frankl-Füredi-Kalai inequalities. We conjecture that if $\Delta$ is a flag homology sphere then $\gamma (\Delta)$ satisfies the Kruskal-Katona, and further, the Frankl-Füredi-Kalai inequalities. This conjecture is a significant refinement of Gal's conjecture, which asserts that such $\gamma$-vectors are nonnegative.

---

47. Equivalence Relations of Permutations Generated by Constrained Transpositions

Stephen Linton ; James Propp ; Tom Roby ; Julian West.

We consider a large family of equivalence relations on permutations in $S_n$ that generalise those discovered by Knuth in his study of the Robinson-Schensted correspondence. In our most general setting, two permutations are equivalent if one can be obtained from the other by a sequence of pattern-replacing moves of prescribed form; however, we limit our focus to patterns where two elements are transposed, conditional upon the presence of a third element of suitable value and location. For some relations of this type, we compute the number of equivalence classes, determine how many $n$-permutations are equivalent to the identity permutation, or characterise this equivalence class. Although our results include familiar integer sequences (e.g., Catalan, Fibonacci, and Tribonacci numbers) and special classes of permutations (layered, connected, and $123$-avoiding), some of the sequences that arise appear to be new.

---

48. Nonzero coefficients in restrictions and tensor products of supercharacters of $U_n(q)$ (extended abstract)

Stephen Lewis ; Nathaniel Thiem.

The standard supercharacter theory of the finite unipotent upper-triangular matrices $U_n(q)$ gives rise to a beautiful combinatorics based on set partitions. As with the representation theory of the symmetric group, embeddings of $U_m(q) \subseteq U_n(q)$ for $m \leq n$ lead to branching rules. Diaconis and Isaacs established that the restriction of a supercharacter of $U_n(q)$ is a nonnegative integer linear combination of supercharacters of $U_m(q)$ (in fact, it is polynomial in $q$). In a first step towards understanding the combinatorics of coefficients in the branching rules of the supercharacters of $U_n(q)$, this paper characterizes when a given coefficient is nonzero in the restriction of a supercharacter and the tensor product of two supercharacters. These conditions are given uniformly in terms of complete matchings in bipartite graphs.

---

49. Crystals from categorified quantum groups

Aaron D. Lauda ; Monica Vazirani.

We study the crystal structure on categories of graded modules over algebras which categorify the negative half of the quantum Kac-Moody algebra associated to a symmetrizable Cartan data. We identify this crystal with Kashiwara's crystal for the corresponding negative half of the quantum Kac-Moody algebra. As a consequence, we show the simple graded modules for certain cyclotomic quotients carry the structure of highest weight crystals, and hence compute the rank of the corresponding Grothendieck group.

---

50. On the diagonal ideal of $(\mathbb{C}^2)^n$ and $q,t$-Catalan numbers

Kyungyong Lee ; Li Li.

Let $I_n$ be the (big) diagonal ideal of $(\mathbb{C}^2)^n$. Haiman proved that the $q,t$-Catalan number is the Hilbert series of the graded vector space $M_n=\bigoplus_{d_1,d_2}(M_n)_{d_1,d_2}$ spanned by a minimal set of generators for $I_n$. We give simple upper bounds on $\textrm{dim} (M_n)_{d_1, d_2}$ in terms of partition numbers, and find all bi-degrees $(d_1,d_2)$ such that $\textrm{dim} (M_n)_{d_1, d_2}$ achieve the upper bounds. For such bi-degrees, we also find explicit bases for $(M_n)_{d_1, d_2}$.

---

51. Toric Ideals of Flow Polytopes

Matthias Lenz.

We show that toric ideals of flow polytopes are generated in degree $3$. This was conjectured by Diaconis and Eriksson for the special case of the Birkhoff polytope. Our proof uses a hyperplane subdivision method developed by Haase and Paffenholz. It is known that reduced revlex Gröbner bases of the toric ideal of the Birkhoff polytope $B_n$ have at most degree $n$. We show that this bound is sharp for some revlex term orders. For $(m \times n)$-transportation polytopes, a similar result holds: they have Gröbner bases of at most degree $\lfloor mn/2 \rfloor$. We construct a family of examples, where this bound is sharp.

---

52. On formulas for moments of the Wishart distributions as weighted generating functions of matchings

Yasuhide Numata ; Satoshi Kuriki.

We consider the real and complex noncentral Wishart distributions. The moments of these distributions are shown to be expressed as weighted generating functions of graphs associated with the Wishart distributions. We give some bijections between sets of graphs related to moments of the real Wishart distribution and the complex noncentral Wishart distribution. By means of the bijections, we see that calculating these moments of a certain class the real Wishart distribution boils down to calculations for the case of complex Wishart distributions.

---

53. Bruhat order, rationally smooth Schubert varieties, and hyperplane arrangements

Suho Oh ; Hwanchul Yoo.

We link Schubert varieties in the generalized flag manifolds with hyperplane arrangements. For an element of a Weyl group, we construct a certain graphical hyperplane arrangement. We show that the generating function for regions of this arrangement coincides with the Poincaré polynomial of the corresponding Schubert variety if and only if the Schubert variety is rationally smooth.

---

54. Counting RNA pseudoknotted structures (extended abstract)

Cédric Saule ; Mireille Regnier ; Jean-Marc Steyaert ; Alain Denise.

In 2004, Condon and coauthors gave a hierarchical classification of exact RNA structure prediction algorithms according to the generality of structure classes that they handle. We complete this classification by adding two recent prediction algorithms. More importantly, we precisely quantify the hierarchy by giving closed or asymptotic formulas for the theoretical number of structures of given size n in all the classes but one. This allows to assess the tradeoff between the expressiveness and the computational complexity of RNA structure prediction algorithms. \par

---

55. Boolean complexes and boolean numbers

Bridget Eileen Tenner.

The Bruhat order gives a poset structure to any Coxeter group. The ideal of elements in this poset having boolean principal order ideals forms a simplicial poset. This simplicial poset defines the boolean complex for the group. In a Coxeter system of rank n, we show that the boolean complex is homotopy equivalent to a wedge of (n-1)-dimensional spheres. The number of these spheres is the boolean number, which can be computed inductively from the unlabeled Coxeter system, thus defining a graph invariant. For certain families of graphs, the boolean numbers have intriguing combinatorial properties. This work involves joint efforts with Claesson, Kitaev, and Ragnarsson. \par

---

56. A unification of permutation patterns related to Schubert varieties

Henning A. Úlfarsson.

We prove new connections between permutation patterns and singularities of Schubert varieties, by giving a new characterization of factorial and Gorenstein varieties in terms of so called bivincular patterns. These are generalizations of classical patterns where conditions are placed on the location of an occurrence in a permutation, as well as on the values in the occurrence. This clarifies what happens when the requirement of smoothness is weakened to factoriality and further to Gorensteinness, extending work of Bousquet-Mélou and Butler (2007), and Woo and Yong (2006). We also prove results that translate some known patterns in the literature into bivincular patterns.

---

57. Schubert complexes and degeneracy loci

Steven V Sam.

The classical Thom―Porteous formula expresses the homology class of the degeneracy locus of a generic map between two vector bundles as an alternating sum of Schur polynomials. A proof of this formula was given by Pragacz by expressing this alternating sum as the Euler characteristic of a Schur complex, which gives an explanation for the signs. Fulton later generalized this formula to the situation of flags of vector bundles by using alternating sums of Schubert polynomials. Building on the Schubert functors of Kraśkiewicz and Pragacz, we introduce Schubert complexes and show that Fulton's alternating sum can be realized as the Euler characteristic of this complex, thereby providing a conceptual proof for why an alternating sum appears. \par

---

58. The Hodge Structure of the Coloring Complex of a Hypergraph (Extended Abstract)

Sarah C Rundell ; Jane H Long.

Let $G$ be a simple graph with $n$ vertices. The coloring complex$ Δ (G)$ was defined by Steingrímsson, and the homology of $Δ (G)$ was shown to be nonzero only in dimension $n-3$ by Jonsson. Hanlon recently showed that the Eulerian idempotents provide a decomposition of the homology group $H_{n-3}(Δ (G))$ where the dimension of the $j^th$ component in the decomposition, $H_{n-3}^{(j)}(Δ (G))$, equals the absolute value of the coefficient of $λ ^j$ in the chromatic polynomial of $G, _{\mathcal{χg}}(λ )$. Let $H$ be a hypergraph with $n$ vertices. In this paper, we define the coloring complex of a hypergraph, $Δ (H)$, and show that the coefficient of $λ ^j$ in $χ _H(λ )$ gives the Euler Characteristic of the $j^{th}$ Hodge subcomplex of the Hodge decomposition of $Δ (H)$. We also examine conditions on a hypergraph, $H$, for which its Hodge subcomplexes are Cohen-Macaulay, and thus where the absolute value of the coefficient of $λ ^j$ in $χ _H(λ )$ equals the dimension of the $j^{th}$ Hodge piece of the Hodge decomposition of $Δ (H)$.

---

59. Bijective enumeration of permutations starting with a longest increasing subsequence

Greta Panova.

We prove a formula for the number of permutations in $S_n$ such that their first $n-k$ entries are increasing and their longest increasing subsequence has length $n-k$. This formula first appeared as a consequence of character polynomial calculations in recent work of Adriano Garsia and Alain Goupil. We give two "elementary' bijective proofs of this result and of its q-analogue, one proof using the RSK correspondence and one only permutations.

---

60. Cyclic sieving for longest reduced words in the hyperoctahedral group

T. K. Petersen ; L. Serrano.

We show that the set $R(w_0)$ of reduced expressions for the longest element in the hyperoctahedral group exhibits the cyclic sieving phenomenon. More specifically, $R(w_0)$ possesses a natural cyclic action given by moving the first letter of a word to the end, and we show that the orbit structure of this action is encoded by the generating function for the major index on $R(w_0)$.

---

61. The cluster and dual canonical bases of Z [x_11, ..., x_33] are equal

Brendon Rhoades.

The polynomial ring $\mathbb{Z}[x_{11}, . . . , x_{33}]$ has a basis called the dual canonical basis whose quantization facilitates the study of representations of the quantum group $U_q(\mathfrak{sl}3(\mathbb{C}))$. On the other hand, $\mathbb{Z}[x_{11}, . . . , x_{33}]$ inherits a basis from the cluster monomial basis of a geometric model of the type $D_4$ cluster algebra. We prove that these two bases are equal. This extends work of Skandera and proves a conjecture of Fomin and Zelevinsky. This also provides an explicit factorization of the dual canonical basis elements of $\mathbb{Z}[x_{11}, . . . , x_{33}]$ into irreducible polynomials.

---

62. Combinatorial formulas for double parabolic R-polynomials

Justin Lambright ; Mark Skandera.

The well-known R-polynomials in ℤ[q], which appear in Hecke algebra computations, are closely related to certain modified R-polynomials in ℕ[q] whose coefficients have simple combinatorial interpretations. We generalize this second family of polynomials, providing combinatorial interpretations for expressions arising in a much broader class of computations. In particular, we extend results of Brenti, Deodhar, and Dyer to new settings which include parabolic Hecke algebra modules and the quantum polynomial ring.

---

63. On extensions of the Newton-Raphson iterative scheme to arbitrary orders

Gilbert Labelle.

The classical quadratically convergent Newton-Raphson iterative scheme for successive approximations of a root of an equation $f(t)=0$ has been extended in various ways by different authors, going from cubical convergence to convergence of arbitrary orders. We introduce two such extensions, using appropriate differential operators as well as combinatorial arguments. We conclude with some applications including special series expansions for functions of the root and enumeration of classes of tree-like structures according to their number of leaves.

---

64. A note on moments of derivatives of characteristic polynomials

Paul-Olivier Dehaye.

We present a simple technique to compute moments of derivatives of unitary characteristic polynomials. The first part of the technique relies on an idea of Bump and Gamburd: it uses orthonormality of Schur functions over unitary groups to compute matrix averages of characteristic polynomials. In order to consider derivatives of those polynomials, we here need the added strength of the Generalized Binomial Theorem of Okounkov and Olshanski. This result is very natural as it provides coefficients for the Taylor expansions of Schur functions, in terms of shifted Schur functions. The answer is finally given as a sum over partitions of functions of the contents. One can also obtain alternative expressions involving hypergeometric functions of matrix arguments.

---

65. $f$-vectors of subdivided simplicial complexes (extended abstract)

Emanuele Delucchi ; Aaron Pixton ; Lucas Sabalka.

We take a geometric point of view on the recent result by Brenti and Welker, who showed that the roots of the $f$-polynomials of successive barycentric subdivisions of a finite simplicial complex $X$ converge to fixed values depending only on the dimension of $X$. We show that these numbers are roots of a certain polynomial whose coefficients can be computed explicitly. We observe and prove an interesting symmetry of these roots about the real number $-2$. This symmetry can be seen via a nice realization of barycentric subdivision as a simple map on formal power series. We then examine how such a symmetry extends to more general types of subdivisions. The generalization is formulated in terms of an operator on the (formal) ring on the set of simplices of the complex.

---

66. A Combinatorial Formula for Orthogonal Idempotents in the $0$-Hecke Algebra of $S_N$

Tom Denton.

Building on the work of P.N. Norton, we give combinatorial formulae for two maximal decompositions of the identity into orthogonal idempotents in the $0$-Hecke algebra of the symmetric group, $\mathbb{C}H_0(S_N)$. This construction is compatible with the branching from $H_0(S_{N-1})$ to $H_0(S_N)$.

---

67. Tropical secant graphs of monomial curves

María Angélica Cueto ; Shaowei Lin.

We construct and study an embedded weighted balanced graph in $\mathbb{R}^{n+1}$ parametrized by a strictly increasing sequence of $n$ coprime numbers $\{ i_1, \ldots, i_n\}$, called the $\textit{tropical secant surface graph}$. We identify it with the tropicalization of a surface in $\mathbb{C}^{n+1}$ parametrized by binomials. Using this graph, we construct the tropicalization of the first secant variety of a monomial projective curve with exponent vector $(0, i_1, \ldots, i_n)$, which can be described by a balanced graph called the $\textit{tropical secant graph}$. The combinatorics involved in computing the degree of this classical secant variety is non-trivial. One earlier approach to this is due to K. Ranestad. Using techniques from tropical geometry, we give algorithms to effectively compute this degree (as well as its multidegree) and the Newton polytope of the first secant variety of any given monomial curve in $\mathbb{P}^4$.

---

68. Extended Abstract for Enumerating Pattern Avoidance for Affine Permutations

Andrew Crites.

In this paper we study pattern avoidance for affine permutations. In particular, we show that for a given pattern $p$, there are only finitely many affine permutations in $\widetilde{S}_n$ that avoid $p$ if and only if $p$ avoids the pattern $321$. We then count the number of affine permutations that avoid a given pattern $p$ for each $p$ in $S_3$, as well as give some conjectures for the patterns in $S_4$. This paper is just an outline; the full version will appear elsewhere.

---

69. Pattern avoidance in partial permutations (extended abstract)

Anders Claesson ; Vít Jelínek ; Eva Jelínková ; Sergey Kitaev.

Motivated by the concept of partial words, we introduce an analogous concept of partial permutations. A $\textit{partial permutation of length n with k holes}$ is a sequence of symbols $\pi = \pi_1 \pi_2 \cdots \pi_n$ in which each of the symbols from the set $\{1,2,\ldots,n-k\}$ appears exactly once, while the remaining $k$ symbols of $\pi$ are "holes''. We introduce pattern-avoidance in partial permutations and prove that most of the previous results on Wilf equivalence of permutation patterns can be extended to partial permutations with an arbitrary number of holes. We also show that Baxter permutations of a given length $k$ correspond to a Wilf-type equivalence class with respect to partial permutations with $(k-2)$ holes. Lastly, we enumerate the partial permutations of length $n$ with $k$ holes avoiding a given pattern of length at most four, for each $n \geq k \geq 1$.

---

70. $n!$ matchings, $n!$ posets (extended abstract)

Anders Claesson ; Svante Linusson.

We show that there are $n!$ matchings on $2n$ points without, so called, left (neighbor) nestings. We also define a set of naturally labelled $(2+2)$-free posets, and show that there are $n!$ such posets on $n$ elements. Our work was inspired by Bousquet-Mélou, Claesson, Dukes and Kitaev [J. Combin. Theory Ser. A. 117 (2010) 884―909]. They gave bijections between four classes of combinatorial objects: matchings with no neighbor nestings (due to Stoimenow), unlabelled $(2+2)$-free posets, permutations avoiding a specific pattern, and so called ascent sequences. We believe that certain statistics on our matchings and posets could generalize the work of Bousquet-Mélou et al. and we make a conjecture to that effect. We also identify natural subsets of matchings and posets that are equinumerous to the class of unlabeled $(2+2)$-free posets. We give bijections that show the equivalence of (neighbor) restrictions on nesting arcs with (neighbor) restrictions on crossing arcs. These bijections are thought to be of independent interest. One of the bijections maps via certain upper-triangular integer matrices that have recently been studied by Dukes and Parviainen [Electron. J. Combin. 17 (2010) #R53].

---

71. The Frobenius Complex

Eric Clark ; Richard Ehrenborg.

Motivated by the classical Frobenius problem, we introduce the Frobenius poset on the integers $\mathbb{Z}$, that is, for a sub-semigroup $\Lambda$ of the non-negative integers $(\mathbb{N},+)$, we define the order by $n \leq_{\Lambda} m$ if $m-n \in \Lambda$. When $\Lambda$ is generated by two relatively prime integers $a$ and $b$, we show that the order complex of an interval in the Frobenius poset is either contractible or homotopy equivalent to a sphere. We also show that when $\Lambda$ is generated by the integers $\{a,a+d,a+2d,\ldots,a+(a-1)d\}$, the order complex is homotopy equivalent to a wedge of spheres.

---

72. Linear coefficients of Kerov's polynomials: bijective proof and refinement of Zagier's result

Valentin Féray ; Ekaterina A. Vassilieva.

We look at the number of permutations $\beta$ of $[N]$ with $m$ cycles such that $(1 2 \ldots N) \beta^{-1}$ is a long cycle. These numbers appear as coefficients of linear monomials in Kerov's and Stanley's character polynomials. D. Zagier, using algebraic methods, found an unexpected connection with Stirling numbers of size $N+1$. We present the first combinatorial proof of his result, introducing a new bijection between partitioned maps and thorn trees. Moreover, we obtain a finer result, which takes the type of the permutations into account.

---

73. Balanced binary trees in the Tamari lattice

Samuele Giraudo.

We show that the set of balanced binary trees is closed by interval in the Tamari lattice. We establish that the intervals $[T_0, T_1]$ where $T_0$ and $T_1$ are balanced trees are isomorphic as posets to a hypercube. We introduce tree patterns and synchronous grammars to get a functional equation of the generating series enumerating balanced tree intervals.

---

74. Chain enumeration of k-divisible noncrossing partitions of classical types

Jang Soo Kim.

We give combinatorial proofs of the formulas for the number of multichains in the $k-divisible$ noncrossing partitions of classical types with certain conditions on the rank and the block size due to Krattenthaler and Müller. We also prove Armstrong's conjecture on the zeta polynomial of the poset of k-divisible noncrossing partitions of type A invariant under the 180° rotation in the cyclic representation.

---

75. Enumerating (2+2)-free posets by the number of minimal elements and other statistics

Sergey Kitaev ; Jeffrey Remmel.

A poset is said to be (2+2)-free if it does not contain an induced subposet that is isomorphic to 2+2, the union of two disjoint 2-element chains. In a recent paper, Bousquet-Mélou et al. found, using so called ascent sequences, the generating function for the number of (2+2)-free posets: $P(t)=∑_n≥ 0 ∏_i=1^n ( 1-(1-t)^i)$. We extend this result by finding the generating function for (2+2)-free posets when four statistics are taken into account, one of which is the number of minimal elements in a poset. We also show that in a special case when only minimal elements are of interest, our rather involved generating function can be rewritten in the form $P(t,z)=∑_n,k ≥0 p_n,k t^n z^k = 1+ ∑_n ≥0\frac{zt}{(1-zt)^n+1}∏_i=1^n (1-(1-t)^i)$ where $p_n,k$ equals the number of (2+2)-free posets of size $n$ with $k$ minimal elements.

---

76. A Closed Character Formula for Symmetric Powers of Irreducible Representations

Stavros Kousidis.

We prove a closed character formula for the symmetric powers $S^N V(λ )$ of a fixed irreducible representation $V(λ )$ of a complex semi-simple Lie algebra $\mathfrak{g}$ by means of partial fraction decomposition. The formula involves rational functions in rank of $\mathfrak{g}$ many variables which are easier to determine than the weight multiplicities of $S^N V(λ )$ themselves. We compute those rational functions in some interesting cases. Furthermore, we introduce a residue-type generating function for the weight multiplicities of $S^N V(λ )$ and explain the connections between our character formula, vector partition functions and iterated partial fraction decomposition.

---

77. Denominator formulas for Lie superalgebras (extended abstract)

Victor Kac ; Pierluigi Möseneder Frajria ; Paolo Papi.

We provide formulas for the Weyl-Kac denominator and superdenominator of a basic classical Lie superalgebra for a distinguished set of positive roots. \par

---

78. Affine structures and a tableau model for $E_6$ crystals

Brant Jones ; Anne Schilling.

We provide the unique affine crystal structure for type $E_6^{(1)}$ Kirillov―Reshetikhin crystals corresponding to the multiples of fundamental weights $s\Lambda _1, s\Lambda _2$, and $s\Lambda _6$ for all $s≥ 1$ (in Bourbaki's labeling of the Dynkin nodes, where 2 is the adjoint node). Our methods introduce a generalized tableaux model for classical highest weight crystals of type $E$ and use the order three automorphism of the affine $E_6^{(1)}$ Dynkin diagram. In addition, we provide a conjecture for the affine crystal structure of type $E_7^{(1)}$ Kirillov―Reshetikhin crystals corresponding to the adjoint node.

---

79. Enumeration of inscribed polyominos

Alain Goupil ; Hugo Cloutier ; Fathallah Nouboud.

We introduce a new family of polyominos that are inscribed in a rectangle of given size for which we establish a number of exact formulas and generating functions. In particular, we study polyominos inscribed in a rectangle with minimum area and minimum area plus one. These results are then used for the enumeration of lattice trees inscribed in a rectangle with minimum area plus one.

---

80. Word equations in a uniquely divisible group

Christopher J. Hillar ; Lionel Levine ; Darren Rhea.

We study equations in groups $G$ with unique $m$-th roots for each positive integer $m$. A word equation in two letters is an expression of the form$ w(X,A) = B$, where $w$ is a finite word in the alphabet ${X,A}$. We think of $A,B ∈G$ as fixed coefficients, and $X ∈G$ as the unknown. Certain word equations, such as $XAXAX=B$, have solutions in terms of radicals: $X = A^-1/2(A^1/2BA^1/2)^1/3A^-1/2$, while others such as $X^2 A X = B$ do not. We obtain the first known infinite families of word equations not solvable by radicals, and conjecture a complete classification. To a word w we associate a polynomial $P_w ∈ℤ[x,y]$ in two commuting variables, which factors whenever $w$ is a composition of smaller words. We prove that if $P_w(x^2,y^2)$ has an absolutely irreducible factor in $ℤ[x,y]$, then the equation $w(X,A)=B$ is not solvable in terms of radicals.

---

81. Constant term evaluation for summation of C-finite sequences

Qing-Hu Hou ; Guoce Xin.

Based on constant term evaluation, we present a new method to compute a closed form of the summation $∑_k=0^n-1 ∏_j=1^r F_j(a_jn+b_jk+c_j)$, where ${F_j(k)} are $C$-finite sequences and $a_j$ and $a_j+b_j$ are nonnegative integers. Our algorithm is much faster than that of Greene and Wilf.

---

82. The Möbius function of separable permutations (extended abstract)

Vít Jelínek ; Eva Jelínková ; Einar Steingrímsson.

A permutation is separable if it can be generated from the permutation 1 by successive sums and skew sums or, equivalently, if it avoids the patterns 2413 and 3142. Using the notion of separating tree, we give a computationally efficient formula for the Möbius function of an interval $(q,p)$ in the poset of separable permutations ordered by pattern containment. A consequence of the formula is that the Möbius function of such an interval $(q,p)$ is bounded by the number of occurrences of $q$ as a pattern in $p$. The formula also implies that for any separable permutation $p$ the Möbius function of $(1,p)$ is either 0, 1 or -1.

---