離散數學（一）討論區 2020FMath203

使用說明

新增討論串或留言

點選 Edit 後開始編輯
有三種模式： 只看到編輯器； 只看到結果； 同時看到兩邊

最新的討論串放最上面

​​​​### 討論串標題？
​​​​> 討論串內文
​​​​> [name=yourname] [time=weekday and date] [color=blue]

最新的留言放最下面（記得和前一人的留言空一行）

​​​​> 討論串內文
​​​​> [name=yourname] [time=weekday and date] [color=yourcolor]

• yourname 填你的名字或暱稱（加分用）
• weekday and date 填時間（比如說 Sat, Mar 21, 1986）
• yourcolor 到這邊選一個你喜歡的顏色吧
• 遇到排版問題沒關係，打個 :question: 就會有人幫忙解決

更多說明看這邊
數學式、表情符號…

討論區

新討論串從這邊開始 （留言留在討論串最下面）

此區停止更新（也關閉修改權限），可以改在網路大學上問問題／回答問題。

Big Oh and Little Oh

複習時看到一個yt寫Little Oh 的證明，是需要先證明Big Oh的

$f(n)<=c\ast g(n)$再證極限為0，而且我看到很多部影片中Little Oh定義都是寫

$f(n)<=c\ast g(n)$，但是好像沒有看到筆記或課本有寫Little Oh需要先滿足Big Oh？希望不是我錯過了什麼 iwantA+future

的確

$f=o(g)$ 是比

$f=O(g)$ 強的條件
也就是

$f=o(g)⟹f=O(g)$
課本是說

$f=o(g)$ 的意思是

$\underset{n\to \mathrm{\infty }}{lim}\frac{f(n)}{g(n)}=0$
這句話等價於
對於任何

$c$，當

$n$ 夠大的時候都滿足

$0\le f(n)/g(n)<c$。
希望有回答到你的問題～ Jephian LinThu, Oct 15

K(n,m)需要幾個蟲洞呢?

今天上課討論

$K_{3,3}$ 在杯上的問題，而其連線不交叉原因是上面有一個蟲洞，那如果要

$m$ 點連

$n$ 點不交岔會最少需要幾個蟲洞? wei chengTue, Sep 11 [color=yourcolor]

設蟲洞有

$k$ 個，且

$m,n\in \mathbb{N}$，
if

$n=1$ 或

$2$ 或

$m=1$ 或

$2$ ，then

$k=0$；
if

$n>2$ 且

$m>2$ ,then

$k=(m-2)(n-2)$ Lifang Lu Fri, Sep 11

如果能加上一些說明就太好了! wei chengTue, Sep 11 [color=yourcolor]

第一個if應該很好理解。 而第二個if，除了m1、m2可以完全連接n個點，其餘的m點只能連接n最外面兩個點。 BTW 大家時間是不是都亂打？ Lifang Lu Fri, Sep 11

看來難的部份是說明最少須要這麼多個蟲洞！
方便起見，我們就說

$g(G)$ 是把圖

$G$ 畫出來不交叉最少所須的蟲洞個數。
Lifang 已經說明了

$g(K_{m,n})\le (m-2)(n-2)$。
wei cheng 發現

$g(K_{3,n})\le \lceil \frac{n-2}{2}\rceil$，畫法跟 Lifang 的想法差不多，先將

$K_{2,n}$ 畫在平面，然後再多加一個點。這時候發現一個蟲洞可以幫這個點連到內部的兩個點，所以可以省下一半的蟲洞。
但答案似乎是

$g(K_{3,n})=\lceil \frac{n-2}{4}\rceil$。有辦法畫出來嗎？
可以把答案拍下來，再用上方的 上傳照片。 Jephian LinMon, Sep 14

不會，坐等答案。 Mathisfun Thu, Sep 17

我試驗了一下,狀況超出我想像QQ
中間的圖我畫錯了,

$m_1$,

$m_m$不用連
最後一個圖我試驗了K(3,6)，但我還是需要兩個wormhole，而不是老師的1個wormhole。
Robinson ChiangWed, Oct 7

wei cheng, AL point +0.5.

Lifang Lu, AL point +0.5.
Robinson Chiang, AL point +0.5.

科科，那就再努力一下看看囉？還是你要挑戰

$K_{4,4}$？一樣一個洞。 Jephian LinSat, Oct 10

第一次上課算的那個數字是什麼？

第一次上課的時候老師叫我們算一個 0~6 的數字是幹麻的？如果只是要拿來分組應該不用那麼複雜吧？ I love mathFri, Aug 7

感覺就是讓課程有趣一點安餒 yournamemaybe Wed,Sep 9

有讓課程有趣一點就好，不過不只這樣喔。（樓上記得寫時間和選顏色～） Jephian LinThu, Sep 10

重複物件時環狀排列的公式

課本有提到重覆物件的環狀排列,請問它的公式是甚麼?以及它是如何推導的 YEH JUEWE WEN

thread closed.
moved to archive.

上課講的那串數字到底是什麼？

$1,2,3,4,1,2,3,4,5,1,2,3,4,5,2,3,4,5,6,2,3,4,5,6,\dots$ Jephian LinTue, Sep 22

thread closed.
moved to archive.

