看板 Grad-ProbAsk 關於我們 聯絡資訊
看到兩題題目分別如下 X={x1,x2......xm}, Y={y1,y2......yn} with lXl=m and lYl=n (a)How many relations are there fromX toY? (b)How many functions f: X -> Y satisfy f(x1)=f(xm)=yn a的答案是2^mn b的答案是n^m-2 我想請問(a)為什麼不為n^m呢? 觀念有點不清QQ 感謝大家~ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.31.160.88 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1482820664.A.08F.html
Gabino: 第一題問的是relation 用矩陣想想看 12/27 14:54
Transfat: 你畫一個relation matrix, 縱軸是X={x1,x2..xm}, 橫軸 12/27 14:58
Transfat: 是Y={y1,y2...yn}, 每一個element 都可以是1(有關係)或 12/27 14:59
Transfat: 0(沒關係),所以總共有2^(m*n) 種relation between X&Y 12/27 14:59
Transfat: n^m 應該是function(x)=y 的數量 12/27 15:01
aa06697: relation是AxB(卡氏積)的子集 12/27 16:38
aa06697: function也是一種關係 但是他不能「一對多」 也就是說關 12/27 16:41
aa06697: 係矩陣每列只能有一個1 所以數量就少的多了~ 12/27 16:41
newpuma: 可以問b嗎 為什麼是n^m -2? 12/27 22:42
yupog2003: 應該是n^(m-2)? 12/27 22:48
newpuma: 那-2的次方是怎麼得到的? 12/27 23:03
yupog2003: 因為X1和Xm已經對出去到Yn了,剩下m-2個點要對應 12/27 23:14
yupog2003: 每個點依舊有n種選擇 12/27 23:14
newpuma: 喔喔我以為是任意m 謝突破盲點xd 12/28 00:42