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.

  • 1
    My guess is number of ways of selecting 4 numbers (order matters) such that you don't have 3 consecutive integers appearing in order. Example: 3,4,5,77 is not to be counted. If you have a number as an answer, perhaps we can confirm.2011-06-02
  • 1
    It is a little ambiguous; I believe you want to count lists of $4$ distinct elements of $\{1,2,\ldots,100\}$ that contain $3$ consecutive integers in the correct order. So for example, $(17,18,19,72)$ would be counted, and $(6,4,5,99)$ would not be. What is not clear to me is whether $(17,18,72,19)$ should be counted.2011-06-02
  • 0
    Is it "exactly $3$" or "at least $3$"? So for example does the quadruple $(11, 12, 13, 14)$ qualify? Also, is something like $(7,8, 44, 9)$ to be counted? As soon as the question is made clear, answers are likely to come quickly.2011-06-02
  • 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: I copied the question directly from the source, and I don't know whether it asks for exact 3 or at least 3. Anyway, the answer by the sourse is 18,915. Does this number look right to you?2011-06-02
  • 0
    @Robert: Simple enough to solve both problems; figure out the ones that have exactly three, figure out the ones that have all four. The real issue is whether the three integers must be consecutive *in the permutation* or not; i.e., if 1,9,2,3 "counts" or not.2011-06-02
  • 0
    @Arturo: The book I am reading had not discussed inclusion-exclusion where the question appeared. So your suggestion using this method is probably not applicable here.2011-06-02
  • 1
    @Robert: All you have to do is account for overcounting: if you first count how many *start* with three sequential numbers; then you count how many *end* with three sequential numbers, then you've counted those that both start *and* end with three sequential number (i.e., those in which all four numbers are in sequence) twice. So just count how many of those there are, and subtract from the total you get by adding the first two computations. It's inclusion-exclusion but without invoking it explicitly.2011-06-02
  • 0
    @Arturo: If you are able to reach the answer, then probably your interpretation is correct. I will work it out tonght myself but have to run now.2011-06-02
  • 1
    @Robert: Yes, I got exactly what you give as the answer by doing exactly what I described: I counted how many four tuples have at least the first three numbers in order; then I counted how many have at least the last three in order and added them to my previous result; and then I counted how many tuples had all four entries in order and subtracted it from my running total. I got exactly 18,915.2011-06-02
  • 0
    To all: Last night, I used Arturo's earlier "Added" principle to work out the details and was able to get 18,915.2011-06-03
  • 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