changed 5 years ago
Linked with GitHub

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

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

麻煩附一下連結、或是課本的位置。
Jephian LinSat, Oct 10

連結
YEH JUEWE WEN

課本這部份在討論離散可能會考慮的問題
它要強調的是很多問題都可以算得出來,但是不見得會有明確的算法,而離散數學的其中一部份就是在討論怎樣可以有算地計數。
 以這個例子來說,它沒有單純的公式,但它可以用每個著色的對稱性來分類。這部份要到下學期才會講到,可以參考這邊
Jephian LinSat, Oct 10

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

\(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\)
Jephian LinTue, Sep 22

將所有數字五個分成一組,12341|23451|23452|34562|34563|45673。分隔開的五個數分別標記為abcde,當e等於a時,下一組即上一組的abcd都加1,e不變動;若e等於a-1時,下一組的e加1使e=a,abcd不變動。
Lai,Chen YuThu, Oct 1

當然!這也是一種規律,但我心中想的比這還單純一些。課本的每個章節最後都有一個 Discussion。也許裡面有答案?另外請再私下跟我說 Lai 是誰?
Jephian LinFri, Oct 2

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

Lai, AL point +0.5.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Chen Yu, AL point +0.5.
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Robinson Chiang, AL point +0.5.
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Bingo!
Jephian LinSat, Oct 10

鋪地磚

考慮排成一排的 \(n\) 個正方格,如果手上有兩種地磚,一種是 \(1\times 1\)、一種是 \(1\times 2\),令 \(a_n\) 為用這兩種地磚鋪滿整排的方法數(e.g., \(a_1=1\), \(a_2=2\)),求 \(a_n\)
Jephian LinWed, Sep 16

\(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}\),後面的以此類推
Shuhan Hsieh, Wei-ju ChyrThu, Sep 17

疑,沒看懂,可以再說明一下 \(\binom{n-2}{2}\) 嗎?
Jephian LinSun, Sep 20

\(\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}\)
Shuhan HsiehSun, Sep 20

Shuhan Hsieh, AL point +0.5.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Wei-ju Chyr, AL point +0.5.
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

有趣耶!跟我想的不一樣,不過這是正確的:) 第一項 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\),算一下後面幾項,然後想想這個數列有沒有什麼名字?
Jephian LinSun, Sep 20

算了前面幾項得到 \(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}\))
Shuhan HsiehSun, Sep 20

所以費氏數列必須滿足 \(a_n=a_{n-1}+a_{n-2}\)。由我們鋪磚的定義,可以看出 \(a_n\) 有這個遞迴關係式嗎?
Jephian LinWed, Sep 16

恕我吐槽一下,我猜測樓上日期應該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.
Robinson ChiangWed,Oct 7

Shuhan Hsieh, AL point +0.5.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Robinson Chiang, AL point +0.5.
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

除了排版有待加強以外我沒什麼好抱怨的

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Jephian LinSat, Oct 10

近視會傳染
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

誤用數學歸納法會得到奇怪的結論。請拋開一切日常的直覺,細細品味以下的證明,並思考問題出在哪?
敘述 \(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}\) 成立。
根據數學歸納法,近視會傳染。(請小心你周圍有近視的同學
Jephian LinFri, Oct 2

我重新思考了步驟:
證明的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交集為空,因此有誤。
連假愉快!
Robinson ChiangSun,Oct 4

Robinson Chiang, AL point +1.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Beautiful explanation!
Jephian LinMon, Oct 5

教師節快樂!
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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

謝謝! :rofl: 好像已經不能用了,我幫你找了一個類似的。
Jephian LinTue, Sep 29

\(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\)
Jephian LinSat, Sep 26

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\)
Chen YuSun, Sep 27

Chen Yu, AL point +0.5.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Nice work! 有你們這群優秀的學生真好!
Jephian LinSun, Sep 27

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)

\(\sum_{n=1}^{50} (-1)^n - 2^n + 10\) = -2251799813684746
Shuhan HsiehSat, Sep 26

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

Shuhan Hsieh, AL point +0.5.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Nice! 順便提一下 Sage 裡 2^n2**n 都是 2n 次方的意思,但是一般 Python 裡只有 2**n 才是 2n 次方的意思,2^n 是別的意思。
Jephian LinSun, Sep 27

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嗎?
有連結嗎我發現找不到他了

請閱讀討論區的使用說明
課程筆記上已經更新連結了,或是參考這個連結 Theorem 3.9。週五上課會講到。
Jephian LinWed, Sep 23

隔一格、隔兩格?

考慮一排 \(n\) 個座位,要選 \(k\) 個位置放坐墊。
如果一個座位可以放多個座墊,那放法有 \(H^n_k\) 種。(坐墊和坐墊之間沒距離)
如果一個座位只能放一個坐墊,那放法有 \(C^n_k\) 種。(坐墊和坐墊之間距離至少為 \(1\)
如果坐墊和坐墊之間距離至少為 \(2\)(就是一定要隔一格),那放法有幾種?
如果坐墊和坐墊之間距離至少為 \(3\)(就是一定要隔兩格),那放法有幾種?
Jephian LinSun, Sep 20

隔一格可以先把所有坐墊中間放一個空位,即剩下n-2k+1個空位,剩下的空位再從k個座位的中間加上兩側即k+1用H排序決定剩下空位位置,所以為\(H^{k+1}_{n-2k+1}\)種。隔兩格也是一樣的道理,所以是\(H^{k+1}_{n-3k+2}\)種。
Chen YuSun, Sep 20

答案是正確的。可以說明一下 \(n-2k+1\) 是怎麼來的嗎?為什麼先把所有坐墊中間放一個空位,會剩下 \(n-2k+1\) 個空位?
Jephian LinMon, Sep 21

就所有n個座位扣掉k個排上坐墊的位置,再扣去k個坐墊兩兩中間的空位即k-1個空隔,所以剩下還沒有排進去的空位還有n-k-(k-1)=n-2k+1個空位。
Chen YuSun, Sep 21

Chen Yu, AL point +0.5.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

這個等式怎麼證明?

如果 \(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}.\]
Jephian LinWed, Sep 16

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

Lifang Lu, AL point +0.5.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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

Shuhan Hsieh, AL point +0.5.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

應該是 \((x+y)^{a+b}= (x+y)^a * (x+y)^b\)
Lifang Lu
Thu, Sep 17

兩個都沒錯喔!
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}\) 種方法。
因此兩邊等式成立。
Jephian LinWed, Sep 16

這個數列會不會停下來?

課本題到一個數列叫作 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

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

Lifang Lu, AL point +1.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

很好的觀察,所以有兩個重點:
第一:奇數變偶數,偶數會一直變小變成奇數
第二:一但出現 \(2^k\) 的形式就會一路降為 \(1\)
所以重點在於奇數的部份是不是會一直下降,但目前看起來好像有升有降
有辦法找到一個比我的例子還長的數列嗎?
(我幫你留言中的數學式排版了一下)
Jephian LinTue, Sep 8

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

這個主意不錯:只有第一個數可能是三的倍數。可以給個具題的例子嗎?比如說 9 開始的話真的會比較長嗎?
Jephian LinFri, Sep 11

數列要比你長很簡單,首位為 2^17 就行,只是沒有奇數。
Lifang Lu
Fri, Sep 11

Lifang Lu, AL point +0.5.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

其實比較長要看跟誰比,如果將 \(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。
上面錯誤已修正。
wei chengFri, Sep 11 [color=yourcolor]

wei cheng, AL point +0.5.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Nice work! 有興趣的可以再參考一下維基百科:Collatz sequence 裡的更多內容~
Jephian LinSat, Sep 12

Select a repo