传球问题
解答：
考虑更一般情况：r个人互相传球n次的情况
令X(n)为第n次传球后，此球在最初发球者手中的所有情况的种数，Y(n)为第n次传球时，此球不在最初发球者手中的所有情况的种数。则不难得出： X(1)=0，Y(1)=r-1。 X(2)=Y(1)，Y(2)=(r-1)X(1)+(r-2)Y(1)。 … … … X(n)=Y(n-1)，Y(n)=(r-1)X(n-1)+(r-2)Y(n-1)。
设n=2k1+k2（k1是整数，k2=0或1），可推得
X(n)= C1(n)(r-1)(r-2)^(n-2)+C2(n)(r-1)^2(r-2)^(n-4) +C3(n)(r-1)^3(r-2)...全部
解答：
考虑更一般情况：r个人互相传球n次的情况
令X(n)为第n次传球后，此球在最初发球者手中的所有情况的种数，Y(n)为第n次传球时，此球不在最初发球者手中的所有情况的种数。则不难得出： X(1)=0，Y(1)=r-1。
X(2)=Y(1)，Y(2)=(r-1)X(1)+(r-2)Y(1)。 … … … X(n)=Y(n-1)，Y(n)=(r-1)X(n-1)+(r-2)Y(n-1)。
设n=2k1+k2（k1是整数，k2=0或1），可推得
X(n)= C1(n)(r-1)(r-2)^(n-2)+C2(n)(r-1)^2(r-2)^(n-4) +C3(n)(r-1)^3(r-2)^(n-6)+…+Ck1(n)(r-1)^k1(r-2)^k2
其中Cj(n)=C(n-j-2,j-1)+C(n-j-2,j-2) C(m,k)为m个不同数中取k个数的组合种数=m(m-1)…(m-k+1)/k！ 若k=0，则C(m,k)=1 若k＜0或k＞m，则C(m,k)=0
注：实际计算时，X(n)也可按前面的递归公式一步步求出。
例子：r=5，n=7，7=2*3+1得k1=3，k2=1
X(7)=C(1)×(4)×(3)^5+C(2)×(4)^2×(3)^3+C(3)×(4)^3×(3)
=1×4×3^5+4×4^2×3^3+3×4^3×3=3276
补充：
受zhh2360启发，X(n,r)有更简单的计算方法：
X(n,r)=[(r-1)/r][(r-1)^(n-1)+(-1)^n]，证明如下：
将X(n)=Y(n-1)代入Y(n)=(r-1)X(n-1)+(r-2)Y(n-1)得：
Y(n)-(r-2)Y(n-1)-(r-1)Y(n-2)=0 （１）
设Y(n)=Aα^n+Bβ^n
则α，β是方程y^2-(r-2)y-(r-1) =0的根，不难求出这两个根是r-1,-1
再由初始条件Y(0)=0,Y(1)=r-1代入(1)得到：
A+B=0
A(r-1)-B=r-1
解得A=(r-1)/r,B=-(r-1)/r
故Y(n)=[(r-1)/r][(r-1)^n -(-1)^n]
所以，X(n,r)=Y(n-1)
=[(r-1)/r][(r-1)^(n-1)-(-1)^(n-1)]
=[(r-1)/r][(r-1)^(n-1)+(-1)^n]。
对于本题是上面讨论的特列，r=5，所以
本题传球种数=[4/5][4^(N-1)+(-1)^N]。
。收起
