5
$\begingroup$

Consider the set of permutations $\mathfrak{S}_n$, on $\{1,2,\dots,n\}$, and identify each element $\pi\in\mathfrak{S}_n$ with the corresponding permutation matrix.

There has been some study (e.g. see this paper) on the notion of diagonal and antidigonal $X$-ray sequences. Given a permutation matrix $\pi\in\mathfrak{S}_n$, starting from the bottom, construct the $k$-th diagonal sum $y_k$ of its entries for $k=1,2,\dots,2n-1$. Then, the sequence or word $y(\pi)=y_1y_2\cdots y_{2n-1}$ is called the diagonal $X$-ray of $\pi$.

For example, if $\pi=231\in\mathfrak{S}_3$ then $y(\pi)=10020$.

It is easy to check that the number $N(\mathfrak{S}_n)$ of distinct $X$-ray sequences of the set $\mathfrak{S}_n$ is less than $n!$ while the exact value is unknown.

QUESTION. Is there at least a $1^{st}$-order asymptotic estimate on the growth rate of $N(\mathfrak{S}_n)$?

$\endgroup$
  • $\begingroup$ (If you use mathfrak isn't $\mathfrak{S}_n$ (mathfrak S) more standard?) would you provide a few values of $N(\mathfrak{S}_n)$ for small $n$? $\endgroup$ – YCor Oct 16 '18 at 20:52
  • 2
    $\begingroup$ @YCor That's A019589. $\endgroup$ – Bullet51 Oct 17 '18 at 1:05

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.