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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.