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 within permutations of cards (or numbers). So for example, with , the permutation

1 3 2 4

contains the two increasing sequences of length :

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 , 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 , there exist permutations of up to numbers with no m-runs

What it does not tell you is:

For all , does every permutation of more than numbers have at least one m-run?

But for , it’s easy to prove

For , 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: and . In the first case, to avoid a 3-run, we must have . Likewise . Also, to avoid a 3-run of (a, b, d). Now, where do we put e?

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

---

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

#!/usr/bin/python

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
    else:
        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"
    exit()

nallfalse = 0
for aa in permutations(range(1,n+1)):
    allfalse = True
    for b in combinations(aa, m):
        if isascdesc (b):
            allfalse = False
            break
    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 , and of course it’s true for larger too), but there are 306 permutations containing no 4-runs. For 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 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.