7
$\begingroup$

I am trying to find out a closed-form formula (or a generating function at least) for the number of permutations $\sigma$ that satisfy $$ S = \sum_{i = 1}^{n} i\sigma(i)$$ for a given value of $S$. We can find a maximum and minimum possible sum for a particular $n$ and I have observed that the intermediate sums (between max and min) will always exist for $n>3$. The frequency of the occurrence of each sum is approximately a bell-shaped curve although it is not unimodal.

I have tried various approaches to solve this problem including using a partitions formulation but I have not been able to derive much from it. Any clue as to how to proceed with this problem? Has a similar problem been solved elsewhere?

$\endgroup$
1
  • 4
    $\begingroup$ You can find information about this sequence here: oeis.org/A135298 $\endgroup$ Oct 6, 2015 at 16:15

1 Answer 1

6
$\begingroup$

You can search this statistic (normalized so that the smallest value is 0) in www.FindStat.org and you will find that this is the rank of the permutation inside the lattice of alternating sign matrices. You find further information at http://www.findstat.org/St000055 and the references there:

Sack, J., Úlfarsson, H. Refined inversion statistics on permutations MathSciNet:2880660

Striker, J. A unifying poset perspective on alternating sign matrices, plane partitions, Catalan objects, tournaments, and tableaux MathSciNet:2794039

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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