Number of permutations inducing same order on consecutive elements

Question

Let $n$ be a positive integer. Let $S_{n+1}$ be the set of permutations of $1,\dots, n, n+1$. Let $B_n$ be the set of binary sequences of length $n$.

There is a surjection $f:S_{n+1}\to B_n$ where the $i$-th digit of $f(\pi)$ is 1 if $\pi(i+1)>\pi(i)$ and 0 otherwise.

For $n>1$ we have $(n+1)!>2^n$ so $f$ cannot be injective.

Is there a simple formula for the cardinality of the inverse image of a sequence $b\in B_n$? Or an algorithm better than ranging through all permutations?

For $n=5$ the possible cardinalities are 1, 5, 10, 14, 19, 26, 35, 40, 61.

For $n=6$ we get 1, 6, 15, 20, 29, 34, 50, 55, 64, 71, 78, 90, 99, 111, 132, 155, 169, 181, 272.

Answer 1

(please excuse that this contains product placements)

For this question you can use https://www.findstat.org to get you started. You can regard the cardinality of the preimage of $b\in B_n$ as a combinatorial statistic on binary words. Then compute the first few statistic values (more easily using a computer) and plug them into findstat. For example, using sage you can do this as follows:

sage: statistic = lambda w: sum(1 for pi in Permutations(len(w)+1) if all((pi[i+1] > pi[i]) == (w[i] == 1) for i in range(len(pi)-1)))
sage: q = findstat([(w, stat(w)) for n in range(1, 6) for w in Words([0,1], length=n)]); q
0: St000529 (quality [100, 100])
1: St000277oMp00178 (quality [100, 100])
2: St001595oMp00180oMp00178 (quality [100, 100])

You can then look at the hits using

sage: q[1].info()

or

sage: q[1].browse()

Of course, this only works because you are doubly lucky: the set of binary words is a collection known to findstat, and the statistic is actually in the database.