About Warm-ups Problems News

Problem 10

Posted 06/01/2015
Refresh the webpage if formulas are not shown correctly.
----------------------
Previous    Next
----------------------

This problem is proposed by Ran Pan. If you want to submit your problem, please click here.

----------------------

A parity-alternating permutation in the $n$-th symmetric group $S_n$ is a permutation with no pairs of consecutive elements having the same parity. Actually, the set of all the parity-alternating permutations in $S_n$ is a subgroup of $S_n$, denoted by $P_n$. For example, $234165\in P_6$ and $7654123\in P_7$.

We say a permutation $\sigma=( \sigma_1,\sigma_2,\cdots,\sigma_n)\in S_n$ avoids 132 if there are no integers $1\le i < j < k\le n$ such that $\sigma_i\lt \sigma_k\lt \sigma_j$. Exercise E is a related warm-up that includes the definition of pattern 123 avoiding.

We say a permutation $\sigma=( \sigma_1,\sigma_2,\cdots,\sigma_n)\in S_n$ avoids 132 consecutively if there are no integers $1\le i\leq n-2$ such that $\sigma_i < \sigma_{i+2} < \sigma_{i+1}$. Exercise D is a related warm-up that includes the definition of consecutive pattern 123 avoiding.

$a(n)$ is the number of permutations in $P_n$ avoiding $132$.
$b(n)$ is the number of permutations in $P_n$ avoiding $132$ consecutively.

$c(n)$ is the number of permutations in $P_n$ avoiding $123$.
$d(n)$ is the number of permutations in $P_n$ avoiding $123$ consecutively.

Find $a(n)$, $b(n)$, $c(n)$ and $d(n)$.


----------------------

Updated 02/10/2017 by Dun Qiu

Based on the structure of $\mathcal S_n(132)$, we get the generating function for parity-alternating permutation in $\mathcal S_n(132)$. By Lagrange Inversion, we have:

  $a(2n)=\frac{2}{n}\binom{3n}{n-1}$ is counted by A046646,

  $a(2n-1)=\frac{1}{n}\binom{3n-2}{n-1}$ is counted by A006013.


Later, we extend parity-alternating permutations to $012\cdots k-1(\textrm{mod}\ k)$-alternating permutations on $\mathcal S_n(132)$, getting all generating functions of $\textrm{mod}\ k$ case and solving coefficients by Lagrange Inversion. There are many interesting facts in this generalization, and more results are coming.

$b(n)$, $c(n)$ and $d(n)$ are still open.




Back to top