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

Question

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?

Answer 1

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)

your input matches
    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.