n=rs+1個の整数列は、必ず長さr+1の増加部分列か、長さs+1の減少部分列を含む。

証明はrに関する数学的帰納法による。

それでは

増加（減少）列の長さの平均は？

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　（１，２，３，４，５，６，７）の順列，たとえば，

　　３，４，５，１，６，７，２

を考える．

　これは単調増加する部分列３つ

　　Ｌ1＝｛３，４，５｝，Ｌ2＝｛１，６，７｝，Ｌ3＝｛２｝

に分かれる．

　（１，２，３，４，５，６，７，・・・，ｎ）の順列でも同様に考えることができる．

　ｎ→∞のとき，Ｌ1の長さの平均は，

　　ｅ−１＝１．７１８２８１８２８

に近づく．同様に

　　Ｌ2＝ｅ^2−２ｅ＝１．９５２４

　　Ｌ3＝ｅ^3−３ｅ^2＋３ｅ／２＝１．９９５７

　　Ｌn→２

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