遇到排列组合中的一类问题,上网搜索了下还没有这类问题的解答,所以思考该问题同时顺便写下这篇文章记录下。抽象地用数学语言描述,K 个不同元素可重复地有序地选择 N 次(其中 N >= K),且 K 个元素全出现,问有多少种可能。
问题描述
同事问了一个排列组合问题,思考了许久并且上网搜索了下没有这类问题。问题如下:一班级有K位同学,每次随机抽一位同学拍照,拍完后该同学回到班级中,重复以上拍照N次。问K位同学都拍照的概率。
抽象以上问题,K 个不同元素标记为 ,可重复有序选择 N 次,其中 ,且 K 个元素全出现,该情况总数。暂时称这类问题为“可重复遍历有序选择”。
不考虑所有同学都出现,N次拍照过程是“可重复有序选择”的过程。考虑到所有同学都出现,N次拍照过程是“可重复遍历有序选择”的过程。所以概率为:“可重复遍历有序选择” / “可重复有序选择”
问题解答
首先,考虑“可重复有序选择”简单问题,K 个不同元素,可重复有序选择 N 次,显然选择总数为
再,考虑“可重复遍历有序选择”,假设这样 k 个元素 n 次“可重复遍历有序选择”总数为 ,稍微计算。
当 时,即可选择的元素为 ,;
当 时,即可选择的元素为 , 情况则有:, 情况则有:;
得以下公式:
,
, ,
, , ,
$…$
思路:尝试将“可重复遍历有序选择”转化为“可重复有序选择”。
则可以将这个问题转化为:k 个元素先选择出 i 个元素 ,再在对 i 个元素“可重复遍历有序选择”得 ,对 求和等于“可重复有序选择”总数,即,
从集合角度简单证明:等式右边能覆盖所有可能性,并且求和中的各个求和项彼此没有交集;等式左边可以分解成右边的子问题;两个结果集合一一映射。从而证明等式成立
对 举例验证发现有以下线性方程组:
,
,
,
矩阵表示一般情况下该线性方程组:
暂时没找到解析解答,用数值方法解该方程组的数值解。n 较大时因为数值计算误差会有问题,以下对 n = 10 计算,并数值方法验证:
1 |
|
结果如下:
1 |
|