鋪地磚

考慮排成一排的

$n$ 個正方格，如果手上有兩種地磚，一種是

$1\times 1$、一種是

$1\times 2$，令

$a_n$ 為用這兩種地磚鋪滿整排的方法數（e.g.,

$a_1=1$,

$a_2=2$），求

$a_n$？ Jephian LinWed, Sep 16

thread closed.
moved to archive.

近視會傳染

誤用數學歸納法會得到奇怪的結論。請拋開一切日常的直覺，細細品味以下的證明，並思考問題出在哪？
敘述

$S_n$：若

$n$ 個人之中有一人近視，則全部

$n$ 個人都會近視。
basic step： 當

$n=1$ 時，敘述

$S_1$ 是正確的，的確如果 1 人之中有一人近視，則全部（只有 1 個人）都會近視。
indutive step：
假設

$S_n$ 成立。
考慮一群

$n+1$ 個人組成的集合

$A=\{p_1,\dots ,p_{n+1}\}$，並假設其中有一人近視。不失一般性，令近視的人叫

$p_1$。
令

$B=\{p_1,\dots ,p_n\}$ 及

$C=\{p_2,\dots ,p_{n+1}\}$ 為兩群人數為

$n$ 的集合。
因為

$B$ 有

$n$ 個人且

$p_1$ 近視，根據歸納法假設，

$B$ 中的所有人都會近視；如此一來，我們知道

$p_2$ 也有近視。
這時

$C$ 有

$n$ 個人且

$p_2$ 近視，根據歸納法假設，

$C$ 中的所有人都會近視；如此一來，

$A$ 中的所有人都近視。
我們得到

$S_n$ 成立

$⟹$

$S_{n+1}$ 成立。
根據數學歸納法，近視會傳染。（請小心你周圍有近視的同學…） Jephian LinFri, Oct 2

thread closed.
moved to archive.

教師節快樂！

表情符號顯示不出來QQ mathisfun Sat, Mon 28

thread closed.
moved to archive.

$S(n)\le n{\log }_{2}n$ 的完整證明

如果

$S(2)=1$,

$S(4)=6$,

$S(2n)=2n+2S(n)$。
證明

$S(n)\le n{\log }_{2}n$ 對於所有

$n=2^k,k\ge 1$。
Jephian LinSat, Sep 26

thread closed.
moved to archive.

sumrecursive

參考課本的程式。 計算

$\sum _{n=1}^{50}(-1{)}^n-2^n+10$ 的值，並附上你的程式碼。 Jephian LinThu, Sep 24

def sumrecursive(n):
    if n == 1:
        return 2;
    else:
        return sumrecursive(n-1) + (n*n - 2*n + 3)
sumrecursive(3)

thread closed.
moved to archive.

隔一格、隔兩格？

考慮一排

$n$ 個座位，要選

$k$ 個位置放坐墊。 如果一個座位可以放多個座墊，那放法有

$H_k^n$ 種。（坐墊和坐墊之間沒距離）
如果一個座位只能放一個坐墊，那放法有

$C_k^n$ 種。（坐墊和坐墊之間距離至少為

$1$）
如果坐墊和坐墊之間距離至少為

$2$（就是一定要隔一格），那放法有幾種？
如果坐墊和坐墊之間距離至少為

$3$（就是一定要隔兩格），那放法有幾種？ Jephian LinSun, Sep 20

thread closed.
moved to archive.

這個等式怎麼證明？

如果

$a+b=n$，則

$$(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{a}{0})(\genfrac{}{}{0ex}{}{b}{k})+(\genfrac{}{}{0ex}{}{a}{1})(\genfrac{}{}{0ex}{}{b}{k-1})+\cdots +(\genfrac{}{}{0ex}{}{a}{k})(\genfrac{}{}{0ex}{}{b}{0}).$$ Jephian LinWed, Sep 16

thread closed.
moved to archive.

這個數列會不會停下來？

課本題到一個數列叫作 Collatz sequence，它的做法是這樣：

1. 選一個正整數
   $n$
2. 如果
   $n$ 是奇數，則
   $n\leftarrow 3n+1$
3. 如果
   $n$ 是偶數，則
   $n\leftarrow n/2$
4. 一直重覆步驟 2 和 3 直到
   $n$ 變為
   $1$ 為止。
   

比如說 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1。我試了很多數都會停下來，它真的都會停下來嗎？
Jephian LinTue, Sep 8

thread closed.
moved to archive.

我要怎麼新增討論串？

好多功課我都不會，想和大家討論，請問要怎麼把問題貼上來呢？ I love mathFri, Aug 7

請參考新增討論串或留言中的說明。 Jephian LinSat, Aug 8

---

聊天測試區

歡迎～我把你的留言移到下面來。 Jephian LinSat, Aug 8

哈囉，我只是上來打個招呼 blackpinkWed, Sep 9

怎樣才能加入系？

怎樣才能加入系排？ I love mathFri, Aug 7

---

英文單字區

• preliminary: 基本的、先備知識
• pattern: 模式
• algorithm: 演算法
• category: 類別
• metro: 捷運
• concrete: 具體的
• precise: 精準的
• postulate: 公理
• Euclid: 歐幾里得