About Warm-ups Problems News

Problem 13

Posted 08/08/2015 and updated 08/11/2015, 06/06/2016
Refresh the webpage if formulas are not shown correctly.
----------------------
Previous    Next
----------------------

In Exercise E, we mentioned permutations avoid 123 and Exercise D is about permutations avoid 123 consecutively. It would be fun if we involve these two notions in one problem.

Suppose `\pi` are `\tau` are two permutations, here we'd like to ask how many permutations of length `n` avoid `\pi` and also avoid `\tau` consecutively.

`a(n)` is the number of permutations of length `n` that avoid `123` and meanwhile avoid `321` consecutively.


Find `a(n)`.


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

Updated 08/11/2015 by Ran Pan

Some interesting facts:

For `n\ge 1`, the several initial terms of `a(n)` are `1, 2, 4, 7, 10, 19, 28, 56, 84`, which coincide with A104722 from `4`.

Suppose `A_\pi^{c.\tau(n)}` is the number of permutations of length `n` that avoid `\pi` and avoid `\tau` consecutively. We find that

  `A_{132}^{c.123}(3)=4`, `A_{132}^{c.123}(4)=9`, `A_{132}^{c.123}(5)=21`, `A_{132}^{c.123}(6)=51`, `A_{132}^{c.123}(7)=127`, `A_{132}^{c.123}(8)=323`, which seem to coincide with Motzkin numbers(A001006).

  `A_{132}^{c.321}(3)=4`, `A_{132}^{c.321}(4)=9`, `A_{132}^{c.321}(5)=21`, `A_{132}^{c.321}(6)=51`, `A_{132}^{c.321}(7)=127`, `A_{132}^{c.321}(8)=323`, which seem to coincide with Motzkin numbers(A001006).

  `A_{123}^{c.132}(3)=4`, `A_{123}^{c.132}(4)=9`, `A_{123}^{c.132}(5)=21`, `A_{123}^{c.132}(6)=51`, `A_{123}^{c.132}(7)=127`, `A_{123}^{c.132}(8)=323`, which also seem to coincide with Motzkin numbers(A001006).

  `A_{321}^{c.132}(3)=4`, `A_{321}^{c.132}(4)=9`, `A_{321}^{c.132}(5)=23`, `A_{321}^{c.132}(6)=63`, `A_{321}^{c.132}(7)=178`, `A_{321}^{c.132}(8)=514`, which seem to coincide with A135307.

  `A_{1324}^{c.123}(3)=5`, `A_{1324}^{c.123}(4)=16`, `A_{1324}^{c.123}(5)=60`, `A_{1324}^{c.123}(6)=258`, `A_{1324}^{c.123}(7)=1238`, `A_{1324}^{c.123}(8)=6531`. No such sequences are found on OEIS.

  `A_{1324}^{c.321}(3)=5`, `A_{1324}^{c.321}(4)=16`, `A_{1324}^{c.321}(5)=56`, `A_{1324}^{c.321}(6)=220`, `A_{1324}^{c.321}(7)=932`, `A_{1324}^{c.321}(8)=4269`. No such sequences are found on OEIS.





Updated 06/06/2016 and contributed by Dun Qiu

Based on bijection between certain permutations and Dyck paths, we are sure that:

  `A_{132}^{c.123}(n)` is counted by Motzkin numbers.

  `A_{132}^{c.321}(n)` is counted by Motzkin numbers.

  `A_{123}^{c.132}(n)` is counted by Motzkin numbers.


More results are coming.




Back to top