1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Alphabetically ordered in consecutive positions (BD) or any positions (B - D) ? $\endgroup$
    – true blue anil
    Mar 15, 2016 at 5:36
  • 1
    $\begingroup$ OP means any positions. Only that is consistent with 119/120. $\endgroup$
    – talegari
    Mar 15, 2016 at 6:34

1 Answer 1

Reset to default
0
$\begingroup$

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).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .