(N.B.: the combinatorics have not been checked carefully, and I've had a lovely glass of wine or two)
Here's a very nice introduction to the current (and rather lively) world of permutation patterns, and forbidden patterns, in sequences of numbers or letters or DNA base pairs or thingies you can sort.
Salient bit for my purposes at the moment:
Start with an arbitrary sequence of numbers (all different, for the moment). For example look at this random sequence of 7 integers I just made my computer puke out (using Ruby, so that's the notational convention I'll stick with here):
[63, 79, 81, 27, 71, 74, 73]
OK. So let's talk about the six length-3 permutation patterns 123, 132, 213, 231, 312 and 321 (which you will notice are all the permutations of {1,2,3} you're ever gonna see). The Combinatorics folks, they look at those numbers I wrote up above, and they reduce them to relative relations to one another. So for example in the sub-sequence [63, 79, 81] the first is less than the second, and that's less than the third, so we say that matches the permutation pattern 123. On the other hand, [79, 81, 27] goes up first, and then way down farther, so it's a match for 231. And so on.
Now there are five length-3 contiguous sub-sequences in those 7 numbers I wrote there. But these Combinatorics folk, they don't rest easy unless they make it somewhat more complicated than you can hold in your head---it's the large numbers they go for, see?---so they want you to look at all sub-sequences, including those that skip one or more entries in the sequence. So for them [63, 27, 73] is on equal footing with the more obvious [71, 74, 73]; which is fine, even though it makes more work for us. So instead of a mere five sub-sequences, there are (respecting the Combinatorics folks' wishes) all of these:
63, 79, 81
63, 79, 27
63, 79, 71
63, 79, 74
63, 79, 73
63, 81, 27
63, 81, 71
63, 81, 74
63, 81, 73
63, 27, 71
63, 27, 74
63, 27, 73
63, 71, 74
63, 71, 73
63, 74, 73
79, 81, 27
79, 81, 71
79, 81, 74
79, 81, 73
79, 27, 71
79, 27, 74
79, 27, 73
79, 71, 74
79, 71, 73
79, 74, 73
81, 27, 71
81, 27, 74
81, 27, 73
81, 71, 74
81, 71, 73
81, 74, 73
27, 71, 74
27, 71, 73
27, 74, 73
71, 74, 73
I think there are probably 7 choose 3 of those, or 35. And those are examples of these patterns:
63, 79, 81 -> 123
63, 79, 27 -> 231
63, 79, 71 -> 132
63, 79, 74 -> 132
63, 79, 73 -> 132
63, 81, 27 -> 231
63, 81, 71 -> 132
63, 81, 74 -> 132
63, 81, 73 -> 132
63, 27, 71 -> 213
63, 27, 74 -> 213
63, 27, 73 -> 213
63, 71, 74 -> 123
63, 71, 73 -> 123
63, 74, 73 -> 132
79, 81, 27 -> 231
79, 81, 71 -> 231
79, 81, 74 -> 231
79, 81, 73 -> 231
79, 27, 71 -> 312
79, 27, 74 -> 312
79, 27, 73 -> 312
79, 71, 74 -> 312
79, 71, 73 -> 312
79, 74, 73 -> 321
81, 27, 71 -> 312
81, 27, 74 -> 312
81, 27, 73 -> 312
81, 71, 74 -> 312
81, 71, 73 -> 312
81, 74, 73 -> 321
27, 71, 74 -> 123
27, 71, 73 -> 123
27, 74, 73 -> 132
71, 74, 73 -> 132
Got that? Make sense?
As the linked paper above points out, there's a great deal of interest in these patterns, because reasons. Cryptography and number theory and group theory and graphs and all kinds of stuff about bioinformatics and database searching when you get right down to it. But me, I am always the one who wants to ask "why stop there"?
OK so let's say we have a two-dimensional matrix of numbers, all different (for the moment), like one of those fancy ones the physicists are talking about, where we say for now that every entry is a unique real number. So if we label these unique real numbers with their absolute order with respect to one another, in fact what we end up with is a matrix filled in with some permutation.
Here's a 3x4 matrix I had Ruby spit out for me just now:
[[7, 9, 10, 2],
[12, 6, 11, 5],
[3, 4, 1, 8]]
And, generalizing without heed to sanity or health, I want to do the analogous thing the Combinatorics folks did to the sequence, namely look at all the 2x2 submatrices (or minors, as Molly Logue reminded me today) present in that matrix, which are:
7 9
12 6
7 9
3 4
7 10
12 11
7 10
3 1
7 2
12 5
7 2
3 8
9 10
6 11
9 10
4 1
9 2
6 5
9 2
4 8
10 2
11 5
10 2
1 8
12 6
3 4
12 11
3 1
12 5
3 8
6 11
4 1
6 5
4 8
11 5
1 8
Which---hey!--- you can also categorize and/or reduce those into a subset of patterns, in exactly the same way the string/sequence ones work, resulting in these patterns (which I won't bother making into matrices, because it's hard to type them)...
7 9 -> 23/41
12 6
7 9 -> 34/12
3 4
7 10 -> 12/43
12 11
7 10 -> 34/21
3 1
7 2 -> 31/42
12 5
7 2 -> 31/24
3 8
9 10 -> 23/14
6 11
9 10 -> 34/21
4 1
9 2 -> 41/32
6 5
9 2 -> 41/23
4 8
10 2 -> 31/42
11 5
10 2 -> 42/13
1 8
12 6 -> 43/12
3 4
12 11 -> 43/21
3 1
12 5 -> 42/13
3 8
6 11 -> 34/21
4 1
6 5 -> 32/14
4 8
11 5 -> 42/13
1 8
So since those are all over the place, I'm gonna conjecture we have a possibility of pattern-avoiding matrices, in much the same way one can have pattern-avoiding sequences. And for the same reasons, right?
But more importantly (for the moment), notice something interesting I snuck in accidentally when I got lazy and didn't want to represent the patterns as matrices and made them sort of stringlike: if we treat a matrix as filled in with a string, and we permit (as the Combinatorics folks do) skips between the start and end of the string, then what this examination of "permutation patterns" in matrices is doing is in fact adding further constraints on the types (and number) of "skips". While every case in which I reduce a matrix to a submatrix by removing a row and/or a column will produce a sub-sequence of the original matrix's stretched-out contents, not every sub-sequence permitted in the string case is a permitted pattern in the matrix case. For example, [7, 9, 12, 6] is the first submatrix I read off, there; but nowhere did I read off [7, 9, 10, 5].
It strikes me that this matrix example is constrained in an interesting way. For example, a permutation of length 12 has way more sub-sequences (including all skips) of length 4 than just the 18 I found for the matrix as such; I'm going to back-of-the-envelope-plus-wolfram-alpha it and say we've reduced it from about 495 to 18. And if I had set the dimensions of the matrix to 4x3 instead of 3x4, or 2x6 for that matter, I would have had a very different subset of the particular patterns I kept in this case.
This is all in service of a weird-ass genetic programming puzzle. I'll need to think a bit more about it, but it starts with permutations, and it wants to be something interesting about strategies for transforming a sequence from one that fails to avoid forbidden patterns, into a matrix which does avoid those forbidden patterns. Or something like that.
To be honest, it's mathematical recreations at this point, with a lot of implied play-time: What is the probability distribution of patterns like, for uniform random matrices of a given size? What happens when I multiple some matrix, with measured permutation patterns, by some other one with other permutation patterns? How do the distributions change? Can I reach all permutation patterns by simple arithmetic? With only one matrix, and its inverse or transpose, say? And so on.
I haven't tried to hit the literature, and I probably won't. Recreations, for now. Open questions. Play.
Just play, for now.