27
$\begingroup$

Assuming that the problem of exhibiting a bijection is not considerd a frivolous pursuit, allow me to ask a question troubling me for some time now.

Let $\lambda \vdash n$ denote the fact that $\lambda$ is a partition of $n$. Denote the number of parts by $l(\lambda)$. If $T$ is a standard Young tableau (SYT), we will denote the underlying partition shape by $sh(T)$.

Given a positive even integer $2n$, let $$ Pe_{2n}=\{ \lambda: \lambda\vdash 2n,\text{ } l(\lambda) \leq3 \text{ and all parts of } \lambda \text{ are even} \}$$ and $$ Qe_{2n}=\{ \lambda: \lambda\vdash 2n, \lambda = (k,k,1^{2n-2k}), \text{ }k\geq 1 \}$$

Using these sets we will define two more sets whose elements are SYTs. $$ TPe_{2n}=\{T: T \text{ an SYT, } sh(T)\in Pe_{2n} \}$$ and $$ TQe_{2n}=\{T: T \text{ an SYT, } sh(T)\in Qe_{2n} \}$$

$\textbf{Question}$: Is there a bijective proof exhibiting the fact that the cardinalities of $TPe_{2n}$ and $TQe_{2n}$ are equal?

The second question is very similar. Given an odd positive integer $2n+1$, let $$ Po_{2n+1}=\{ \lambda: \lambda\vdash 2n+1,\text{ } l(\lambda)=3 \text{ and all parts of } \lambda \text{ are odd} \}$$ and $$ Qo_{2n+1}=\{ \lambda: \lambda\vdash 2n+1, \lambda = (k,k,1^{2n+1-2k}), \text{ }k\geq 1 \}$$

Using these sets we will define two more sets whose elements are SYTs. $$ TPo_{2n+1}=\{T: T \text{ an SYT, } sh(T)\in Po_{2n+1} \}$$ and $$ TQo_{2n+1}=\{T: T \text{ an SYT, } sh(T)\in Qo_{2n+1} \}$$

$\textbf{Question}$: Is there a bijective proof exhibiting the fact that the cardinalities of $TPo_{2n+1}$ and $TQo_{2n+1}$ are equal?

I tried quite a few approaches ( Motzkin path interpretations, matching diagrams etc) but did not succeed. I hope somebody here can guide me.

The relevant OEIS entry would be link text

Thanks,

Vasu

