2012-11-11

離散習題3-123 (c)

題目:Let A={a, b, c, d} , B={1, 2, 3, 4, 5, 6, 7}
how many onto functions f: B->A satisfying f(1)=a?

解答是onto(6,3)+onto(6,4)=2100
為什麼這題不能用全部onto個數 - f(1)!=a
=> onto(7,4) - 3*onto(6,4)=3720

2 則留言:

線代離散助教(wynne) 提到...

只扣掉3*onto(6,4)還不夠
因為這樣只會扣到有其他東西被丟到與 1 同一個箱子的情形
得要再扣掉 1 單獨佔用一個箱子的方法數才行,
所以如果要用扣的, 算法應為
onto(7,4) - 3 * [onto(6,4) + onto(6,3)]

K 提到...

哦哦 完全沒考慮到這個方向
謝謝解答!!