Let $\mathfrak{S}_n$ be the permutation group on $[n]$. Given the pattern $\sigma=k(k-1)\cdots321$, let $I_n(\sigma)$ be the number of involutions in $\mathfrak{S}_n$ that avoid the pattern $\sigma$. Amitai Regev proved (see this paper and references therein) the case $k=4$: $$I_n((4321))=\sum_{k\geq0}\binom{n}{2k}C_k$$ which are the Motzkin numbers. Here $C_k$ are the Catalan numbers.

Given an integer partition $\lambda$, draw the Young diagram and fill in hook-lengths of each cell. If a number $t$ is not among these hook-lengths then $\lambda$ is called a $t$-core. If it misses $a, b, c$ then call it an $(a,b,c)$-core partition.

Let $N(n,n+1,n+2)$ be the number of all partitions that are $(n,n+1,n+2)$-core partitions. Then (see this paper for definitions and this result) $$N(n,n+1,n+2)=\sum_{k\geq0}\binom{n}{2k}C_k.$$

QUESTION. Is there a direct bijection between the above $(4321)$-avoiding involutions in $\mathfrak{S}_n$ and $(n,n+1,n+2)$-core partitions?

EDIT. Fedor's comment/question below alerted me to correct a mistake: we are only counting involutions and not all permutations.

  • I find it reasonable to reproduce the definiton of $S$-core here. – Fedor Petrov Dec 12 '16 at 15:36
  • I edited to account for this, hope it helps. – T. Amdeberhan Dec 12 '16 at 15:59
  • Hm, what are six diagrams without hook lengths 3,4,5? – Fedor Petrov Dec 14 '16 at 17:50
  • Well, empty diagram and three diagrams with 1 or 2 boxes, what else? – Fedor Petrov Dec 14 '16 at 17:53
  • @Fedor: Well, the Motzkin numbers for $n\geq0$ are: $1, 1, 2, 4, 9, 21, 51, 127,\dots$. So, corresponding to $(3,4,5)$, there are $4$ core partitions. Where did you get $6$? – T. Amdeberhan Dec 14 '16 at 18:15

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.