17
$\begingroup$

I've come across a function from the set of integer partitions to the natural numbers which I don't recognise but which probably ought to be familiar; it arises in the homogeneous Garnir relations for graded Specht modules (see Kleshchev, Mathas & Ram: "Universal graded Specht modules", Proc. LMS 105). I hope someone will recognise it and point me to a useful reference.

The function (let's call it $f$) is defined recursively; to begin with, $f(\varnothing)=1$. Now suppose we have a non-empty partition $\lambda$, and take a box $(i,j)$ in the Young diagram for which $i+j$ is maximised. Let $\mu$ be the partition you get by removing the first $i$ rows from the Young diagram and let $\nu$ be the partition you get by removing the first $j$ columns from the Young diagram. Now recursively define

$f(\lambda) = \binom{i+j}if(\mu)f(\nu)$.

For example, take $\lambda=(5,3,3,1)$. Let $(i,j)=(3,3)$, so that $\mu=(1)$ and $\nu=(2)$. One can calculate $f(\mu)=2$ and $f(\nu)=3$, so that $f(\lambda)=120$.

It's not hard to show that $f$ is well-defined (i.e. doesn't depend on the choice of $(i,j)$). I have two other definitions of $f$ (also recursive) which I'll omit for now (it's non-trivial to show that they are equivalent).

Please let me know if you've seen this function (or a similar-looking one) before. Since it's a function from partitions to positive integers, it ought to count tableaux of some kind.

Improve this question
$\endgroup$
8
  • $\begingroup$ $\dbinom{i+j}{i}$ counts lattice path through the $i\times j$ rectangle (not only Dyck paths). So it seems like you're counting some kind of families of paths... $\endgroup$
    – darij grinberg
    Commented May 30, 2013 at 15:06
  • 1
    $\begingroup$ Warning, a little advertisement: have you tried to search the statistic finder FindStat.org to see if your data on partitions matches statistics in the database (maybe after applying some combinatorial maps)? $\endgroup$
    – Christian Stump
    Commented May 30, 2013 at 15:14
  • 1
    $\begingroup$ It's not hard to construct a poset $P(\lambda)$, so that your function counts the number of standard tableaux of $P(\lambda)$, (aka number of order preserving labellings of $P(\lambda)$). Unfortunately this isn't a particularly famous poset, so it just gives a definition that makes it clear that $f$ doesn't depend on the choices in your definition. As far as similar functions, this is almost like counting the number of parking functions of shape $\lambda$ but I doubt there is any deep connection other than the similar construction. $\endgroup$
    – Gjergji Zaimi
    Commented May 31, 2013 at 6:10
  • 1
    $\begingroup$ This is the kind of question whose answer I want to read on arXiv when the dust has settled... $\endgroup$
    – darij grinberg
    Commented May 31, 2013 at 8:44
  • 1
    $\begingroup$ @Darij: the dust has now settled: arxiv.org/abs/1309.6467 $\endgroup$
    – Matt Fayers
    Commented Sep 28, 2013 at 9:32

2 Answers 2

Reset to default
10
$\begingroup$

Find a large enough $N$ that $i+j \leq N$ for all boxes $(i,j)$ of the partition. So your partition is contained in the staircase partition $(N,N-1,N-2, \ldots, 2,1)$. Turn your partition into a planar rooted forest on $N+1$ vertices using the bijection I'll list below. Your statistic is the number of ways to order the vertices of the tree so that every vertex is labeled before its children.

I'll use your example $(5,3,3,1)$ to illustrate. It embeds in $(5, 4,3,2,1)$. Here I show the original partition with $\ast$'s and the extra elements of the staircase with $\cdot$'s. $$\begin{matrix} \ast &\ast & \ast & \ast & \ast \\ \ast & \ast & \ast & \cdot & & \\ \ast & \ast & \ast & & \\ \ast & \cdot & & & \\ \cdot & & & & \\ \end{matrix}$$

Read along the southwest edge of the partition to make a matching parentheses string: Up is $($ and right is $)$; pad with an extra $($ at the start and $)$ at the end. So we get $(()())\ (())\ ()$. The vertices of my forest will be matching pairs, with edges going up for containment. So $$\begin{matrix} & & a & b & c \\ & \nearrow &\uparrow & \uparrow & \\ d & & e & f & \\ \end{matrix}$$

We are counting was to order $(a,b,c,d,e,f)$ so that $a$ comes before $d$ and $e$ and $b$ comes before $f$. Sure enough, the count is $6!/(3 \cdot 2) = 120$.

Proof Sketch: If I choose $N$ so large that the Dyck path never touches the boundary of the staircase, then the tree has a single connected component. The root of that component must be ordered first. Deleting that root has the same effect as reducing $N$ by $1$. So we may assume that we choose $N$ so that the Dyck path does touch the boundary, say at $(i,j)$ with $i+j = N$.

Then the forest may be divided into two halves: Components coming from the left of $(i,j)$ and components coming from the right. The number of ways to allocate the labels between those halves is $\binom{i+j}{i}$, and we then must recursively choose how to order each of them. This replicates your recursion.

Improve this answer
$\endgroup$
9
  • $\begingroup$ "Read along the southwest edge of the partition"... starting where? I've got a feeling you have to start somewhere at the "$0$-th column", since the way you describe the bijection you should get $(()(()(())(()$ which isn't even well-formed. $\endgroup$
    – darij grinberg
    Commented Jun 2, 2013 at 8:48
  • $\begingroup$ Also, the forest you've drawn does have several connected components, despite the partition touching the boundary? $\endgroup$
    – darij grinberg
    Commented Jun 2, 2013 at 8:50
  • $\begingroup$ I'm not sure where you get that parentheses string. We are reading the edges of the boundary, including the edges which don't touch $\lambda$ itself but are necessary to get us to the bottom left and top right of the staircase. For example, if we are doing partitions inside the staircase $(3,2,1)$, then the empty partition is $(((())))$ and the full stair case is $()()()()$. And yes, we get a connected forest if and only if we DON'T return to the boundary. $\endgroup$
    – David E Speyer
    Commented Jun 2, 2013 at 12:26
  • $\begingroup$ Yup! This is the same poset that I had in mind for counting the number of order preserving labelings. I'm still not sure if it has any combinatorial significance, or if it has been studied in any other context. $\endgroup$
    – Gjergji Zaimi
    Commented Jun 2, 2013 at 13:12
  • 6
    $\begingroup$ The number $f(\lambda)$ of order preserving labelings (aka linear extensions) of this poset occurred naturally in the work on "Dyck tilings". The poset appears in the work of Kim et al (arxiv.org/abs/1205.6578); note that there is an easy "hook formula" for the number $f(\lambda)$ in particular, given by $n!/\prod_c(|c|)$ in terms of the "lengths" of the chords. The aforementioned work follows one of Kim (arxiv.org/abs/1108.5558), which answered conjectures of Kenyon and Wilson (arxiv.org/abs/1007.2006, Conjecture 1) $\endgroup$
    – Philippe Nadeau
    Commented Jun 3, 2013 at 9:58
3
$\begingroup$

Okay, I agree that this answer comes actually a little late...

If you type some values of your function into FindStat, you will see David Speyer's answer automatically generated, since it is obtained as a natural statistic obtained after applying a natural combinatorial map.

To have some values, for size up to $4$ it is given by $$ [1] => 2, [2] => 3, [1,1] => 3, [3] => 4, [2,1] => 6, [1,1,1] => 4, $$ $$ [4] => 5, [3,1] => 8, [2,2] => 6, [2,1,1] => 8, [1,1,1,1] => 5. $$

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .