4
$\begingroup$

Let $S_n$ be the symmetric group. For any sequence of numbers $y=[y_1,y_2,\cdots,y_k]$, define the flattening operation as $\mbox{flatt}_{k}(y)$ as a relabeling of $y_1,y_2,\cdots,y_k$ in terms of their relative order with numbers from $[k]$. So for example $\mbox{flatt}_3([4,2,5])=[2,1,3]$, $\ \mbox{flatt}_5([2,1,3,4,5])=[2,1,3,4,5]$.

For a permutation $\pi\in S_n$, denote by $\pi(2,n-1):=[\pi(2),\pi(3),\cdots,\pi(n-1)]$

Define $X_1:=\{[1]\}$, $X_2:=\{[2,1]\}$. Now define

$$X_n=\{\pi\in S_n:\ \pi(1)=\pi(n)+1, \ \mbox{flatt}_{n-2}(\pi(2,n-1))\in X_{n-2} \}$$

For example,

$$X_1:=\{[1]\}$$ $$X_2:=\{[2,1]\}$$ $$X_3=\{[3,1,2],[2,3,1]\}$$ $$X_4=\{[4,2,1,3],[3,4,1,2],[2,4,3,1]\}.$$

It's easy to see $|X_n|=(n-1)!!$. Does this class of permutations have a common name? Have they been studied before? I've checked the lists at oeis.org (by cardinality) and findstat.org but didn't see anything.

Edit: Here's the OEIS for (2n-1)!!, the even $X_{2n}$'s.

$\endgroup$
6
  • $\begingroup$ FYI: What you call "flattening" is known as "packing" in the combinatorial Hopf algebras community. $\endgroup$ Nov 23, 2014 at 4:52
  • $\begingroup$ Isn't $\mathop{\rm flat}_3([4,2,5])=[2,1,3]$? Otherwise I do not understand what is `relabeling'... $\endgroup$ Nov 24, 2014 at 14:12
  • $\begingroup$ @IlyaBogdanov: must be dyslexia or something. Changed, thanks! $\endgroup$
    – Alex R.
    Nov 24, 2014 at 16:14
  • $\begingroup$ Do you have a bijection between $X_{2n}$ and perfect matchings on $[2n]$? $\endgroup$ Nov 24, 2014 at 17:46
  • 1
    $\begingroup$ @darij grinberg: I had standardization in my dictionary, not packing. Are they the same thing? $\endgroup$
    – user35313
    Nov 24, 2014 at 18:21

0

Your Answer

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

Browse other questions tagged or ask your own question.