0

I have $n$ numbers and I want to calculate the number of permutations in which $k$ certain numbers appear after each other (e.g. numbers $1$ to $10$ ($n = 10$), and let's say I want the permutations in which $6$ comes after $3$, and $3$ comes after $9$ ($k = 3$); they do not have to be subsequent like $..**9\;3\;6**..$ but any permutation like $..2**\;9**\;4**\;3**\;8\;7**\;6**..$ is also acceptable as still $6$ comes after $3$ and $3$ comes after $9$). I went ahead and solved it for different situations and came up with the following sort of a formula:

$$-1+\sum\limits_{i=0}^{n-k}(i+1)\cdot(n-k-i+1)!$$

So like for $n = 5$ and $k = 3$ we have $13$ possible permutations for any selected $3$ numbers (like for $1,\;3$ and $4$ to appear after each other among numbers $1$ to $5$) and so on! It seems the formula works fine (I tried it for several combinations) but you know this is a terrible way of calculation (at least to me!) as I had to first calculate the answer for many different situations and then eventually obtain the above-mentioned formula. So I was wondering if there is a better way of calculating this!

Rushabh Mehta
  • 13,663
RezAm
  • 129
  • For the specific problem you mention, note that each possible ordering of the three elements is equi-probable...there are $6$ possible orders, so... – lulu May 13 '18 at 18:57
  • 6 possible orders of what? As I said, I just need to calculate the number of permutations in which k arbitrary selected numbers show up in a certain sequence; like if I have 200 numbers, we know there are 200! possible permutations. now lets say we select 34, and 112, and we wanna know in how many of those possible permutations, the number 34 is coming after 112. – RezAm May 13 '18 at 19:04
  • $6$ permutations of your three special numbers. That is, the numbers $3,6,9$ can occur in any order in any given permutation and each order is equally likely. – lulu May 13 '18 at 19:06
  • 1
    For the example in your comment the answer is clearly $\frac 12$ since it is equally likely that one precedes the other. To make this clear: divide all the permutations into two types, type $A$ in which $34$ precedes $112$ and type $B$ in which $112$ precedes $34$. These two sets are in bijection by the transposition $34\leftrightarrow 112$. – lulu May 13 '18 at 19:06
  • Thanks, with that the possible numbers should always be like 1/k! I guess? – RezAm May 13 '18 at 19:16
  • 1
    Yes, that;s correct. – lulu May 13 '18 at 19:18

1 Answers1

2

Just ignore all the other numbers and there are $k!$ possible orders of the $k$ numbers, one of which is acceptable. That means $\frac 1{k!}$ of the permutations are acceptable. As there are $n!$ total permutations, the number of acceptable ones is $$\frac {n!}{k!}$$

Ross Millikan
  • 374,822