---
title: 2020FMath203 forum archive
tags: 2020F, Math203
---

[TOC]

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

> 麻煩附一下連結、或是課本的位置。
> [name=Jephian Lin] [time=Sat, Oct 10] [color=teal]

> [連結](https://rellek.net/book/s_intro_enum.html)
> [name=YEH JUEWE WEN]

> 課本這部份在討論離散可能會考慮的問題
> 它要強調的是很多問題都可以算得出來，但是不見得會有明確的算法，而離散數學的其中一部份就是在討論怎樣可以有算地計數。
> 以這個例子來說，它沒有單純的公式，但它可以用每個著色的對稱性來分類。這部份要到下學期才會講到，可以參考[這邊](https://rellek.net/book/s_polya_square.html)。
> [name=Jephian Lin] [time=Sat, Oct 10] [color=teal]

### 上課講的那串數字到底是什麼？
> $1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 2, 3, 4, 5, 6, \ldots$
> [name=Jephian Lin] [time=Tue, Sep 22] [color=teal]

>將所有數字五個分成一組，12341|23451|23452|34562|34563|45673。分隔開的五個數分別標記為abcde,當e等於a時，下一組即上一組的abcd都加1，e不變動；若e等於a-1時，下一組的e加1使e=a，abcd不變動。
>[name=Lai,Chen Yu] [time=Thu, Oct 1] [color=blueviolet]

> 當然！這也是一種規律，但我心中想的比這還單純一些。課本的每個章節最後都有一個 [Discussion](https://rellek.net/book/s_induction_discussion.html)。也許裡面有答案？另外請再私下跟我說 Lai 是誰？
> [name=Jephian Lin] [time=Fri, Oct 2] [color=teal]

>我不知道這個討論串是不是問題還沒解決所以決定來寫結論XD。\
>就是美國的硬幣有幣值cent(0.01)、nickel(0.05)、dime(0.10)、quarter(0.25)、half(0.5)、coin(1)\
>所以這個數列的次序代表我想用最少的硬幣表示出這個次序的金額，以cent為單位，所以:\
>1234123451234523456234561234523456345673，我數到40就好了XD
>[name=Robinson Chiang][time=Wed,Oct 7][color=aqua]

:::success
Lai, AL point +0.5. :tada:
Chen Yu, AL point +0.5. :tada:
Robinson Chiang， AL point +0.5. :tada:
:::

> Bingo！
> [name=Jephian Lin] [time=Sat, Oct 10] [color=teal]

### 鋪地磚
> 考慮排成一排的 $n$ 個正方格，如果手上有兩種地磚，一種是 $1\times 1$、一種是 $1\times 2$，令 $a_n$ 為用這兩種地磚鋪滿整排的方法數（e.g., $a_1=1$, $a_2=2$），求 $a_n$？
> [name=Jephian Lin] [time=Wed, Sep 16] [color=teal]

> $a_n$應該會=1+$\binom{n-1}{1}$+$\binom{n-2}{2}$+...+$\binom{n-k}{k}$ (停止條件為 n-k<k) 第一項是全部都是用$1\times 1$的，所以方法數為1，第二項是用一個是$1\times 2$其他用$1\times 1$的總共為n-1塊，所以排列的方法數為$\binom{n-1}{1}$，後面的以此類推
> [name=Shuhan Hsieh, Wei-ju Chyr] [time=Thu, Sep 17]
[color=Aqua]

> 疑，沒看懂，可以再說明一下 $\binom{n-2}{2}$ 嗎？
> [name=Jephian Lin] [time=Sun, Sep 20] [color=teal]

> $\binom{n-1}{1}$是放入一個$1\times 2$的其他剩餘n-2格用n-2個$1\times 1$的填滿，所以總共為n-1個，然後選一個位置放$1\times 2$的，所以為$\binom{n-1}{1}$;$\binom{n-2}{2}$則是放入兩個$1\times 2$的其他剩餘n-4格用n-4個$1\times 1$的填滿，所以總共為n-2個，然後選兩個位置放$1\times 2$的，所以為$\binom{n-2}{2}$
> [name=Shuhan Hsieh] [time=Sun, Sep 20]
[color=Aqua]

:::success
Shuhan Hsieh, AL point +0.5. :tada:
Wei-ju Chyr, AL point +0.5. :tada:
:::

> 有趣耶！跟我想的不一樣，不過這是正確的：） 第一項 1 也可以寫成 $\binom{n}{0}$，所以完整的答案是
> $$\binom{n}{0} + \binom{n-1}{1} + \binom{n-2}{2} + \cdots + \binom{n-k}{k}, k = \left\lfloor\frac{n}{2}\right\rfloor$$
> 附加一題，估且把 $a_0$ 當作 $1$（不放也算是一種放法），所以 $a_0=1$, $a_1=1$, $a_2=2$，算一下後面幾項，然後想想這個數列有沒有什麼名字？
> [name=Jephian Lin] [time=Sun, Sep 20] [color=teal]

>算了前面幾項得到 $a_0=1$, $a_1=1$, $a_2=2$, $a_3=3$, $a_4=5$, $a_5=8$, $a_6=13$, $a_7=21$ ...此數列應為費氏數列 ($a_0=1$, $a_1=1$, $a_n=a_{n-1}+a_{n-2}$)
> [name=Shuhan Hsieh] [time=Sun, Sep 20]
[color=Aqua]

> 所以費氏數列必須滿足 $a_n=a_{n-1}+a_{n-2}$。由我們鋪磚的定義，可以看出 $a_n$ 有這個遞迴關係式嗎？
> [name=Jephian Lin] [time=Wed, Sep 16] [color=teal]

>恕我吐槽一下，我猜測樓上日期應該key錯了XD\
>再來回答教授的問題，當然可以從定義看出來XD，這好像是排容還是什麼有點忘了。就是從定義來看這題可以說是我要排{$a_1$,$a_2$,....,$a_n$:$a_i$= 1 or 2}使得總合為N。\
>就慢慢觀察，那麼我會從3開始看，我想總合為3，則有21、12、111，那就開始思考case:\
>Case1:\
>When $a_1$=1，那我的情況就是要鋪兩格的意思，那就跟我N=2的舖法是一樣的。\
>Case2:\
>When $a_1$=2,那我就是要鋪一格的意思，跟我N=1的舖法一樣。\
>So {N=3}={N=1}+{N=2}
>\
>那我繼續推理就可得到一個結論:**{N}={N-1}+{N-2}**，i.e. Fibonnaci sequence.
>[name=Robinson Chiang][time=Wed,Oct 7][color=aqua]

:::success
Shuhan Hsieh, AL point +0.5. :tada:
Robinson Chiang, AL point +0.5. :tada:
:::

> 除了排版有待加強以外我沒什麼好抱怨的:smiley:
> [name=Jephian Lin] [time=Sat, Oct 10] [color=teal]

### 近視會傳染 :scream:
> 誤用數學歸納法會得到奇怪的結論。請拋開一切日常的直覺，細細品味以下的證明，並思考問題出在哪？
> **敘述 $S_n$**：若 $n$ 個人之中有一人近視，則全部 $n$ 個人都會近視。
> **basic step**： 當 $n=1$ 時，敘述 $S_1$ 是正確的，的確如果 1 人之中有一人近視，則全部（只有 1 個人）都會近視。
> **indutive step**：
> 假設 $S_n$ 成立。
> 考慮一群 $n+1$ 個人組成的集合 $A = \{p_1,\ldots,p_{n+1}\}$，並假設其中有一人近視。不失一般性，令近視的人叫 $p_1$。
> 令 $B = \{p_1,\ldots,p_{n}\}$ 及 $C = \{p_2,\ldots,p_{n+1}\}$ 為兩群人數為 $n$ 的集合。
> 因為 $B$ 有 $n$ 個人且 $p_1$ 近視，根據歸納法假設，$B$ 中的所有人都會近視；如此一來，我們知道 $p_2$ 也有近視。
> 這時 $C$ 有 $n$ 個人且 $p_2$ 近視，根據歸納法假設，$C$ 中的所有人都會近視；如此一來，$A$ 中的所有人都近視。
> 我們得到 $S_n$ 成立 $\implies$ $S_{n+1}$ 成立。
> 根據數學歸納法，近視會傳染。（請小心你周圍有近視的同學...）
> [name=Jephian Lin] [time=Fri, Oct 2] [color=teal]

>我重新思考了步驟:
>證明的prop是\
>$S_{n}$:如果n個人中有1人近視，則n個人都近視。\
>那麼我想使用的MI.應該是\
>Step1:\
>當|S|=1,S={$n_1$},$n_1$ is nearsighted, then for every element in S, they are all nearsighted obviously.\
>Step2:\
>我假設|S|=n成立，則我觀察|S|=n+1的狀況，**並且由n的集合擁有的性質去induct**，這是比較常發生失誤的地方。不過教授的例子特別的地方是inductive step裡面的B,C要想達成目的必須有個假設:\
>**B∩C ≠ ∅**\
>因此我觀察n=1到n=2的induction就可以發現B跟C交集為空，因此有誤。\
>連假愉快!
>[name=Robinson Chiang][time=Sun,Oct 4][color=Aqua]

:::success
Robinson Chiang, AL point +1. :tada:
:::

> Beautiful explanation!
> [name=Jephian Lin] [time=Mon, Oct 5] [color=teal]

### 教師節快樂！:mortar_board:
> :rolling_on_the_floor_laughing::rolling_on_the_floor_laughing::rolling_on_the_floor_laughing:
> 表情符號顯示不出來QQ
> [name=mathisfun]
[time=Sat, Mon 28]
[color=magenta]

> 謝謝！ :rofl: 好像已經不能用了，我幫你找了一個類似的。
> [name=Jephian Lin] [time=Tue, Sep 29] [color=teal]

### $S(n)\leq n\log_2n$ 的完整證明
> 如果 $S(2) = 1$, $S(4) = 6$, $S(2n) = 2n + 2S(n)$。
> 證明 $S(n)\leq n\log_2n$ 對於所有 $n=2^k, k\geq 1$。
> [name=Jephian Lin] [time=Sat, Sep 26] [color=teal]

> 1.當k=1時，$S(2^1) = 1\leq 2^1\log_2 2^1=2*1=2$成立。
> 2.假設$k=t$，$t>1$時，$S(2^t)\leq 2^t\log_2 2^t$成立。
> 3.當$k=t+1$時，
> $S(2^{t+1})=S(2*2^t)=2*2^t+2S(2^t)(題目條件)$
> $\leq 2*2^t+2*2^t\log_2 2^t(條件2)$
> $=2*2^t+2*2^t*t=2*2^t(1+t)$
> $=2^{t+1}(t+1)=2^{t+1}\log_2 2^{t+1}$亦成立。
> 由數學歸納法得出$S(n)\leq n\log_2 n$
>[name=Chen Yu] [time=Sun, Sep 27][color=Lime]

:::success
Chen Yu, AL point +0.5. :tada:
:::

> Nice work! 有你們這群優秀的學生真好！
> [name=Jephian Lin] [time=Sun, Sep 27] [color=teal]

### `sumrecursive`
> 參考課本的[程式](https://rellek.net/book/s_induction_statements.html#sage-4)。
> 計算 $\sum_{n=1}^{50} (-1)^n - 2^n + 10$ 的值，並附上你的程式碼。
> [name=Jephian Lin] [time=Thu, Sep 24] [color=teal]

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

>$\sum_{n=1}^{50} (-1)^n - 2^n + 10$ = -2251799813684746
> [name=Shuhan Hsieh] [time=Sat, Sep 26]
[color=Aqua]

def sumrecursive(n):
    if n == 1:
        return 7;
    else:
        return sumrecursive(n-1) + (((-1)^n) - 2^n + 10)
sumrecursive(50)

:::success
Shuhan Hsieh, AL point +0.5. :tada:
:::

> Nice! 順便提一下 Sage 裡 `2^n` 和 `2**n` 都是 `2` 的 `n` 次方的意思，但是一般 Python 裡只有 `2**n` 才是 `2` 的 `n` 次方的意思，`2^n` 是別的意思。
> [name=Jephian Lin] [time=Sun, Sep 27] [color=teal]

### Theorem 3.9
> Theorem 3.9. Let m,n,cab,am+bn=ccmn.
> Let's see how the Euclidean algorithm can be used to write
> gcd(m,n)am+bn a,b∈Z
> 這是要證的定理3.9嗎?
> 有連結嗎我發現找不到他了

> 請閱讀討論區的[使用說明](#%E4%BD%BF%E7%94%A8%E8%AA%AA%E6%98%8E)。
> 課程筆記上已經更新連結了，或是參考這個連結 [Theorem 3.9](https://hackmd.io/@jlch3554/2020FMath203-notes#Theorem-39)。週五上課會講到。
> [name=Jephian Lin] [time=Wed, Sep 23] [color=teal]

### 隔一格、隔兩格？
> 考慮一排 $n$ 個座位，要選 $k$ 個位置放坐墊。
> 如果一個座位可以放多個座墊，那放法有 $H^n_k$ 種。（坐墊和坐墊之間沒距離）
> 如果一個座位只能放一個坐墊，那放法有 $C^n_k$ 種。（坐墊和坐墊之間距離至少為 $1$）
> 如果坐墊和坐墊之間距離至少為 $2$（就是一定要隔一格），那放法有幾種？
> 如果坐墊和坐墊之間距離至少為 $3$（就是一定要隔兩格），那放法有幾種？
> [name=Jephian Lin] [time=Sun, Sep 20] [color=teal]

>隔一格可以先把所有坐墊中間放一個空位，即剩下n-2k+1個空位，剩下的空位再從k個座位的中間加上兩側即k+1用H排序決定剩下空位位置，所以為$H^{k+1}_{n-2k+1}$種。隔兩格也是一樣的道理，所以是$H^{k+1}_{n-3k+2}$種。
>[name=Chen Yu] [time=Sun, Sep 20][color=Lime]

> 答案是正確的。可以說明一下 $n-2k+1$ 是怎麼來的嗎？為什麼先把所有坐墊中間放一個空位，會剩下 $n-2k+1$ 個空位？
> [name=Jephian Lin] [time=Mon, Sep 21] [color=teal]

>就所有n個座位扣掉k個排上坐墊的位置，再扣去k個坐墊兩兩中間的空位即k-1個空隔，所以剩下還沒有排進去的空位還有n-k-(k-1)=n-2k+1個空位。
>[name=Chen Yu] [time=Sun, Sep 21][color=Lime]

:::success
Chen Yu, AL point +0.5. :tada:
:::

### 這個等式怎麼證明？
> 如果 $a+b = n$，則
> $$\binom{n}{k} = \binom{a}{0}\binom{b}{k} + \binom{a}{1}\binom{b}{k-1} + \cdots +\binom{a}{k}\binom{b}{0}.$$
> [name=Jephian Lin] [time=Wed, Sep 16] [color=teal]

> 我不知道怎麼證明，但這個式子可以想成:有a個男生，b個女生，要在其中選k個人。
> [name=Lifang Lu]
[time=Wed, Sep 16]
[color=LightSkyBlue]

:::success
Lifang Lu, AL point +0.5. :tada:
:::

>我想到的是利用二項式定理去證明，用 $(x+y)^{a+b} = (x+y)^a \times (x+y)^b$ ，找 $x^ky^{a+b-k}$ 那一項的係數兩邊相等，就可以得到上面那條式子（已更正了）
> [name=Shuhan Hsieh]
[time=Wed, Sep 16]
[color=Aqua]

:::success
Shuhan Hsieh, AL point +0.5. :tada:
:::

> 應該是 $(x+y)^{a+b}= (x+y)^a * (x+y)^b$
> [name=Lifang Lu]
[time=Thu, Sep 17]
[color=LightSkyBlue]

> 兩個都沒錯喔！
> Lifang Lu: 你只要把你的敘述寫完整就是證明了。
> 考慮一班 $n$ 個人，其中 $a$ 個男生 $b$ 個女生。
> 若要從班上挑出 $k$ 個人，有 $\binom{n}{k}$ 種挑法。
> 同時另一種算法是：
> 從男生中挑出 $0$ 個、再從女生中挑出 $k$ 個，有 $\binom{a}{0}\binom{b}{k}$ 種方法。
> 從男生中挑出 $1$ 個、再從女生中挑出 $k-1$ 個，有 $\binom{a}{1}\binom{b}{k-1}$ 種方法。
> ...
> 從男生中挑出 $k$ 個、再從女生中挑出 $0$ 個，有 $\binom{a}{k}\binom{b}{0}$ 種方法。
> 因此兩邊等式成立。
> [name=Jephian Lin] [time=Wed, Sep 16] [color=teal]

### 這個數列會不會停下來？
> 課本題到一個數列叫作 Collatz sequence，它的做法是這樣：
> 1. 選一個正整數 $n$
> 2. 如果 $n$ 是奇數，則 $n \leftarrow 3n+1$
> 3. 如果 $n$ 是偶數，則 $n \leftarrow n/2$
> 4. 一直重覆步驟 2 和 3 直到 $n$ 變為 $1$ 為止。
> [color=teal]

> 比如說 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1。我試了很多數都會停下來，它真的都會停下來嗎？
> [name=Jephian Lin] [time=Tue, Sep 8] [color=teal]

> 奇數一定會變成偶數，而偶數不一定會變成奇數，而且單看奇數數列有變小的趨勢，直到 $2^k$ ($k\in\mathbb{N}$)出現，最後變成1。
> [name=Lifang Lu]
[time=Fri, Sep 11]
[color=LightSkyBlue]

:::success
Lifang Lu, AL point +1. :tada:
:::

> 很好的觀察，所以有兩個重點：
> 第一：奇數變偶數，偶數會一直變小變成奇數
> 第二：一但出現 $2^k$ 的形式就會一路降為 $1$
> 所以重點在於奇數的部份是不是會一直下降，但目前看起來好像有升有降
> 有辦法找到一個比我的例子還長的數列嗎？
> （我幫你留言中的數學式排版了一下）
> [name=Jephian Lin] [time=Tue, Sep 8] [color=teal]

> 如果只是要找長數列只需從三的奇數倍數找，在不考慮偶數的情況下，因為偶數可以藉由/2而變為奇數，加上3n+1的關係使得此數列只有第一個可能是三的倍數，
> ex:9 28 14 7 ...
> [name=wei cheng] [time=Fri, Sep 11] [color=yourcolor]

> 這個主意不錯：**只有第一個數可能是三的倍數**。可以給個具題的例子嗎？比如說 9 開始的話真的會比較長嗎？
> [name=Jephian Lin] [time=Fri, Sep 11] [color=teal]

> 數列要比你長很簡單，首位為 2^17 就行,只是沒有奇數。
> [name=Lifang Lu]
[time=Fri, Sep 11]
[color=LightSkyBlue]

:::success
Lifang Lu, AL point +0.5. :tada:
:::

> 其實比較長要看跟誰比，如果將 $f(n)=3n+1$, $g(n)=n/2$，$f(n)$、$g(n)$ 的數列必然比n的數列短，因為 $f,g$ 皆是($\mathbb{N}\to \mathbb{N}$)上 1-1 函數，所以只要出現已經做出來的數字其數列必收斂至1。
> 所以9的數列中出現7，則表示9的數列必然比7長並且收斂到1。
> 上面錯誤已修正。
> [name=wei cheng] [time=Fri, Sep 11] [color=yourcolor]

:::success
wei cheng, AL point +0.5. :tada:
:::

> Nice work! 有興趣的可以再參考一下[維基百科：Collatz sequence](https://en.wikipedia.org/wiki/Collatz_conjecture) 裡的更多內容～
> [name=Jephian Lin] [time=Sat, Sep 12] [color=teal]