证明：n个整数的任何排列都饱含长度不小于根号n的特调子排列？
Richard Xu 4小时前 44如题
0 赞 0 踩
其他回答
Erdos-Szekeres定理
http://www.math.ucsd.edu/~jverstra/erdos-szekeres.pdf
http://www.math.ucsd.edu/~jverstra/erdos-szekeres.pdf
热心网民 4小时前 0条评论
0 赞 0 踩
只需证明长为n^2+1的数列必有长为n+1的单调子序列
在该数列上定义偏序关系：且
不失一般性，假设该数列中没有长为n+1的单调不降子序列
则上述偏序关系中链的长度最长为n
由Dilworth定理的对偶定理，该数列可以划分为n个反链
由抽屉原理，至少有一个反链的大小为n+1
反链中所包含的元素不能在上述偏序关系中比较大小，意味着若反链中某两个元素满足则必有，则该长为n+1的反链构成了长为n+1的单调降子序列。
Q.E.D.
在该数列上定义偏序关系：且
不失一般性，假设该数列中没有长为n+1的单调不降子序列
则上述偏序关系中链的长度最长为n
由Dilworth定理的对偶定理，该数列可以划分为n个反链
由抽屉原理，至少有一个反链的大小为n+1
反链中所包含的元素不能在上述偏序关系中比较大小，意味着若反链中某两个元素满足则必有，则该长为n+1的反链构成了长为n+1的单调降子序列。
Q.E.D.
Richard Xu 4小时前 0条评论
0 赞 0 踩
登录后可回答 提交回答
关键词 :
- 上一个：有没有跟西游记降魔篇类似之尴尬的电影？
- 下一个：假若大家都成自己所属生肖之动物，世界会是啊样子？
相关资讯
- 谋女郎章子怡素颜助阵张艺谋电影 夸赞其很浪漫
- 伊能静儿子脚踩20cm高跟鞋 与美女同框大秀长腿
- 霍思燕教育孩子好严厉 嗯哼大哭满脸鼻涕紧跟妈妈
- 莫文蔚将举办“绝色”巡回演唱会 宣传海报遭网友吐槽
- 杨幂和许凯路透照曝光 杨幂身穿白衬衣美腿隐约可见
- 拍打戏被照顾？张蓝心:不要因为我是女孩降低标准
- TVB老戏骨余慕莲化险为夷顺利出院 和以前身形模样判若两人
- 王子文晒粉丝手写信 好奇提问“为什么叫我小丸”
- 李光洙为什么宣布退出RM主持 李光洙退出runningman原因曝光
- 郑恺公司涉合同纠纷案 被强制执行3300万
推荐资讯
点击排行