2009-11-28

counting Problem (Inclusion and Exclusion)

At Flo's shop, Flo wants to arrange 15 different plants
on five shelves for a window display.
In how many ways can she arrange them
so that each shelf has at least one, but no more than four, plants?

這問題我看解答是把問題對應到非負整數解的問題
x1 + x2 + x3 + x4 +x5 = 15 ,1<= xi <= 4 for all i = 1 to 5
1.若用GF 解的話用 EGF
2.若用 排容的話 最後答案要乘上排列數 (ie: 15!*answer)
但一般非負整數解問題都是解相同-->不同

我想問的是
這問題是相異到相異的問題
一般會想到onto(m,n)
但它卻有限制條件(onto只要箱子沒空的就可以了,不管箱子裡有幾顆球)
那有相異到相異且限制條件的問題只有1 or 2 這兩種嗎?
還是也可以用onto解???

謝謝


1 則留言:

AIdrifter 提到...

個人淺見

覺得用onto算很可怕
(15,5)的話
接下來要扣掉不合的

其中一個為5就爆表
所以光是這邊就有一大堆可能
況且也不能用(10,5)去想
因為5不是平均扣在每一個shelves上
所以 2個為5也不合

接下來還有6 7 8 9 10 最多至11
光想就很恐怖了orz

ps 7以後就可以指考慮一個

ie
5 55 56 57
6 66
7 75
8
9
10
11


重點是onto不能指定你要扣掉哪一個相異的箱子 你要怎麼把不合的case扣掉呢?
所以建議這題還是用解答方法比方便