最近看排列组合,发现了一个很有意思的三角形 (形如附图),不知道前人研究过没,不过这个三角形,是用来分组用的,简称相同元素的分组问题。
假如有一组相同的元素,共n个(n>0),如若分组,要求至少有一个组的数量最多为m个(m<=n),问该种情况下,可以得到的分组方式为多少种 (记为E(n, m))?令:f(n)=E(n,1)+E(n,2)+…+E(n,n)。
则E(n,1) = 1; E(n,2) = int(n/2), int表示取整; E(n,n) = 1; E(n,n-1) = 1。
当m<n/2时, E(n, m)=E(n-m, 1)+E(n-m, 2)+...+E(n-m, m); 通过该公式,m>2时,都可以转化为E(n,1), E(n,2)而获得相关数字。
当m>= int (n/2)时, E(n, m) = f(m)。
但是,求取任一个f(n),基本要将前面的数据进行一次循环;而当m>2时,也需要经过多次循环才能求得,如何在算法上,将此公式化简,加快计算步骤,将是一个很有意思的问题。
https://wap.sciencenet.cn/blog-5038-480314.html
上一篇:
鹊桥仙下一篇:
鸿 门 宴