넘치게 채우기

https://leetcode.com/problems/k-inverse-pairs-array/description/?envType=daily-question&envId=2024-01-27 LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com LeetCode - K Inverse Pairs Array 문제 유형 : 순열, 조합, 수학, 마호니언 삼각형, 다이나믹 프로..

마호니언 숫자의 삼각형(또는 마호니언 삼각형)의 수들은 ∏(𝑖=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 n*(n-1)/2. T(n, k) = Sum_{j=0..n-1} T(n-1, k-j) 정리하면, T(n, k)..