Partitions, rooks, and symmetric functions in noncommuting variables

Abstract

Let ${\Pi }_n$ denote the set of all set partitions of $\{1,2,\dots ,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Π_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Π_n$, define their {\it slash product\/} to be $π|\si=π\cup(\si+m)\inΠ_{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Π_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\ge 0$. 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.

8 pages, 1 figure

Cited by in corpus (1)

• A Bijection between Atomic Partitions and Unsplitable Partitions