In computer science and discrete mathematics, an [inversion](https://en.wikipedia.org/wiki/Inversion_%28discrete_mathematics%29) is a pair of places in a sequence where the elements in these places are out of their natural order. So, if we use ascending order for a group of numbers, then an inversion is when larger numbers appear before lower number in a sequence.

Check out this example sequence: ```(1, 2, 5, 3, 4, 7, 6)``` and we can see here three inversions
```5``` and ```3```; ```5``` and ```4```; ```7``` and ```6```.

You are given a sequence of numbers and you should count the number of inversions in this sequence.

```Input```: A sequence as a tuple of integers.

```Output```: The inversion number as an integer.

Example:
```python
  count_inversion((1, 2, 5, 3, 4, 7, 6)) == 3
  count_inversion((0, 1, 2, 3)) == 0
```

Difficulty: introductory

Starter code:

def count_inversion(sequence):
	

Solutions:
def count_inversion(nums):
    return sum(a > b for i, a in enumerate(nums) for b in nums[i + 1:])


def count_inversion(s):
    return sum(s[i] > s[j]
               for i in range(len(s) - 1)
               for j in range(i + 1, len(s)))

def count_inversion(sequence):
    def rec(arr):
        if len(arr) <= 1: return arr, 0
        a, ai = rec(arr[:len(arr)//2])
        b, bi = rec(arr[len(arr)//2:])
        res, i, j, count = [], 0, 0, ai + bi
        while i < len(a) and j < len(b):
            if a[i] <= b[j]:
                res.append(a[i])
                i += 1
            else:
                res.append(b[j])
                j += 1
                count += len(a) - i
        return res + a[i:] + b[j:], count
    return rec(list(sequence))[1]

from itertools import combinations

def count_inversion(lst):
    return sum(a>b for a,b in combinations(lst,2))

def count_inversion(sequence):
    return sum(a > b for i, a in enumerate(sequence[:-1]) for b in sequence[i+1:])

def merge(a, left_index, mid, right_index, aux):
    i, j = left_index, mid + 1
    inversions = 0

    for k in range(left_index, right_index + 1):
        aux[k] = a[k]

    for k in range(left_index, right_index + 1):
        if i > mid:
            a[k] = aux[j]
            j += 1
        elif j > right_index:
            a[k] = aux[i]
            i += 1
        elif aux[i] <= aux[j]:
            a[k] = aux[i]
            i += 1
        elif aux[j] < aux[i]:
            a[k] = aux[j]
            j += 1

            inversions += mid - i + 1
    return inversions

def count(a, left_index, right_index, aux):
    if right_index <= left_index:
        return 0
    mid = left_index + (right_index - left_index) // 2
    left_inversions = count(a, left_index, mid, aux)
    right_inversions = count(a, mid + 1, right_index, aux)
    return left_inversions + right_inversions + merge(a, left_index, mid, right_index, aux)

def count_inversion(sequence):
    if len(sequence) < 2:
        return 0
    aux = [None for _ in range(len(sequence))]
    sequence_list = list(sequence)
    return count(sequence_list, 0, len(sequence) - 1, aux)

from collections import deque


def count_inversion(nums):
    forward_nums = deque(nums)
    result = 0
    for a in nums:
        forward_nums.popleft()
        for b in forward_nums:
            if a > b:
                result += 1
    return result


def count_inversion(sequence):
    """
        Count inversions in a sequence of numbers
    """
    count = 0
    for i, x in enumerate(sequence):
        for y in sequence[i+1:]:
            if x > y: count += 1
    return count


count_inversion = lambda sequence: sum([sum([1 if sequence[x] > sequence[x + y] else 0 for y in range(1, len(sequence) - x)]) for x in range(len(sequence))])

def count_inversion(sequence):
    """
        Count inversions in a sequence of numbers
    """
    return sum(n > m for i, n in enumerate(sequence) for m in sequence[i:])