A Simple Method for Calculations of the Number of Inversions in Permutation

Abstract

The aim of this paper is to show the recurrence method for obtaining the number of inversions In(k) in input sets with different sizes n, when the information about In-1(k) is given. The proposed method is based on a simple observation that the use of recursive approach gives an elegant way for obtaining those numbers in contradiction to the so far existing approach based on binomial coefficients and pentagonal numbers. The complexity of this method is O(n3). The results of this proposal can be used for interesting exercises in education of maths and also for problem of inversions description in sorting algorithms.