마호니언 삼각형이란? (Mahonian Triangle)

마호니언 숫자의 삼각형(또는 마호니언 삼각형)의 수들은

∏(𝑖=0..𝑛−1)(1+𝑥+...+𝑥𝑖)를 전개했을 때의 각 계수이다.

코시 곱에 의해서 1부터 n까지의 순열에서 K번의 역전이 일어난 순열의 개수임이 증명된다.

k는 해당하는 순열을 increasing order로 만들기 위한 버블정렬의 스왑 횟수와도 같다.

삼각형은 좌우대칭의 형태를 가진다.

순열의 무질서도와 정규 분포에도 관련이 있다.

 

공식

T(n, k)를 1부터 n까지의 순열에서 K번의 역전이 일어난 순열의 개수라고 하였을 때, 다음이 성립한다.

T(1, 0) = 1,

T(n, k) = 0 for n < 0, k < 0 or k > n*(n-1)/2.

T(n, k) = Sum_{j=0..n-1} T(n-1, k-j)

 

정리하면, 

T(n, k) = T(n, k-1) + T(n-1, k) - T(n-1, k-n).

유도는 아래에 있다. 부분합이라고 생각하면 편하다.

 

 

n=3의 예시

x⁰(x⁰+x¹)(x⁰+x¹+x²)

= 1(1+x¹)(1+x¹+x²)

= x³ + 2x² + 2x¹ + 1

 

1 2 2 1

 

실제 삼각형의 전개는 아래와 같다. n이 행, k가 열이다.

n\k| 0 1 2 3 4 5 6 7 8 9 10

---+--------------------------------------------------------------

1 | 1;

2 | 1, 1;

3 | 1, 2, 2, 1;

4 | 1, 3, 5, 6, 5, 3, 1;

5 | 1, 4, 9, 15, 20, 22, 20, 15, 9, 4, 1;

6 | 1, 5, 14, 29, 49, 71, 90, 101, 101, 90, 71, ...

7 | 1, 6, 20, 49, 98, 169, 259, 359, 455, 531, 573, ...

8 | 1, 7, 27, 76, 174, 343, 602, 961, 1415, 1940, 2493, ...

9 | 1, 8, 35, 111, 285, 628, 1230, 2191, 3606, 5545, 8031, ...

10 | 1, 9, 44, 155, 440, 1068, 2298, 4489, 8095, 13640, 21670, ...

 

 

참조

https://oeis.org/A008302

https://math.stackexchange.com/questions/2008758/showing-mahonian-triangle-numbers-related-to-inversion-probability

https://stackoverflow.com/questions/19372991/number-of-n-element-permutations-with-exactly-k-inversions?newreg=f7951d49580647d6850fa587c57a8a97