一个求通项的难题,在x坐标轴的原点处有一只机器猫,它在x轴上分别以二分之一的概率或向x轴正方向,或向x轴负方向一步一步行走.步长恒为一个单位.问：经过2n步之后,机器猫回到坐标原点而
3人问答
问题描述：
一个求通项的难题,
在x坐标轴的原点处有一只机器猫,它在x轴上分别以二分之一的概率或向x轴正方向,或向x轴负方向一步一步行走.步长恒为一个单位.
问：经过2n步之后,机器猫回到坐标原点而且这2n步机器猫仅在坐标轴正方向一侧运动的概率an（用含n的式子表示）为多少?
需要过程…… 感激不尽！
侯力回答：
按我的理解,符合要求的“走法”中,起始和终止都在原点,中间2n-2步都在正半轴上(不包括原点),对吧?实际上只要求出符合你要求的“走法”一共有多少种就行了.这是一个非常经典的组合计数问题（当然,不太简单）,答案是Ca...
侯力回答：
首先，抱歉写错了一点。如果要求中间2n-2步都在正半轴上(不包括原点)，那走法数应该是n-1阶Catalan数C(n-1)=C(2n-2,n-1)/n.如果允许中间2n-2步到0，但不能到负半轴，走法数才是n阶Catalan数C(n)=C(2n,n)/(n+1).只要考虑我上面写的第二种情形就行。显然，如果第二种情形的结论是C(n),那么第一种情形的结论必然是C(n-1),因为中间的2n-2步就是第二种情形！说下证明吧，还是很巧妙滴~~重述一下问题：考虑长为2n的0,1序列，其中0,1各有n个。如果任一位置之前“1”的个数≥“0”的个数，称这样的序列为Catalan序列，否则称为补序列。求的是Catalan序列的个数C(n),只要求补序列的个数即可。若{x(i)}为补序列，取最小的k,使得k项之前“1”的个数“0”的个数.定义y(i)=1-x(i),1≤i≤k;y(i)=x(i),k+1≤i≤2n.不难验证，这样定义的{x(i)}为补序列。由此得到一个把{x(i)}映到{y(i)}的双射，因此补序列{x(i)}的个数=n+1个1，n-1个0组成的0,1序列的个数=C(2n,n-1).长为2n的0,1序列有C(2n,n)个，故C(n)=C(2n,n)-C(2n,n-1)=C(2n,n)/(n+1).这样可以算出a(n)=2^(-2n)*C(2n-2,n-1)/n.
数学推荐
数学推荐
最新更新
精品分类
优秀数学推荐
热门数学
邮箱： 