1
$\begingroup$

Assume that there are $N$ positive integer sequence $\{1,...,N\}$. When the sequence is permuted, there exist $N!$ possible permuted sequences. I want to know how many sequences would have at least $K$ consecutive numbers inside, e.g., $\{i,...,i+K-1\}$ with an arbitrary positive integer $i$.

This can be a trivial problem, however, it would be helpful if someone let me know how to solve the problem (or any helpful references).

$\endgroup$
  • $\begingroup$ What exactly do you mean by "pattern"? Depending on your definition of "pattern" the answer to this question is very different. If you find it hard to define what you want, can you give a fully worked example, say for $N=5$, $i=1$ and $K=3$, so we can extrapolate from there? $\endgroup$ – Hamed May 3 '18 at 6:57
  • $\begingroup$ Exactly $K$ or do you mean at least $K$ consecutive? $\endgroup$ – hardmath May 3 '18 at 6:59
  • 1
    $\begingroup$ @hardmath I meant at least $K$ consecutive. $\endgroup$ – harpuia May 3 '18 at 8:22
  • $\begingroup$ I think the inclusion exclusion principle can be used here. Count all those containing e.g. (1,2,3), add all those containing (2,3,4), subtract all those containing (1,2,3,4) (because you double-counted), etc. en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle $\endgroup$ – antkam May 3 '18 at 23:04
1
$\begingroup$

First, $i$ can take only values in $\{1,\ldots,N-K+1\}$, so it has $N-K+1$ possibilities and the first value of this subsequence of $K$ consecutive numbers can start in $N-K+1$ positions.

Let's consider the first subsequence $\{1,\ldots,K\}$ and assume that it starts in position $i$. Then, you have $(N-K)!$ permutations for each $i$. So, if we restrict to permutations containing the subsequence $\{1,\ldots,K\}$, we have a total of $(N-K+1) \times (N-K)!$ cases.

Now, consider the second subsequence $\{2,\ldots,K+1\}$. The observation is that permutations containing the second subsequence have been already counted before unless the second subsequence starts in a position smaller than $2$. So, the second subsequence is allowed to start in only one position (the first one), and for this position there are again $(N-K)!$ permutations. This gives a total of $(N-K)!$ other possibilities for the second subsequence.

For the $i$-th subsequence, with $1<i\le K$, things do not change: permutations containing the $i$th subsequence have been already counted before unless the $i$-th subsequence starts in the first position.

For the $i$-th subsequence, with $i> K$, all permutations have been already counted.

Summing up, we have a total of \begin{align} & (N-K)! (N-K+1) + \underbrace{ (N-K)! + \cdots + (N-K)! }_{ K - 1 \mbox{ times}} \\ &= (N-K)! (N-K+1) + (K-1) (N-K)!\\ & = (N-K)! N \end{align} permutations.

$\endgroup$
  • 1
    $\begingroup$ Not sure I understand your answer... for N=5, K=2, the case (5,1,4,2,3) has (2,3) appearing not in the first position, and it certainly has not been counted before when you count the permutations containing the subsequence (1,2). In general, I think this question requires using the inclusion exclusion principle. $\endgroup$ – antkam May 3 '18 at 23:01
  • $\begingroup$ @antkam You're right (again!), there is a conceptual error in my argument. $\endgroup$ – user52227 May 4 '18 at 7:58
  • $\begingroup$ Even though I've noticed there can be an error in your answer, I made my own answer from your one and other comments. Thx. $\endgroup$ – harpuia May 6 '18 at 4:45

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.