论坛 › 趣题妙解 › 求逆序数为m的排列总数

fungarwai 发表于 2015-1-19 14:40:47

求逆序数为m的排列总数

N(1)=0
N(12)=0,N(21)=1
N(123)=0,N(132)=1,N(213)=1,N(231)=2,N(312)=2,N(321)=3
...
1
1,1
1,2,2,1
1,3,5,6,5,3,1

$1$
$1+x$
$(1+x)(1+x+x^2)$
$(1+x)(1+x+x^2)(1+x+x^2+x^3)$

BeerRabbit 发表于 2015-1-19 17:00:27

首先要确定用于排列的数字的个数吧？
比如，1~n的排列中，逆序数为m的排列总数为F(n,m)=？
显然，m<=C(n,2)

fungarwai 发表于 2015-1-19 17:59:03

设x为1,2,...,n的排列，x的逆序数为N(x)
$N(x,n+1)=N(x)$
$N(n+1,x)=n+N(x)$
把x分成$x_1,x_2$，$x_2$有k个元素
$N(x_1,n+1,x_2)=k+N(x)$
\(\displaystyle \sum_{m=0}^{C_{n+1}^2} a(n+1,m) x^m=(\sum_{m=0}^n x^m)(\sum_{m=0}^{C_n^2} a(n,m) x^m)\)

查看完整版本: 求逆序数为m的排列总数