About Warm-ups Problems News

Problem 10

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

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 `7654132\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.

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.

`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.

Find `a(n)` and `b(n)`.




Back to top