4

Question:
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$$

Problem:
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.

Community
  • 1
JoeyAndres
  • 1,269

1 Answers1

4

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

André Nicolas
  • 507,029
  • Right! Thanks for the help again. – JoeyAndres Jul 20 '14 at 13:32
  • You are welcome. In "consecutives" problems, such as at least four consecutive heads, the same sort of issue comes up. – André Nicolas Jul 20 '14 at 13:35
  • @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? – Dunka Nov 06 '14 at 21:37
  • 1
    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) – André Nicolas Nov 06 '14 at 22:16
  • Or else we count count the no four consecutives and four consecutives separately, which is messier. – André Nicolas Nov 06 '14 at 22:16