$\endgroup$
9
  • $\begingroup$ Just out of curiosity, how did you discover these identities? What is the proof you currently have? And lastly, have you looked into A.Regev's most recent papers (on arXiv)? There might be a bijection using the number of peaks of Motzkin paths... $\endgroup$ Jul 14, 2011 at 1:01
  • $\begingroup$ @Gjergji: I was working on the computation of Kronecker coefficients and was intrigued by certain identities relating to counting tableaux of bounded height implied by them. You might want to look into work by Garsia-Xin-Zabrocki on computing $s_{(n,n)}*s_{(n,n)} and other examples.(one of the identities I happened to find was listed in this question: mathoverflow.net/questions/47070/…) $\endgroup$ Jul 14, 2011 at 3:14
  • $\begingroup$ ... So I started playing around by counting Young tableaux with addition constraints and this is what I ended up with. One potential way to calculate $TPe_{2n}$ where I am actually counting fixed point free involutions with length of longest longest increasing subsequence bounded by 3, (I am sorry I haven't really worked out the details, and this was long back) would be to use Gessel's determinantal formulae as listed on Pg. 15 of Stanley's article on increasing and decreasing sequences and their variants (link: www-math.mit.edu/~rstan/papers/ids.pdf). $\endgroup$ Jul 14, 2011 at 3:14
  • $\begingroup$ ... And to answer your last question, I have had a look at Regev's stuff but haven't managed to get anything concrete out of it. Since I am pretty certain the problem would yield to other approaches, I am very interested in a bijective proof $\endgroup$ Jul 14, 2011 at 3:17
  • $\begingroup$ I'm getting different sizes for $TP_{10}$ and $TQ_{10}$. Are you sure you don't have a typo somewhere? $\endgroup$ Sep 3, 2011 at 17:23

2 Answers 2

11
$\begingroup$

Not an answer, but too long for a comment. This addresses a previous comment and points out the smallest case where the requested bijection is not obvious (for the even case).

Through $n = 8$, the partition sets are in bijection via a combination of transposition and the identity map, so there is a direct correspondence for the tableaux.

$Pe_{10} = \{10, 82, 64, 622, 442\}$ and $Qe_{10} = \{55, 4411, 331^4, 221^6, 1^{10}\}$. The partitions that don't match up are 64 & 442 versus 55 & 4411.

Using the hook length formula, there are 90 standard Young tableaux of shape (6,4) and 252 of shape (4,4,2), so these contribute 342 to $TPe_{10}$. (Sorry for the change in partition notation, but "90 of shape 64" looked strange.) There are 42 tableaux of shape (5,5) and 300 of shape (4,4,1,1), also contributing 342 to $TQe_{10}$. So the conjecture does hold for $n=10$.

This example shows that the requested bijection cannot preserve the tableaux shape/underlying partition.


The next case is even more interesting because the tableaux counts match even though there are not the same number of partitions in the sets.

The unmatched partitions are $(8,4),(6,4,2),(4,4,4) \in Pe_{12}$ and $(5,5,1,1),(4,4,1,1,1,1) \in Qe_{12}$. And the sums work: Writing $\textrm{SYT}(\lambda)$ for the number of standard Young tableaux with shape $\lambda$, we have $$\textrm{SYT}((8,4))+\textrm{SYT}((6,4,2))+\textrm{SYT}((4,4,4))=275+2673+462=3410,$$ $$\textrm{SYT}((5,5,1,1))+\textrm{SYT}((4,4,1,1,1,1))=1485+1925=3410.$$

The next two cases work but don't offer anything new. Here are a few general comments.

  • From a formula for the number of partitions of $n$ with up to three parts, $|Pe_{2n}| = \lfloor \frac{(n+3)^2}{12} \rceil$ where $\lfloor \cdot \rceil$ denotes nearest integer.

  • For $n$ odd, 3 partitions match up between the two sets: $(2n)$, $(2n-2,2)$, and $(2n-4,2,2)$ in $Pe_{2n}$ with $1^{2n}$, $221^{2n-4}$, and $331^{2n-6}$ in $Qe_{2n}$ (matching by transposition).

  • For $n$ even, 4 partitions match because $(n,n)$ is in both sets.

  • Continuing along this line of reasoning would require formulas for $\textrm{SYT}(\lambda)$ for partitions from each of the sets.


Following up on the last bullet, in the 1996 JCTA note "Polygon Dissections and Standard Young Tableaux," Stanley credits O'Hara and Zelevinsky with a formula for $\textrm{SYT}(\lambda)$ for $\lambda = kk1^m$. Rewritten in terms of $k$ and $m$, it is $$\frac{1}{2k+m+1} \binom{2k+m+1}{k} \binom{m+k-1}{k-1}.$$ Perhaps Stanley's bijection between such tableaux and certain sets of nonintersecting diagonals in a polygon discussed in the note could help.


It's not hard to work out that $$\textrm{SYT}((a,b,c))=\frac{(a+b+c)!(a-b+1)(b-c+1)(a-c+2)}{(a+2)!(b+1)!c!}$$ (without regard to the parity of $a,b,c$).

$\endgroup$
10
+50
$\begingroup$

Let me explain a way to prove such results. There are (mostly) two types of people out there, those that think of the $n$th Catalan number as $\frac{1}{n+1}\binom{2n}{n}$ and those that think of it as $\binom{2n}{n}-\binom{2n}{n-1}$. The first type of people will likely think of Dyck paths as eqivalence classes or $\mathbb Z/(n+1)\mathbb Z$ orbits of paths, whereas the second type will probably think of Dyck paths as "paths inside an $n\times n$ rectangle that don't cross the origin" (See proof 2 vs proof 3 here). While the first type would probably be happy to count standard young tableaux using the usual form of the hook-length formula, the second type would probably prefer the (equivalent):

Jacobi-Trudi Formula

The number of Standard Young Tableaux on a partition of shape $\lambda=(\lambda_1,\dots,\lambda_k)$ of $n$ is $$f^{\lambda}=\sum_{\sigma \in S_k}\varepsilon(\sigma)\binom{n}{\lambda_1+k-\sigma(k)\, ,\dots,\,\lambda_k+1-\sigma(1)}.$$ Where $\varepsilon$ denotes the sign of a permutation. Similar to the Catalan numbers in this presentation one sacrifices obvious positivity but has obvious integrality. For the sake of illustration, in the case $k=3$, this says $$f^{(a,b,c)}=\binom{n}{a,b,c}+\binom{n}{a+1,b+1,c-2}+\binom{n}{a+2,b-1,c-1}-\binom{n}{a+1,b-1,c}-\binom{n}{a,b+1,c-1}-\binom{n}{a+2,b,c-2}.$$

The computation:

Let's take the case of three even parts, although this method will work for the odd case as well as the general case of partitions with a fixed (arbitrary) number of rows. If one sums the quantity $f^{(a,b,c)}$ over all triples of integers $a\geq b\geq c\geq 0$ with $a+b+c=n$ then the multinomial coefficients form the formula above telescope and we are left with $$|TPe_{2n}|=\sum_{k\geq 0}\binom{2n}{k,k,2n-2k}-\sum_{k\geq 0}\binom{2n}{k,k+1,2n-2k-1}$$

Now we can turn our attention to $TQe_{2n}$. We can count the number of SYT of shape $(k,k,1^{2n-2k})$ from the hook length formula, but instead of presenting it in "type one" as Brian Hopkins did in the other answer, we will use the "type two" presentation $$f^{(k,k,1^{2n-2k})}=\binom{2n}{k}\binom{2n-k-1}{k-1}-\binom{2n}{k+1}\binom{2n-k}{k}$$ $$=\binom{2n}{k,k,2n-2k}-\binom{2n}{k}\binom{2n-k-1}{k}-\binom{2n}{k-1}\binom{2n-k}{k}.$$

So in order to get the desired equality we sum over all $k\geq 1$ $$|TQe_{2n}|=\sum_{k\geq 1}f^{(k,k,1^{2n-2k})}=\sum_{k\geq 1}\left(\binom{2n}{k,k,2n-2k}-\binom{2n}{k}\binom{2n-k-1}{k}-\binom{2n}{k-1}\binom{2n-k}{k}\right)$$ $$=\sum_{k\geq 1}\binom{2n}{k,k,2n-2k}-\sum_{k\geq 0}\left(\binom{2n}{k}\binom{2n-k-1}{k}+\binom{2n}{k}\binom{2n-k-1}{k+1}\right)+\binom{2n}{0}\binom{2n-1}{0}$$ $$=\sum_{k\geq 1}\binom{2n}{k,k,2n-2k}-\binom{2n}{k,k+1,2n-2k-1}+\binom{2n}{0,0,2n}$$ $$=\sum_{k\geq 0}\binom{2n}{k,k,2n-2k}-\sum_{k\geq 0}\binom{2n}{k,k+1,2n-2k-1}=|TPe_{2n}|.$$

Can it be made bijective?

Yes. All the manipulations with binomial coefficients have obvious bijective interpretations in terms of lattice paths, so one would have to do the same for the Jacobi-Trudi formula mentioned above. This is classical for the case of Catalan numbers, but it can be generalized for any partition using a similar reflection trick. I have been lazy and didn't work out the final bijection for you, but at least this is a start. I am currently writing a note about such bijections between SYT's with bounded parts, so if no one has explained it by then I'll make sure to update this answer.

$\endgroup$
2
  • $\begingroup$ Why do you call your formula the "hook length formula"? It's quite a journey from it. I think Jacobi-Trudi would be a better name for it. $\endgroup$ Sep 18, 2015 at 1:43
  • $\begingroup$ That's a good point, Jacobi-Trudi is a much better name. The point was that there are many ways to go about counting SYT's other than just the hook-length formula, so it was more intended as a cheeky companion to Brian's answer. :) $\endgroup$ Sep 18, 2015 at 2:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.