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$

  • 1
    $\begingroup$ Even after I read Brian's answer, I still don't understand your question. What does it mean "... that avoid 312"? $\endgroup$ – achille hui Apr 26 '15 at 2:45
  • $\begingroup$ 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. $\endgroup$ – Rory Daulton Apr 26 '15 at 10:44
  • 1
    $\begingroup$ @achille: That’s a standard concept; Noah shouldn’t be penalized for not defining it in the question. $\endgroup$ – Brian M. Scott Apr 26 '15 at 19:09
  • $\begingroup$ @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. $\endgroup$ – achille hui Apr 26 '15 at 19:22
  • 1
    $\begingroup$ @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!) $\endgroup$ – 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\}$.

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

  • $\begingroup$ 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}$ $\endgroup$ – Noah Apr 26 '15 at 14:57
  • 1
    $\begingroup$ @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? $\endgroup$ – Brian M. Scott Apr 26 '15 at 19:14
  • $\begingroup$ i the first part σ(1),…,σ(k−1) we have (k-1)! and in the second one \σ(k+1),…,σ(n) we have (n-k)! $\endgroup$ – Noah Apr 26 '15 at 19:40
  • 1
    $\begingroup$ @Noah: No, you don’t: not all of the $(k-1)!(n-k)!$ combinations avoid $312$. $\endgroup$ – Brian M. Scott Apr 26 '15 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.