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
----------------------
This problem is proposed by
Ran Pan. If you want to submit your problem, please click
here.
----------------------
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