从1到n,求这n个数的随机序列里面存在一个长度为n/2的递增子序列的概率?注意“递增子序列”的概念,不清楚的XDJM请先百度下

Question

从1到n,求这n个数的随机序列里面存在一个长度为n/2的递增子序列的概率?
注意“递增子序列”的概念,不清楚的XDJM请先百度下

Answer 1

首先,可以证明最大递增子序列和最大递减子序列的长度和=n+1.
这个可以用数学归纳法：显然n=1时成立,假设n=k时成立,当n=k+1时
如果我们把k+1这个数放在原数列前面,最大递增子数列长度不变,最大递减子数列长度加1,假设成立.
如果把k+1这个数放在原数列后面,最大递增子数列长度加1,最大递减子数列长度不变,假设也成立.
如果把k+1这个数放在数列中,也可以发现假设是成立的.
现在假设最大递增子数列长度是i,最大递减子数列长度是j.
显然p(i=m)=p(j=m),m是1到n中间一个数
又因为p(j=m)=p(i=n+1-m).
所以p(i=m)=p(i=n+1-m)
假设n是偶数.p(i=1)=p(i=n); p(i=2)=p(i=n-1).p(i=n/2)=p(i=n/2+1);
把这些等式左右两边分别加起来,右边就是最大递增子序列长度大于n/2的概率.
又因为所有概率和为1,所以最大递增子序列大于n/2的概率是0.5.
最大子序列长度为n/2的概率不会算.
所以所求概率=0.5+p(i=n/2).
当n很大时,p(i=n/2)约为0,所求概率约为0.5