钥匙与锁的问题(1)

KeyTo9_Fans

10# 056254628 我也做到这一步了。 能否把较小的$N$的答案先算出来，然后看看能不能找到规律？ 7# mathe “应该$p(k)$都是$1/N$” 明显不对吧？

xbtianlang

ABC为箱子，abc是里面的钥匙，最后的箱子是开的。数字是砸的次数。 不砸的概率$1/N$，砸N-1个箱子的概率是$1/(N!)$。 AB C 砸 ab c 2 ac b 1 bc a 0 ba c 1 ca b 0 cb a 1 合计 2+3+1=6 ABC D 砸 abc d 3 abd c 2 acd b 1 acb d 2 adb c 1 adc b 2 bcd a 0 bca d 1 bda c 0 bdc a 1 bac d 2 bad c 1 cda b 1 cdb a 0 cab d 1 cad b 0 cbd a 1 cba d 2 dab c 0 dac b 1 dbc a 2 dba c 1 dca b 0 dcb a 1 合计 6+11+6+1=24

KeyTo9_Fans

这两个结果 $N=3$：$2+3+1=6$ $N=4$：$6+11+6+1=24$ 让我想到了下面两个等式： $(1+x)(2+x)=2+3x+x^2$ $(1+x)(2+x)(3+x)=6+11x+6x^2+x^3$

056254628

下面计算p(1): 1至N的数字排列,形成2个环。 N为奇数，那么种类＝$\sum_{i=1}^{(N-1)/2}{((N!)/((N-i)!))/i*(((N-i)!)/(N-i))}$ =$N!*\sum_{i=1}^{(N-1)/2}{1/(i*(N-i))}$ =$(N!)/N*\sum_{i=1}^{(N-1)/2}{1/i+1/(N-i)}$ =$(N!)/N*\sum_{i=1}^{N-1}{1/i}$ N为偶数，那么种类＝$\sum_{i=1}^{N/2-1}{((N!)/((N-i)!))/i*(((N-i)!)/(N-i))}+((N!)/((N/2)!))/(N/2)*(((N/2)!)/(N/2))/2$ =$(N!)/N*\sum_{i=1}^{N-1}{1/i}$ ------------------------------------------------ 所以p(1)=$1/N*\sum_{i=1}^{N-1}{1/i}$

056254628

受13楼的提示： 应该存在以下恒等式 $1/(N!)*\prod_{i=1}^{N-1}{i+x}=\sum_{i=0}^{N-1}{p(i)*x^i}$

mathe

10# 056254628 我也做到这一步了。 能否把较小的$N$的答案先算出来，然后看看能不能找到规律？ 7# mathe “应该$p(k)$都是$1/N$” 明显不对吧？ KeyTo9_Fans 发表于 2012-1-11 21:28

的确完全想偏了

mathe

设N个锁砸k次的数目为$a_{N,k}$记 $F_N(x)=\sum_{k=0}^{+infty}a_{N,k}x^k$ 是一个N-1次多项式。其中$F_1(x)=1$ 对于N个锁砸k次，由于相当于k+1个环。其中第N个锁单独构成一个环的方案正好是$a_{N-1,k-1}$个 而对于第N个锁所在环必须至少两个锁的情况，删除第N个锁对应于一个$a_{N-1,k}$中的方案，而对于$a_{N-1,k}$中每个方案，插入第N个锁，根据它前面一个锁的数据的不同可以有N-1个方案，所以这种方案正好有$(N-1)a_{N-1,k}$个 所以得到$a_{N,k}=a_{N-1,k-1}+(N-1)a_{N-1,k}$ 于是$F_N(x)=xF_{N-1}(x)+(N-1)F_{N-1}(x)$ 于是$F_N(x)=(x+N-1)F_{N-1}(x)$ 于是就可以得出13#的结论

056254628

17# 用递推方法确实不错。