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$ Commented 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$ Commented Nov 24, 2014 at 14:12
  • $\begingroup$ @IlyaBogdanov: must be dyslexia or something. Changed, thanks! $\endgroup$
    – Alex R.
    Commented Nov 24, 2014 at 16:14
  • $\begingroup$ Do you have a bijection between $X_{2n}$ and perfect matchings on $[2n]$? $\endgroup$ Commented 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
    Commented Nov 24, 2014 at 18:21

0

You must log in to answer this question.

Browse other questions tagged .