Given a set of numbers {$1,2,...,n$}, I want to find the number of permutations without 3-term subsequence of '1-3-2' pattern
Now this would be $A_n = n! - U_n$, where $A_n$ is the number of acceptable permutations and $U_n$ is the number of unacceptable permutations.
I have a vague idea that I should be using the Catalan numbers to consider cases of $U_n$. I could think of this as the parentheses problem where "(" is the low number, "A" is the high number, and ")" is the high number but I am unsure this works.
Would this be a valid argument? Any ideas?
This is a classical problem in the theorem of "permutation avoidance". I'm not sure what you mean by "acceptable" permutations; ones which have no $132$ patterns or ones which have a $132$ pattern. I'll let $C_n$ be the permutations with no $132$ patterns; clearly $C_n=n!$ for $n\le2$.
For a general permutation on $\{1,\ldots,n\}$, thought of as a word, to be $132$-avoiding it must have the form $w\,n\,w'$ for some $k$ where $w'$ is a $132$-avoiding word on $\{1,\ldots,k\}$ and $w'$ is a $132$-avoiding word on $\{k+1,\ldots,n-1\}$. For a given $k$ the number of such words is $C_kC_{n-k-1}$ and so we get the recurrence $$C_n=\sum_{k=0}^{n-1}C_kC_{n-k-1}$$ which may be familiar.