推 alan790712:看不懂英文= =' 專業名詞嘛 04/27 20:24
※ [本文轉錄自 Math 看板]
作者: XII (Mathkid) 看板: Math
標題: Re: [分析] 排列組合
時間: Sat Apr 26 02:03:08 2008
※ 引述《zzzxxxqqq (嫩WLK)》之銘言：
: 延續一下我昨天提的把8相異球放到3個相同箱子的速解法，
: (3^8+3)/3! = 1094
: 想法來自分堆後分給人理論上會是3^8，而影響分堆後分給人的主因
: 就是分幾堆，當分1堆時分給人的情況只有3種，其他都是3!種
: 所以1094*3!-(分成一堆方法數)*(3!-分成1堆分給人)=3^8。
: 1094*3!-1*3=3^8
用 Burnside formula
G=S_3
3=2+1=1+1+1(所有permutation的cycle type)
所求=(1/3!)(0*2+1*3+3^8*1)=1094
: 如果今天是8個相異球放到4相同箱子的速解法，
: 也是一樣考慮分幾堆的情況，分1堆時分給人情況有3種，分2堆時
: 分給人是C(4,2)*2種，其他也都是4!種
: 所以4^8+(分成一堆方法數)*(4!-分成一堆分給人)+
: (分成2堆方法數)*(4!-分成二堆分給人)=答案*4!
: → 4^8 + 1*20 + (8+28+56+35)*(4!-C(4,2)*2)=答案*4!
: 答案...2795
G=S_4
4=3+1=2+2=2+1+1=1+1+1+1
所求=(1/4!)(0*6+1*8+2^8*6+4^8)=2795
(其實可以不管沒有1的partition!)
: 也可以延伸到5個箱子，只是再多考慮分3堆分給人的情形而已
: 我只是想說明他有延續性才打這篇~.~
G=S_5
5=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1
所求=(1/5!)(0*24+1*30+0*20+2^8*20+1*15+3^8*10+5^8)=3845
===========================================================
原來Stirling number of second kind, S(n,k), 可以用Burnside formula算啊!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.166.199.1
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.166.195.195