Research Space for Linear Algebra & Discrete Mathematics
老師教的和書上寫的那個是一樣的, 當有 m 個 R, n 個 U, 並且限定在任何時間點 U 的個數不可超過 R 的個數的情況下, 用那個轉換法可知一個非法的走法可以對應到一個具有 m+1 個 U 以及 n-1 個 R 的排列, 所以非法的個數共有 c(m+n,n-1) 個, 那麼合法的總數就是 c(m+n,n)-c(m+n,n-1)以(1)小題為例, 在你上課筆記中的那兩行(一個是左箭頭一個是右箭頭)就是在說明一個不合法的走法與一個具有 2R8U 的排列是一一對應的, 也就是說給定一個非法的走法, 我們可以將那個非法的走法唯一轉換成一種具有 2R8U 的排列, 反過來也一樣, 當給定一個具有 2R8U 的排列, 我們一樣也可以把它轉換回一個非法的走法, 所以當有 7 個 R 和 3 個 U 時, 非法的總數為 c(10,2), 所以合法的走法總共會有 c(10,3)-c(10,2) 個
恩 謝謝助教回答可能是我表達不太好> <我是想要問如果希望R必大於U原本lattice path是因為反轉左邊RUU |RRRURRRURR<---inverse使得C(10,2)為非法數原本原因是因為超過線了可以鏡射到另一邊看等價但老師是用RUU |RRRURRR UUURUUU<---inverse雖然個數是一樣的但是就理解方式我覺得鏡射右邊很奇怪耶...至於(10,2)合法數=7R3U的非法數這我是知道的還有不知道助教有沒有看到第一張圖那一張圖有附上前一題教授排考試的的題目和解答因為不太好表達 所以就把筆記丟上來了在順便麻煩這題了~
1. 有關第一張圖, 你貼的圖和書上寫的解法也是一樣的, 所以我還是看不太知道你的問題是甚麼, 也不太懂你在前一篇寫的想法, 為什麼你會先假設有讓一個教授監考7EXAM的情況發生, 這樣不是一開始就和題目要的有所矛盾了嗎? 得麻煩你再試著解釋一下你的想法囉2. 不管是將前面做鏡射還是將後面做鏡射, 想法都是一樣的, 以圖二為例, 非法的情形就是前面有k個R, k+1個U, 後面有m-k個R, n-k-1個U, 那麼將前面做鏡射以後就變成前面有k個U, k+1個R, 後面不變, 這樣前面加上後面總共就會有n-1個U, m+1個R, 也就是說, 前轉或者是後轉兩者之間只有U,R互調的差別而已, i.e., 2R8U或者是2U8R的差別或者再看第三張圖, 這樣子的轉換也就相當於是在說明每種從(0,0)走到(2n,0)的不合法走法, 都可以對應到一個從(-2,0)隨便走到(2n,0)的走法, 也就是在你筆記上那些綠色字所說的, 因為從(-2,0)隨便走到(2n,0)就代表在2n個symbol裡U要比R多兩個, 也就是說在那裏面必須要有n+1個U, n-1個R
謝謝助教的回答:)關於筆記上那題可是不超過7不是有包含7的意思嗎?<=7所以說用鴿籠假設A教授有七堂課 B教授有6堂課他們可以這樣排課ABABABABABABA而三位教授ABCABCAB..四位ABCDABCD...交錯排而不違反每教授不超過7堂課(含7)還是題目的意思是不可以等於7但是這樣筆記上的圖就錯了阿?還是這是在課本哪裡我離散是舊版(4)我可以去翻一翻看一下原題
原題在p6-66範例7, 你對題意的理解沒問題, 想法也不錯, 就是把排程直接寫出來, 如果你能找到有效表達的方法, 這樣寫也是沒問題的, 但問題是如果要你把你寫的這個想法一般化, 你會怎麼寫呢? 因為現在有幾位教授, 每個人負責幾門課, 這些都是無法確定的, 所以要寫出每種可能的排程方法就會有點麻煩, 然而若是只用hamiltonian path來說明排程的存在性, 這樣寫起來就容易多了
怪不得老師一直跟我講說幾位教授 幾門課不知道不能直講一個case就說他是全對的我在那邊一直當機XD這方法是我朋友想的 覺得很有道理 但是問老師又說不行 囧怕表達不好 所以上來求救謝謝助教耐心地回答~
張貼留言
6 則留言:
老師教的和書上寫的那個是一樣的, 當有 m 個 R, n 個 U, 並且限定在任何時間點 U 的個數不可超過 R 的個數的情況下, 用那個轉換法可知一個非法的走法可以對應到一個具有 m+1 個 U 以及 n-1 個 R 的排列, 所以非法的個數共有 c(m+n,n-1) 個, 那麼合法的總數就是 c(m+n,n)-c(m+n,n-1)
以(1)小題為例, 在你上課筆記中的那兩行(一個是左箭頭一個是右箭頭)就是在說明一個不合法的走法與一個具有 2R8U 的排列是一一對應的, 也就是說給定一個非法的走法, 我們可以將那個非法的走法唯一轉換成一種具有 2R8U 的排列, 反過來也一樣, 當給定一個具有 2R8U 的排列, 我們一樣也可以把它轉換回一個非法的走法, 所以當有 7 個 R 和 3 個 U 時, 非法的總數為 c(10,2), 所以合法的走法總共會有 c(10,3)-c(10,2) 個
恩 謝謝助教回答
可能是我表達不太好> <
我是想要問
如果希望R必大於U
原本lattice path是因為反轉左邊
RUU |RRRURRR
URR<---inverse
使得C(10,2)為非法數
原本原因是因為超過線了
可以鏡射到另一邊看等價
但老師是用
RUU |RRRURRR
UUURUUU<---inverse
雖然個數是一樣的
但是就理解方式
我覺得鏡射右邊很奇怪耶...
至於(10,2)合法數=7R3U的非法數
這我是知道的
還有不知道助教有沒有看到第一張圖
那一張圖有附上前一題教授排考試的
的題目和解答
因為不太好表達
所以就把筆記丟上來了
在順便麻煩這題了~
1. 有關第一張圖, 你貼的圖和書上寫的解法也是一樣的, 所以我還是看不太知道你的問題是甚麼, 也不太懂你在前一篇寫的想法, 為什麼你會先假設有讓一個教授監考7EXAM的情況發生, 這樣不是一開始就和題目要的有所矛盾了嗎? 得麻煩你再試著解釋一下你的想法囉
2. 不管是將前面做鏡射還是將後面做鏡射, 想法都是一樣的, 以圖二為例, 非法的情形就是前面有k個R, k+1個U, 後面有m-k個R, n-k-1個U, 那麼將前面做鏡射以後就變成前面有k個U, k+1個R, 後面不變, 這樣前面加上後面總共就會有n-1個U, m+1個R, 也就是說, 前轉或者是後轉兩者之間只有U,R互調的差別而已, i.e., 2R8U或者是2U8R的差別
或者再看第三張圖, 這樣子的轉換也就相當於是在說明每種從(0,0)走到(2n,0)的不合法走法, 都可以對應到一個從(-2,0)隨便走到(2n,0)的走法, 也就是在你筆記上那些綠色字所說的, 因為從(-2,0)隨便走到(2n,0)就代表在2n個symbol裡U要比R多兩個, 也就是說在那裏面必須要有n+1個U, n-1個R
謝謝助教的回答:)
關於筆記上那題
可是不超過7不是有包含7的意思嗎?
<=7
所以說用鴿籠
假設A教授有七堂課 B教授有6堂課
他們可以這樣排課
ABABABABABABA
而三位教授
ABCABCAB..
四位
ABCDABCD...
交錯排
而不違反每教授不超過7堂課(含7)
還是題目的意思是不可以等於7
但是這樣筆記上的圖就錯了阿?
還是這是在課本哪裡
我離散是舊版(4)
我可以去翻一翻看一下原題
原題在p6-66範例7, 你對題意的理解沒問題, 想法也不錯, 就是把排程直接寫出來, 如果你能找到有效表達的方法, 這樣寫也是沒問題的, 但問題是如果要你把你寫的這個想法一般化, 你會怎麼寫呢? 因為現在有幾位教授, 每個人負責幾門課, 這些都是無法確定的, 所以要寫出每種可能的排程方法就會有點麻煩, 然而若是只用hamiltonian path來說明排程的存在性, 這樣寫起來就容易多了
怪不得老師一直跟我講說
幾位教授 幾門課不知道
不能直講一個case就說他是全對的
我在那邊一直當機XD
這方法是我朋友想的
覺得很有道理
但是問老師又說不行 囧
怕表達不好 所以上來求救
謝謝助教耐心地回答~
張貼留言