# $a_n=a_0a_{n-1} + a_1a_{n-2} \dots + a_{n-1}a_0$

let σ∈Sn and τ∈Sm with m$\leq$n . We say σ avoid the permutation τ if there are no subset ${j_i< \dots <j_m} \subset [n]$ with:

$\sigma(j_i)<\sigma(j_l) \Leftrightarrow \tau(i)<\tau(l)$ for 1$\leq i \leq m$.

example: if m=3 n=4 and $\tau = 123$ then 4321, 3241 etc avoid $\tau$

Now let $a_n$ be #permutations in $S_n$ that avoid 312 , $a_0=1$

prove that $a_n=a_0a_{n-1} + a_1a_{n-2} \dots + a_{n-1}a_0$

• Even after I read Brian's answer, I still don't understand your question. What does it mean "... that avoid 312"? – achille hui Apr 26 '15 at 2:45
• You have done a decent job of clarifying your question. Now you should add the work you have done on the problem so far and just where you are stuck. – Rory Daulton Apr 26 '15 at 10:44
• @achille: That’s a standard concept; Noah shouldn’t be penalized for not defining it in the question. – Brian M. Scott Apr 26 '15 at 19:09
• @BrianM.Scott Well, I simply didn't know about the concept. Isn't it better to make it clear for the "reasonably" general public. In any event, I retract my downvotes and vote to reopen. – achille hui Apr 26 '15 at 19:22
• @achille: Yes, it’s better; I just didn’t expect this concept to be all that unfamiliar, so I can understand why the OP might not have realized that it would be a good idea. (I’m an amateur at combinatorics, so I tend to assume that if I’m familiar with something in the field, quite a few other people will also be familiar with it!) – Brian M. Scott Apr 26 '15 at 19:29

HINT: Show that the number of permutations $p_1p_2\ldots p_n$ of $[n]=\{1,2,\ldots,n\}$ such that $p_k=1$ is $a_{k-1}a_{n-k}$. I’ve left a further hint in the spoiler-protected block below; mouse-over to see it.
Show that in this case $p_1\ldots p_{k-1}$ must be a permutation of $\{2,\ldots,k\}$, and $p_{k+1}\ldots p_n$ must be a permutation of $\{k+1,\ldots,n\}$.
• thank you @brian-m-scott for your hints. but i still have a problem. We know that the number of the permutations is n! . What does it mean $p_k$ = 1 is $a_{k-1}a_{n-k}$ – Noah Apr 26 '15 at 14:57
• @Noah: That’s not quite what I said. $a_{k-1}a_{n-k}$ is the number of permutations $p_1\ldots p_n$ such that $p_k=1$. In the notation that you’ve used in the edited question, I’m saying that $a_{k-1}a_{n-k}$ is the number of permutations $\sigma\in S_n$ such that $\sigma(k)=1$. I’m suggesting that you should consider the parts of the permutation before $\sigma(k)$, namely, $\sigma(1),\ldots,\sigma(k-1)$ and $\sigma(k+1),\ldots,\sigma(n)$, separately: what numbers have to be in each of those parts? – Brian M. Scott Apr 26 '15 at 19:14
• @Noah: No, you don’t: not all of the $(k-1)!(n-k)!$ combinations avoid $312$. – Brian M. Scott Apr 26 '15 at 19:41