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 則留言:

  1. 線代離散助教(wynne)2012年11月11日 晚上9:08

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

    回覆刪除
  2. K2012年11月11日 晚上11:10

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

    回覆刪除