Skip to content
Get started

Exactly three inversions

MediumCombinatorics5 min

An inversion in a list of distinct numbers is a pair of positions i<ji < j whose entries are out of order (ai>aja_i > a_j). How many orderings of {1,2,3,4,5,6}\{1, 2, 3, 4, 5, 6\} have exactly 33 inversions?

Show hints (3)+
  1. Insert the values 1,2,…,61, 2, \dots, 6 one by one. How many inversions can inserting vv create?
  2. Each permutation is a list (t2,…,t6)(t_2, \dots, t_6) with 0≤tv≤v−10 \le t_v \le v-1 and inversion count ∑tv\sum t_v.
  3. Stars and bars, then subtract the cases that break the caps t2≤1t_2 \le 1, t3≤2t_3 \le 2.

Answer

Reveal answer →

29

Create a free account to see the full worked solution and track your progress.

Interview format: Prop Trading, Systematic & Data-Driven Trading

Related questions