4
$\begingroup$

Let $\lambda=(\lambda_1,\cdots,\lambda_n)$ be a partition, with $|\lambda|:=N$. Attach an extra box to $\lambda$ to the right end of the $r$'th row. In coordinate form, the last box on row $r$ has label $(r,\lambda_r)$, so the added box has coordinates $(r,\lambda_r+1)$. Now look at "almost-standard young tableaux at row $r$" of this shape, to be defined as follows: our partition is now $|\lambda|+1$, where all the boxes in the original diagram of $\lambda$ are increasing right and down BUT, enforce that the value in the added box is bigger than $(r,\lambda_r)$, but not necessarily bigger than any box above it. This is all best shown by an example:

Take $\lambda=(4,3,2,1)$, giving $|\lambda|=10$, and fix $r=2$. We now have $|\lambda|+1=11$ and so the following are examples of almost standard tableaux:

$$\begin{array}{cccccc} 1 & 2 & 4 & 6 & \ \\ 3 & 5 & 7 &\leftrightarrow & 8 \\ 9 & 11 & \ & \ & \ \\ 10 & \ &\ & \ & \ \end{array}$$

$$$$

$$\begin{array}{cccccc} 1 & 3 & 6 & 11 & \ \\ 2 & 4 & 9 &\leftrightarrow & 10 \\ 5 & 7 & \ & \ & \ \\ 8 & \ &\ & \ & \ \end{array}$$

where the double arrows show that the added box attaches to the end of the second row. Notice that in the second example, $9<10$ as required but $11>10$ is OK since the added box is "coupled" only to the second row. There are a total of 1850 such tableaux. Compare this to the number of SYT of shape $(4,4,3,2,1)$ which is 1320 and is naturally less than the number of the almost standard tableaux.

I'm interested in counting the number of such tableaux. When $r=1$, we're back to Standard Young Tableaux so everything is easy via the hook formula. Numerically, for $r>1$ things get trickier. Experimentally, there's no obvious hook formula for these tableaux. I'd be very satisfied if this is tractable for staircase shapes $(n,n-1,\cdots,1)$.

These tableaux also satisfy the same kind of recurrences as SYT: you can take away corner boxes (where the maximum value is) and sum over all possible tableaux to get the total. So it looks like a good idea might be to define schur functions in terms of these tableaux. Unfortunately, to calculate such Schur functions, I believe one needs at least some kind of involution on these tableaux.

One idea I have is that when $\lambda_{r-1}>\lambda_r$, you can split into cases where the added box $(r,\lambda_r)$ has value greater/less than the box above it $(r-1,\lambda_r+1)$. In the case of greater, we're back to SYT. It then amounts to calculating the less case, which again seems difficult. Perhaps one can move the $(r-1,\lambda_r+1)$ box to the right of the $(r,\lambda_r+1)$ box. From the second example above we get:

$$\begin{array}{cccccc} 1 & 3 & 6 & \ \\ 2 & 4 & 9 & 10 & 11 \\ 5 & 7 & \ & \ &\ \\ 8 & \ &\ & \ & \ \end{array}$$

So there's some inclusion-exclusion going on here that might reduce these tableaux to truncated tableaux . Unfortunately this idea seems to only work for $r=2$. Another idea is to take the value in the added box $(r,\lambda_r+1)$ and do RSK with it by pushing into the tableaux $\lambda$. This seems to have the effect of taking almost standard young tableaux at row $r$ to one's at rows $1,\cdots,r$ and gives a kind of Pieri rule for the aformentioned tableaux. In the above examples, RSK on the added box gives:

$$\begin{array}{cccccc} 1 & 2 & 4 & 6 & 8 \\ 3 & 5 & 7 & \ & \ \\ 9 & 11 & \ & \ &\ \\ 10 & \ &\ & \ & \ \end{array}$$

$$\begin{array}{cccccc} 1 & 3 & 6 & 10 \ \\ 2 & 4 & 9 & 11 \\ 5 & 7 & \ & \ &\ \\ 8 & \ &\ & \ & \ \end{array}$$

Unfortunately, I don't see how one might actually get a recurrence in terms of $1,2,\cdots,r$ almost-standard tableaux. This is because counting all possible RSK shapes won't ensure the added box has a value bigger than $(r,\lambda_r)$.

The only similar types of tableaux that I've seen are called composition tableaux (mainly because they allow for non-monotonically decreasing partitions), which come up in definitions of quasisymmetric functions. However, the rules for those tableaux are more general than just SYT.

$\endgroup$
1
  • $\begingroup$ As you probably know, this is a special case of the problem of counting the number of linear extensions of a poset. If there is no nice recurrence, you might want to check out John Stembridge's poset package for Maple, which will at least let you numerically compute these numbers. More generally, it will compute the W polynomial. If you're really lucky, perhaps the W polynomials will exhibit some pattern that will let you see how to compute them efficiently. $\endgroup$ Commented Nov 13, 2014 at 3:21

1 Answer 1

1
$\begingroup$

Assuming that I'm understanding your definition of an almost standard tableau, I have an observation. Note that if we take an almost standard tableau and rearrange the entries of column $\lambda_r+1$ in increasing order, we get a SYT. This defines an equivalence relation on almost standard tableaux, with equivalence classes indexed by SYT. You could try to calculate the sizes of the equivalence classes; this calculation seems nontrivial, however.

$\endgroup$

You must log in to answer this question.

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