RFE Dec 2025: Mesh patterns avoiding 321

[Sean A. Irvine]

Hi,

This month I would like to draw attention to what is currently the largest group of OEIS sequences with identical names.

Provide more terms, distinct names, formulas, and/or programs for the 31 sequences based on Murray Tannock's MSc Thesis (available via the Links in the corresponding sequences). These sequences appear (along with many others) in Appendix B, starting on p. 47 of the thesis.

A289452, A289453, A289587, A289588, A289589, A289590, A289591, A289592, A289593, A289594, A289595, A289596, A289597, A289598, A289599, A289600, A289601, A289602, A289603, A289604, A289605, A289606, A289607, A289608, A289609, A289610, A289611, A289612, A289613, A289614, A289654.

The RFE from November also remains open, although M. H. Hasler (and others) have made some improvements to those sequences.

I track these requests for enhancement here:

https://oeis.org/wiki/User:Sean_A._Irvine/Requests_for_Enhancements#Requests_for_Enhancements

Sean.

[Christian Sievers]

Hello,

the name of these sequences should be something like

Number of permutations of length n that avoid the (classical) pattern 321
   (or 231 in the case of the sequences from appendix B.1)
and the mesh pattern (tau,R).
   (where tau = 12 or 21 and R is a subset of {0,1,2}^2 )

- except that often there is more than one mesh pattern that gives
the same terms. Worse, I'm not sure if the mesh patterns that give
the same first eleven terms are guaranteed to give the same full
sequence. Section 3.2 has subsections that begin with
"The following patterns are experimentally Wilf-equivalent up to
 length 10 in Av(231) ..."
and then prove that they are indeed equivalent.
But that is only for the classical pattern 231, and indeed the
abstract only claims to "completely Wilf-classify mesh patterns
of length 2 when avoiding the classical pattern 231."

Except for the sequence 1,1,1,0,0,0,0,0,0,0,0, all sequences in
appendix B that have no "Related OEIS entry" in the table
(these are the new ones that we're talking about) correspond to
at most 8 "Number of patterns in class", as the column heading of
the table says. This is the number of mesh patterns that give the
particular sequence. In each table (for 231 and 321) their sum is
1024, corresponding to 2 options for tau and 2^9 options for R.

The offset of the sequences is given as 1 now, this should be 0.
The numbers correspond to lengths n=0..10, not n=1..11.

In Appendix C, the thesis explains that the python code used for it
can be found at github. The repository is still available and also
contains the TeX code of the thesis. I used it to sum the numbers
of patterns given in the tables.

I used my own code to check my understanding of the sequences.
I used clingo, which has recently become my "secret weapon"
which I used to compute a lot of my latest OEIS contributions,
often with embarrassingly trivial code.
(In Debian, you need the package gringo and its dependency clasp
 to use clingo.)

I put the code at the end of this message.
It should be able to compute all the sequences of Appendix B.
You give it n, the classical pattern pi = 321 or 231, tau = 12 or 21,
and R encoded by a variable rc that has bit 3*I+J set to 1 if
(I,J) is in R, via a slightly clumsy option mechanism using
"-c <var>=<val>".

For example, section 3.2.1 gives six equivalent mesh patterns.
As the whole section 3.2, it uses the dominating pattern pi=231.
The position of the dots in the first mesh pattern show that it
has tau=12, and the set R has all possible elements except (1,1)
and is therefore encoded by rc=511-16.
If the program is in a file named mesh.lp, you can call clingo
like this to compute the term for n=10:
   clingo -c n=10 -c pi=231 -c tau=12 -c rc=511-16 0 mesh.lp

You get a list of all the permutations that avoid pi and (tau,R)
and a summary telling that there were 15366 models, which is the
last number of the sequence at the end of the subsection.

The 0 tells clingo to enumerate all solutions, and if you don't
want to see them all, you can suppress the output of all answers
with the option -q.
For the third pattern in the same subsection, you would use tau=21
and rc=511-64.

Now one could systematically try all mesh pattern, or just play around.
Note that having the value for n=10 almost always determines the sequence.
Just playing around, it's not so easy to find a sequence that wasn't
already in the OEIS when the thesis was written.
But here is one I found: computing
   clingo -c n=10 -c pi=321 -c tau=12 -c rc=234 -q 0 mesh.lp
gives 3740 models. Searching this number in  the table in

B.2 gives one sequence (you can check smaller values) that

did not have a related OEIS entry. It is now A289587.

We can easily compute more terms:

a(11)=11602, a(12)=36357, a(13)=115049,...
When the computations become too slow, there are still options for
parallelization and solver tuning.

So it should be possible to find mesh patterns that give all these
sequences. But with so many sequences that already were in the OEIS,
one may assume that the remainig ones also have some independent
relevance.


All the best
Christian

------------------------------------------------------------

% p describes a permutation
{p(X,1..n)} = 1 :- X=1..n.
{p(1..n,Y)} = 1 :- Y=1..n.

% ... that avoids the classical pattern pi
:- pi=321, p(X1,Y1), p(X2,Y2), p(X3,Y3), X1<X2, X2<X3, Y3<Y2, Y2<Y1.
:- pi=231, p(X1,Y1), p(X2,Y2), p(X3,Y3), X1<X2, X2<X3, Y3<Y1, Y1<Y2.

% ... and also avoids the mesh pattern (tau,R)
% where R is given by the predicate r with
% r(I,J) <=> (I,J) \in R
:- p(X1,Y1), p(X2,Y2), X1<X2,
     Y1<Y2 : tau=12;
     Y2<Y1 : tau=21;
     Z1 = #min{Z : Z=(Y1;Y2)},
     Z2 = #max{Z : Z=(Y1;Y2)},
     not r(I,J) : p(X,Y), o(X1,X2,X,I), o(Z1,Z2,Y,J).

% get the predicate r from its encoding rc via
% r(I,J) <=> bit 3*I+J in rc is 1
r(I,J) :- I=0..2, J=0..2, 2**(3*I+J)&rc>0.

% o(A,B,X,O) if 1 <= A < B <= n, X is a different element in 1..n, and
% o=0, 1 or 2 when X comes before, between, or after A and B, respectively.
o(A,B,X,0) :- X=1..n, A=X+1..n, B=A+1..n.
o(A,B,X,1) :- A=1..n, X=A+1..n, B=X+1..n.
o(A,B,X,2) :- A=1..n, B=A+1..n, X=B+1..n.

#show p/2.

------------------------------------------------------------