# Sequence that sums up to the number of permutations avoiding the pattern $1-23-4$

Let $$a(n)$$ be A113227, i.e., the number of permutations on $$[n]\equiv \{1, \ldots, n\}$$ avoiding the pattern $$1-23-4$$.

The sequence begins with $$1, 1, 2, 6, 23, 105, 549, 3207, 20577, 143239, 1071704, 8555388, 72442465, 647479819$$ $$a(n)$$ is given by the following recurrence relation, due to David Callan $$a(n)=\sum\limits_{k=1}^{n}u(n,k),$$ where $$u(n,k)=u(n-1,k-1)+k\sum\limits_{j=k}^{n-1}u(n-1,j), \qquad u(n,0)=[n=0].$$ Here square brackets denote Iverson brackets.

Let $$b(n)$$ be a sequence of the positive integers such that $$b(2^m(2n+1))=\sum\limits_{k=0}^{m}(k+1)b(2^k n), \qquad b(0)=1 .$$

The sequence begins with $$1, 1, 3, 1, 6, 3, 7, 1, 10, 6, 15, 3, 25, 7, 15, 1, 15, 10, 26, 6, 45, 15, 33, 3, 65$$

Let $$s(n)$$ be a sequence of the positive integers such that $$s(n)=\sum\limits_{k=0}^{2^n-1}b(k)$$

I conjecture that $$s(n)=a(n+1)$$

Is there a way to prove it?

The following is not a complete answer, but too long for a comment.

It looks like FindStat provides an interpretation of the numbers $$b(k)$$ as a statistic on the set of $$1-23-4$$ avoiding permutations. For simplicity, let me use the Sagemath interface. First, let occurrences be the number of occurrences of the pattern and let b be your function.

def occurrences(pi):
n = len(pi)
return sum(1 for k in range(n) for j in range(k-1) for i in range(j)
if pi[i] < pi[j] < pi[j+1] < pi[k])

@cached_function
def b(N):
if not N:
return 1
m = valuation(N, 2)
n = (N // 2^m - 1) / 2
return sum((k+1)*b(2^k*n) for k in range(m+1))


Next, we interpret the numbers $$b(0),\dots,b(2^{n-1})$$ as the distribution of a statistic on the $$1-23-4$$ avoiding permutations.

sage: avd = lambda n: [pi for pi in Permutations(n) if not occurrences(pi)]
sage: dst = lambda n: [i for i in range(2^(n-1)) for _ in range(b(i))]
sage: avd(3)
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
sage: dst(3)
[0, 1, 2, 2, 2, 3]


Finally, we check whether such a statistic is known:

sage: qu = findstat([(avd(n), dst(n)) for n in range(1, 8)], depth=4)
sage: qu[:2]
0: St000289oMp00131oMp00087oMp00235oMp00064 (quality [100, 100])
1: St001879oMp00065oMp00175oMp00081oMp00070 (quality [6, 22])


It is quite rare that a distribution search allowing the composition of 4 maps has such a high confidence:

sage: qu[0].info()
after applying
Mp00064: reverse: Permutations -> Permutations
Mp00235: descent views to invisible inversion bottoms: Permutations -> Permutations
Mp00087: inverse first fundamental transformation: Permutations -> Permutations
Mp00131: descent bottoms: Permutations -> Binary words
to the objects (see .compound_map() for details)

St000289: The decimal representation of a binary word.

among the values you sent, 100 percent are actually in the database,
among the distinct values you sent, 100 percent are actually in the database


Since this is such a rare event, let us double check (please execute the following only if you trust FindStat - foreign code will be executed on your machine)!

sage: f = findstat(); f._allow_execution = True
sage: n=9; sorted([m(pi) for pi in avd(n)]) == dst(n)
True


It remains, of course, to prove these statements. You can look at the full description of the result here.

• Note that the statistic is defined for all permutations, even those that do not avoid $1-23-4$. I think that this makes it even more likely that the map simplifies, I did not check. Commented May 17, 2023 at 14:52
• Indeed, the map can be simplified as follows: it is the binary word corresponding to the minimal elements of the increasing runs of the permutation which are not right-to-left maxima. This is immediate from the description of findstat.org/MapsDatabase/Mp00235 Commented May 17, 2023 at 16:22
• Yes, the code above works, there is no more input required. I do set the maximal number of transformations, by default it is 2, to save bandwidth. The maximal possible value is 9, but this is rarely useful. Commented May 17, 2023 at 16:42
• Dyck paths are actually the collection with the greatest number of statistics in the database. Do you want to try your luck? You only have to adapt the definition of avd and dst above. Commented May 17, 2023 at 16:59
• I just see that A258173 does not really define a subset of Dyck paths. So it is less clear how to turn b into a distribution on Dyck paths. Commented May 17, 2023 at 17:05