2
$\begingroup$

What is this question asking for?

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

[My note: 4-permutation = $P(n,4) = n\times(n-1)\times(n-2)\times(n-3)$]

The answer by the source is 18,915.

  • 0
    @Jonas: I would say the latter is not to be counted.2011-06-02

1 Answers 1

4

If by "$4$-permutations" you mean a selection of $4$ elements in order (which your note suggests), then it is asking the following:

First, suppose you want to figure out in how many ways you can pick four positive integers, not exceeding $100$, in a way where the order matters. Then you have 100 choices for the first integer; 99 for the second; 98 for the third, and 97 for the fourth; i.e., $P(100,4)$.

In some of these selections, there will be absolutely no relation between the chosen integer. You can pick $17$, then $84$, then $53$, and finally $8$.

But some of the selections have three consecutive integers in order: for example, you can pick $11$, $12$, $13$, and $85$, where the first three are in order; or $7$, $71$, $72$, $73$, where the last three are in order.

The question is asking you to count only those selections of 4 positive integers between 1 and 100 in which (at least) three of the selected integers are in their usual order, $k$, $k+1$, and $k+2$. They can be the first three, or the last three that you pick.

My suggestion: Count how many have the first three in order; then count how many have the last three in order; then use inclusion-exclusion to account for possible overcounting when you have all four numbers in their usual order.

Added. Given the answer you have, I am guessing that:

  1. You want at least 3 in order; if all four are in order, that counts too.
  2. They must appear consecutively and in order, so that 8,9,10,47 counts, but 8,47,9,10 does not (even though it contains three consecutive integers, listed in the correct order, namely 8,9,10).

At least, by counting those, I get the answer you were given.

  • 0
    To all: Last night, I used Arturo's earlier "Added" principle to work out the details and was able to get the desired result. Each of (1,2,3,X) till (98,99,100,X) has 97 possibilities that sum up to 97*98=9506. Then (X,1,2,3) has 97. Excluding double count in light of those in the first category, each of (X,2,3,4) till (X,98,99,100) has 96 and, in turn, the sum is 96*97=9312. Finally, the grand total is 9506+97+9312=18915. Now I understand what the question was asking for. Thank you everyone who even cared to pay attention to this small non-issue.2011-06-03