2022-07-02

How many 4-permutations of the positive integers not exeeding 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\ast 97\ast 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.

Alexzander Bowman

Step 1
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.
Step 2
Let's examine your example of the first four positive integers. If $k=1$, the admissible permutations of $\left\{1,2,3,4\right\}$ 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 $\left\{1,2,3,4\right\}$ 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$.

Do you have a similar question?