n个人共有多少种联盟状态？

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

请教一个问题，可能是个经典的组合数学问题，我没有查到：有n个人，可以相互组合成联盟（当然也可以独立），问共有多少种联盟状态？比如n=3时，共有5种联盟状态，其中“（）”表示结成联盟：[(1),(2),(3)]--各自相互独立，组合成三个联盟，只有一种状态
[1,(2,3)]；[2,(1,3)]；[3,(1,2)]--组合成二个联盟，共有三种状态
[(1,2,3)]---组合成一个联盟，共有一种状态
所以当n=3时，共有5种联盟状态

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：三种状态 数学问题 组合数学 经典的 结成 数学

所谓Bell Numbers就是来回答lz的疑问的～

我的好友xpx提供了答案，其实这就是个“求元素为n个的集合上的划分的个数”问题：
含有n个元素的集合的划分数记为Bn
显然B1=1, B2=2,
B0=1
对一般的n有递推公式
Bn+1=C(n,0)B0+C(n,1)B1+....+C(n,n)Bn,

C(n,k)是n元素取k个元素的组合数

利用递推公式可计陆续计算出:
B3=C(2,0)B0+C(2,1)B1+C(2,2)B2=1+2+2=5
B4=C(3,0)B0+C(3,1)B1+C(3,2)B2+C(3,3)B3=1+3*1+3*2+5=15,
.如A={1,2,3,4},即n=4,有15种划分,如下:
仅含1块的划分有1种(1234)
含2块的划分有7种
(1, 234) (2, 134) (3, 124) (4, 123) (12, 34) (13, 24) (14 ,23)
含3块的划分有6种(1, 2, 34) (1, 3, 24) (1, 4, 23) (2, 3, 14) (2, 4, 13) (3, 4, 12)
含4块的划分有1种(1, 2, 3, 4)

但是如何理解公式“Bn+1=C(n,0)B0+C(n,1)B1+....+C(n,n)Bn”  ？

lg21c 发表于 2015-8-26 14:55
但是如何理解公式“Bn+1=C(n,0)B0+C(n,1)B1+....+C(n,n)Bn”  ？

可以这样理解：
C(n,m)为从n中挑出m个的组合数，Bm为这m个元素的划分数，C(n,m)Bm为n中挑出m个元素，然后将这m个元素作划分的总的的组合数，剩下的n-m个样本自成一组，m=1到n，C(n,m)Bm累加起来就是n+1个元素总的划分数

foozhencheng 发表于 2015-8-26 11:54
所谓Bell Numbers就是来回答lz的疑问的～

你说的是对的

https://zh.wikipedia.org/wiki/贝尔数  有介绍

lg21c 发表于 2015-8-26 15:35
你说的是对的

但是只能是递推计算吗？

lg21c 发表于 2015-8-26 15:52
但是只能是递推计算吗？

可以用Bell多项式的母函数展开计算，不过感觉说不上比递推容易~

foozhencheng 发表于 2015-8-27 14:17
可以用Bell多项式的母函数展开计算，不过感觉说不上比递推容易~

Mathematica中有计算贝尔数的函数BellB，十分的酸爽！开始爱上Mathematica了，继Matlab！可真是“学无止境”啊！