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$

Noah
  • 307
  • 1
    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 02: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
  • 1
    @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
  • 1
    @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

1 Answers1

1

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\}$.

By the way, these are the very important Catalan numbers.

Brian M. Scott
  • 616,228
  • 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
  • 1
    @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
  • i the first part σ(1),…,σ(k−1) we have (k-1)! and in the second one \σ(k+1),…,σ(n) we have (n-k)! – Noah Apr 26 '15 at 19:40
  • 1
    @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