排序不等式的证明

设命题为,在的序列 上排序不等式成立

成立,则对于的序列
结合的最大排法里,,由于剩下的序列式长度为的序列,则成立
,而是,由于除外的序列,则最优排法
但是这和题设矛盾,因为子序列的长度,若则由的定义引出矛盾
,则此时
所以
Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s