How many 4-permutations of the positive integers not exceeding $100$ contain three consecutive integers in the correct order

a.) where consecutive means in the usual order of the integers and where these consecutive integers can perhaps be separated by other integers in the permutation?

b.) where consecutive means both that the numbers be consecutive integers and that they be in consecutive integers and that they be in consecutive positions in the permutation?

My Attempt:
3 consecutive integers is, $k, k+1, k+2$, thus $k$ is limited to $98$,

a.) The number of ways we can place and the 2 others is $C(4, 3) = 4$. Since $3$ integers are already taken by $k, k+1, k+2$, the last integer can have 97 integers, thus

$$4*98*97 = 38,024$$

b.) Since $k, k+1, k+2$ have to be consecutive in placement, there's only two possible place for that, thus

$$2*98*97 = 19, 012$$

Both of my answers are a bit off compared to the answer key. In the answer key, a.) $37,927$ b.) $18,915$. One might notice that if my answers are subtracted $97$, I get the answer key's answer. So how exactly do you arrive to these numbers? I'm out of ideas.

  • 1
    $\begingroup$ Inclusion-exclusion principle? That is, make sure we don't double count the sequences of all 4 integers consecutively. $\endgroup$ – hardmath Jul 20 '14 at 13:27
  • $\begingroup$ i feel you, bro!! i did the same stupid mistake $\endgroup$ – Godfather Oct 17 '16 at 10:13

We need to use Inclusion/Exclusion. The "four consecutives" cases have been double-counted.

  • $\begingroup$ Right! Thanks for the help again. $\endgroup$ – JoeyAndres Jul 20 '14 at 13:32
  • $\begingroup$ You are welcome. In "consecutives" problems, such as at least four consecutive heads, the same sort of issue comes up. $\endgroup$ – André Nicolas Jul 20 '14 at 13:35
  • $\begingroup$ @AndréNicolas I'm confused as to what we're double counting in part b. I computed C(98,1) * 2 * C(100,1) to get the answer. Where did I go wrong? $\endgroup$ – Dunka Nov 6 '14 at 21:37
  • 1
    $\begingroup$ We interpret $3$ consecutive as meaning at least $3$ consecutive. You have counted $12,13,14,15$ twice in your way of counting, once as $12,13,14$ followed by $15$, and once as $13,14,15$ preceded by $12$. Every one of the $4$ consecutives has been counted twice. There are $97$ ways to have $4$ consecutives, which is why your answer for b) is greater by $97$ than the official (and correct) answer. To get the right answer, we do as you did, but being aware that one is double-counting, and subtracting $97$ at the end to compensate. (Cont) $\endgroup$ – André Nicolas Nov 6 '14 at 22:16
  • $\begingroup$ Or else we count count the no four consecutives and four consecutives separately, which is messier. $\endgroup$ – André Nicolas Nov 6 '14 at 22:16

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.