Permutation Counting (UVa Live Archive Asia - 2010 Harbin)

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=387&page=show_problem&problem=3093

問題

順列Pでai>iとなっている物の数をE-valueと呼ぶ。長さNの順列でE-valueがkの物の数を求めよ。
1<=N<=1000
0<=k<=N

解法

Eulerian Numberに従って漸化式を計算すれば良い。この漸化式になる理由は、長さn-1の順列Pの一番後ろにnを追加した後、PのE-valueがm-1の場合はai>iとなっていないものとnを交換し、mの場合はai>iとなっているものと交換すれば良いという意味。