Partitions, rooks, and symmetric functions in noncommuting variables

Mahir Bilen Can, Bruce E. Sagan

Published 2010-08-17Version 1

Let $\Pi_n$ denote the set of all set partitions of $\{1,2,\ldots,n\}$. We consider two subsets of $\Pi_n$, one connected to rook theory and one associated with symmetric functions in noncommuting variables. Let $\cE_n\sbe\Pi_n$ be the subset of all partitions corresponding to an extendable rook (placement) on the upper-triangular board, $\cT_{n-1}$. Given $\pi\in\Pi_m$ and $\si\in\Pi_n$, define their {\it slash product\/} to be $\pi|\si=\pi\cup(\si+m)\in\Pi_{m+n}$ where $\si+m$ is the partition obtained by adding $m$ to every element of every block of $\si$. Call $\tau$ {\it atomic\/} if it can not be written as a nontrivial slash product and let $\cA_n\sbe\Pi_n$ denote the subset of atomic partitions. Atomic partitions were first defined by Bergeron, Hohlweg, Rosas, and Zabrocki during their study of $NCSym$, the symmetric functions in noncommuting variables. We show that, despite their very different definitions, $\cE_n=\cA_n$ for all $n\ge0$. Furthermore, we put an algebra structure on the formal vector space generated by all rook placements on upper triangular boards which makes it isomorphic to $NCSym$. We end with some remarks and an open problem.