笔试概率题目

题目
有两个数组A[n], B[m], n
A中的n个元素互不相同，对B中的每一个元素，
都从A中随机取一个元素放入其中，
求A中的n个元素在B中都出现的概率
解答
从古典概率的角度来考虑，相当于从集合A（a1,a2,....,an)中选择元素放到筐子B1,B2,...,Bm中去，求在这m个框子中包含了全部A中元素的概率。

首先，从A中选择元素放置到框子中的方法有n^m中，是没有问题的，
其次，需要计算这些放置方法中把A中所有元素都取了一遍的方法个数。楼下这种方法给出的是n!*n^(m-n),我可以看成是取了前n个筐子莱放置A中n个元素，那么有n!种方式，然后后面的m-n个筐子可以随便放，有n^(m-n)种方式，所以是n!*n^(n-m)中。但是这种方式减少了可能的次数。考虑将m个不同的元素分成n份，这个数目记为S(m,n), 那么我们需要计算的这个数应该是n!*S(m,n)
那么概率就是 n!*S(m,n)/n^m
因为是有标号的，所以Stirling数前面乘一个n!嘛。
ps:
stirling数
将n个不同颜色的球放人k个无标号的盒子中( n>=k>=1，且盒子不允许为空)的方案数就是stirling数.(即含 n 个元素的集合划分
为 k 个集合的情况数)
递推公式:
S(n,k) = 0 (k > n)
S(n,1) = 1 (k = 1)
s(n,k)=1 (n=k)
S(n,k) = S(n-1,k-1)+k*S(n-1,k) (n >= k >= 2)