Re: [問題] 一題排列組合

[newacc (XD)]

※ 引述《spider2 ()》之銘言：
: 平面上有20個點，任三個點不共線，
: 共連成190個線段，問圖形中最多可能有幾個三角形？
: 答案好像是八十萬左右

唔，有人跟我算一樣的答案讓我放心了一點XDD


想法：

要數三角形可以從角或是邊下手
如果要從邊的話，答案很簡單是C(190)(3)，但是這是錯的
因為有可能你選到的三個邊根本沒有交點
所以勢必要從角下手。

構成三個角的三個點有可能有兩種：原本一開始的20個"點" 或是 190個線段交錯的"交點"

所以我們可以分成這幾種

1.三個"點"                 → 1*C(20)(3)

2.兩個"點"，一個"交點"     → 4*C(20)(4)

3.一個"點"，兩個"交點"     → 5*C(20)(5)

4.三個"交點"               → 1*C(20)(6)


1.               2.               3.               4.
.       .        .       .        .      .           .   .

                     ×               ×               ×
                                    ×   .        .  ×  × .
    .            .       .        .                .       .
                                      .

圖自己畫一下會比較清楚0rz

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 219.85.245.65
推 bbhands:沒有用到190這個條件？
→ newacc:190我覺得不是條件XD 他非必要，只要任三點不共線就一定有
→ newacc:190個線段XD
推 bbhands:但實際上邊沒有全連(只有190條)，所以上界應該會更小
→ newacc:咦 C(20)(2)=190，全連啦0.0a
推 bbhands:抱歉我算錯了 Orz
推 nierod008:覺得帳號有點似曾相識原來是學長