I would like to know how to calculate the probability of finding an alphabetically ordered subset of at least K elements in a set of N alphabetical elements.
For example, for a set of N letters from A to from A to E ordered randomly, what is the probability that I will find a subset of at least 2 alphabetically order letters (ex. AB, BD, CE) at any position in the list?
I know the answer to this is 119/120 because I've done it manually. But I need to be able to calculate it for larger N and K values. Can somebody help?
Forgive me if I'm not using the right terminology (I'm new to this), I hope my question is still clear enough.
Thank you in advance, P.
We are looking $$\frac{n! - G_k(n)}{n!}$$ where $G_k(n)$ is number of permutations of $[n]$ which avoid the pattern $12\dots k$. Zeilberger's paper, helps you compute it (a maple program is included).