# $X$-rays of permutations

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)$$?

• (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$? – YCor Oct 16 '18 at 20:52
• @YCor That's A019589. – Bullet51 Oct 17 '18 at 1:05