1
$\begingroup$

Problem

A permutation inversion $b_1 b_2 \ldots b_n$ of the permutation $a_1 a_2 \ldots a_n$ is obtained by letting $b_j$ be the number of elements to the right of $j$ that are less than $j$, i.e. $b_j$ is the number of inversions whose first component is $j$.

For example, the permutation $$591826473$$ has the permutation inversion $$000142157.$$

How to count the number of permutation of length $n$ that every entry in its permutation inversion appears at most twice?

For example, the permutation inversion of $591826473$ is $000142157$, and "$0$" appears $3$ times, so this doesn't count. However, the permutation inversion of $781359642$ is $001122663$, which is satisfied.

$\endgroup$
1
$\begingroup$

Inversion sequence is the standard terminology for $b_1\dots b_n$ as defined in your question. The answer to your question is given in a paper by Martinez and Savage, see section 3.1. The number of such inversion sequences is the Euler number, A000111.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.