The rise and/or fall

The latest Matt Parker’s Maths Puzzle is in fact by Zoe Griffiths and asks about increasing or decreasing sequences of length m within permutations of n cards (or numbers). So for example, with n=4, the permutation

1 3 2 4

contains the two increasing sequences of length m=3:

1 3 4
1 2 4

as well as two length 3 sequences that do not increase or decrease:

1 3 2
3 2 4

and no length 3 sequences that decrease. For n=4, how many of the 24 permutations contain no sequences of length 3 that decrease or increase? (That’s an awkward phrase, so from here on let’s call a sequence that either decreases or increases a run, and one of length 3 a 3-run. So we’re asking how many permutations contain no 3-runs. Answer below:)

The answer is 4: (2, 1, 4, 3), (3, 1, 4, 2), (2, 4, 1, 3), and (3, 4, 1, 2).

Let’s look at the first of these. You can look at all the subsets of length 3 and verify none is a 3-run, but you can also do this: Notice this permutation can be grouped into two pairs, each consisting of consecutive numbers in descending order, and with the second pair using larger numbers than the first:

((2, 1), (4, 3))

To form an increasing run from this permutation you would need to use no more than one number from each group. But there are only two groups. So you can’t make an increasing 3-run.

For a decreasing run, you can use one of the groups, but neither group has larger numbers before it or smaller numbers after, so you can only use numbers from one group, and each group has only two numbers. So you can’t make a decreasing 3-run.

Therefore this permutation has no 3-runs.

What about 5 numbers? A permutation with decreasing groups like the above would have to be something like ((1), (3, 2), (5, 4)) or ((3, 2, 1), (5, 4)): There would have to be either more than two groups, or more than two members in at least one group. Either way there would be a 3-run. So we can’t use this argument to rule out the possibility that every permutation of 5 numbers contains a 3-run.

By similar reasoning, the permutation of 9 numbers (3, 2, 1, 6, 5, 4, 9, 8, 7) has no 4-runs. It can be grouped as

((3, 2, 1), (6, 5, 4), (9, 8, 7))

and as before, an increasing run can use only one number from each group, and there are only three groups; a decreasing run can use only numbers from one group, and each group has only three numbers, so no 4-runs are possible. But again, we can’t use the same trick to demonstrate a 4-run-less permutation of 10 numbers.

Similarly, for 16 numbers, the permutation (4, 3, 2, 1, 8, 7, 6, 5, 12, 11, 10, 9, 16, 15, 14, 13) contains no 5-runs, and so on.

What this argument tells you is:

For all m\ge 2, there exist permutations of up to n = (m-1)^2 numbers with no m-runs

What it does not tell you is:

For all m\ge 2, does every permutation of more than n = (m-1)^2 numbers have at least one m-run?

But for k=3, it’s easy to prove

For n\ge5, every permutation has at least one 3-run

PROOF: Start with a 3-run-less permutation of 4 numbers, (a, b, c, d), then we’ll see a fifth number, e, cannot be added without creating a 3-run. There are two cases: b<a and b>a. In the first case, to avoid a 3-run, we must have c > b. Likewise d < c. Also, d > b to avoid a 3-run of (a, b, d). Now, where do we put e?

If e < d then (c, d, e) is a decreasing 3-run. But if e > d, then (b, d, e) is an increasing 3-run. A similar argument holds in the second case, b > a, so a 3-run can’t be avoided.

For larger n and m, the analysis is harder. I wrote a Python script to check combinations of m and n and print the number of permutations with no m-runs:


from itertools import permutations, combinations
from sys import argv

def isascdesc (a):
    if len(a) < 3:
        return True
    if a[0] < a[1]:
        for i in range (2, len(a)):
            if a[i-1] > a[i]:
                return False
        for i in range (2, len(a)):
            if a[i-1] < a[i]:
                return False
    return True

n = int(argv[1])
m = int(argv[2])

if m > n:
    print "Nah"

nallfalse = 0
for aa in permutations(range(1,n+1)):
    allfalse = True
    for b in combinations(aa, m):
        if isascdesc (b):
            allfalse = False
    if allfalse:
        nallfalse += 1
print nallfalse

And here are some results:

n Number of permutations containing no…
1-runs 2-runs 3-runs 4-runs 5-runs 6-runs 7-runs 8-runs 9-runs 10-runs
3 0 0 4
4 0 0 4 22
5 0 0 0 86 118
6 0 0 0 306 668 718
7 0 0 0 882 4124 4966 5038
8 0 0 0 1764 26328 38538 40220 40318
9 0 0 0 1764 165636 326794 359724 362750 362878
10 0 0 0 0 985032 2954380 3547032 3623594 3628636 3628798

For instance, every permutation of (1, 2, 3, 4, 5, 6) contains 1-runs and 2-runs (obviously) and 3-runs (we proved it for n=5, and of course it’s true for larger n too), but there are 306 permutations containing no 4-runs. For n=10 there are no permutations with no 4-runs but there are nearly a million with no 5-runs.

But the rapidly increasing combinatorics means this script can’t be run in any reasonable amount of time for much more than 10 numbers. Investigating permutations of 17 numbers would be out of the question. (I worked up a more complicated version that runs faster, but not enough faster to help much.)

We proved every permutation of 5 numbers contains a 3-run. Is there a similar proof for 10 numbers and 4-runs? There’s no proof I can see that’s anywhere near as simple. There are only 4 3-run-less permutations of 4 numbers, and they’re all roughly z-shaped, with a direction change at every number, so it’s easy to consider how to add one more number and to show it always leads to a 3-run. But there are 1764 4-run-less permutations of 9 numbers, which many different shapes, so that approach either wouldn’t work or would be insanely complicated.

We could try looking for fairly general properties of an ostensible 4-run-less permutation for n=10 and show they lead to a contradiction. A few such properties are fairly easy to figure out: For instance, 1 and 10 can be separated by no more than 3 intervening numbers. Also, by the proof above, the first five numbers must have a 3-run: In the case where it’s an increasing 3-run, it’s easy to see 10 must be in the first five numbers, the last five numbers must also have an increasing 3-run, and 1 must be in the last five numbers. In fact 10 must be in one of positions 2 through 5, and 1 must be in one of positions 6 through 9. Similarly, if the first five numbers contain a decreasing 3-run, so do the last five numbers, and 1 must be in one of positions 2 through 5, while 10 must be in one of positions 6 through 9.

That seems like a promising start, but beyond that it seems you have to consider a lot of different cases rather than getting more such general properties. Nor is it clear a proof along these lines would readily generalize to larger sets and larger runs (do all permutations of 17 numbers contain a 5-run?), which is what you’d really want.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s