How many 4-permutations of the positive integers not exeeding 100 contain three consecutive integers k, k + 1, k + 2, in the correct order

Question

There is a discrete math question I am strugguling to understand:

"How many 4-permutations of the positive integers not exceeding 100 contain three consecutive integers k, k + 1, k + 2, in the correct order"

a) where these consecutive integers can perhaps be separated by other integers in the permutation?

b) where they are in consecutive positions in the permutation?

We know that the number of permutations with repetition for a is $98*97*4$ since for every 98 possible choices of k we have 97*4 possible 4-permutations, (arrangements) of k,k+1,k+2 and another number different from those 3.

But how can I compute the repreated permutations?

For instance, consider k=1. Then some of the possible permutations are $"1,2,3,4", "4,1,2,3", "1,4,2,3"$ which are also permutations for k=2. I think that given a number k I should find the 4-permutations of k that are repeated in other permutations. Then i will need to multiply this value for 98, the number of total possible Ks and subtract this from the first result. But I do not know how can I compute them.

Sorry if the question has already been made, but my point of interest regards how to find the repetitions I am interested in.

Thanks in advance

You mention repetitions, but you don't indicate whether your $4-$permutations allow repetitions or not. — lulu, Oct 30 '21 at 11:33
Regardless, there aren't very many possible bad patterns. Just describe all of those and count them case by case. — lulu, Oct 30 '21 at 11:34
Does this answer your question? How many 4-permutations of the positive integers not exceeding 100 contain three consecutive integers in the correct order — Sebastián V. Romero, Dec 27 '21 at 12:03

score 1 · Answer 1 · answered Oct 30 '21 at 18:06

How many $4$-permutations of the positive integers not exceeding $100$ contain three consecutive integers $k, k + 1, k + 2$ in the correct order where these consecutive integers can perhaps be separated by other integers in the permutation?

There are $98$ ways to choose $k$, the smallest of the three consecutive integers and $97$ ways to choose a fourth integer from the set of positive integers not exceeding $100$. There are four ways to place the integer which is not among $k, k + 1, k + 2$ within the $4$-permutation. This would appear to yield $98 \cdot 97 \cdot 4$ admissible permutations.

However, we have counted each of the $97$ permutations of four consecutive increasing integers twice.

Let's examine your example of the first four positive integers. If $k = 1$, the admissible permutations of $\{1, 2, 3, 4\}$ are $(1, 2, 3, 4), (1, 2, 4, 3), (1, 4, 2, 3), (4, 1, 2, 3)$ since $1, 2, 3$ must appear in the correct order. If $k = 2$, the admissible permutations of $\{1, 2, 3, 4\}$ are $(1, 2, 3, 4), (2, 1, 3, 4), (2, 3, 1, 4), (2, 3, 4, 1)$ since $2, 3, 4$ must appear in the correct order. Notice that the only common permutation for this set of numbers is $(1, 2, 3, 4)$.

Thus, the number of admissible permutations is $98 \cdot 97 \cdot 4 - 97$.

How many 4-permutations of the positive integers not exeeding 100 contain three consecutive integers k, k + 1, k + 2, in the correct order

1 Answers1